/*      @(#)finger_tbl.h 20.12 93/06/28 SMI      */

/*
 *  (c) Copyright 1989 Sun Microsystems, Inc. Sun design patents
 *  pending in the U.S. and foreign countries. See LEGAL NOTICE
 *  file for terms of the license.
 */

#ifndef finger_table_DEFINED
#define finger_table_DEFINED

/*
 * This is the programmatic interface to the finger table abstraction.
 *
 *     A finger_table is an array of records: .seq[ 0 .. .last_plus_one-1 ].
 *     Each record has an Es_index as its first field, and is
 * .size_of_element bytes long.
 *     The array is ordered by the values of the Es_index field, with the
 * smallest value occurring in the first record of the array.  The
 * implementation supports and requires the ordering.
 *     .last_bounding_index records the last result from ft_bounding_index;
 * it is a cache private to ft_bounding_index used to speed up the common case
 * of a succession of searches for similar positions.
 *     .first_infinity records the first occurrence of an ES_INFINITY;
 * it is a cache private to ft_shift_{up,out} used to speed up a common case
 * of shifts in large tables with many ES_INFINITY's at the end.
 */

#                   ifndef suntool_entity_stream_DEFINED
#include <xview_private/es.h>
#                   endif

typedef struct ft_table
{
    int     last_plus_one;
    unsigned    sizeof_element;
    int     last_bounding_index;
    int     first_infinity;
    Es_index    *seq;
} Ft_table_object;
typedef Ft_table_object *Ft_table;
/* The following two typedef's are for 3.0 compatibility. */
typedef struct ft_table     ft_object;
typedef struct ft_table    *ft_handle;
#define FT_NULL         ((ft_handle)0)

#define FT_CLIENT_CREATE(num_elements, client_type)         \
    ft_create((num_elements), sizeof(client_type)-sizeof(Es_index))
#define FT_SET_ALL(finger_table, to, client_data)           \
    ft_set((finger_table), 0, (finger_table).last_plus_one,     \
           (to), (client_data))
#define FT_CLEAR_ALL(finger_table)                  \
    FT_SET_ALL((finger_table), ES_INFINITY, (char *)0)

#define FT_ADDR(_handle, _index, _addr_delta)               \
    (Es_index *)(                           \
                                            ((char *)((_handle)->seq)) + ((_index)*(_addr_delta)) )
#define FT_NEXT_ADDR(_addr, _addr_delta)                \
    (Es_index *)( (char *)(_addr) + (_addr_delta) )
#define FT_PREV_ADDR(_addr, _addr_delta)                \
    (Es_index *)( (char *)(_addr) - (_addr_delta) )

#define FT_ADDRESS(_handle, _index)                 \
    FT_ADDR((_handle), (_index), (_handle)->sizeof_element)
#define FT_NEXT_ADDRESS(_handle, _addr)                 \
    FT_NEXT_ADDR((_addr), (_handle)->sizeof_element )
#define FT_PREV_ADDRESS(_handle, _addr)                 \
    FT_PREV_ADDR((_addr), (_handle)->sizeof_element )

#endif

extern ft_object
ft_create(/* last_plus_one, sizeof_client_data */);
#ifdef notdef
int     last_plus_one, sizeof_client_data;
#endif
/* Allocates a seq of last_plus_one elements, each occupying
 *   sizeof(Es_index)+sizeof_client_data bytes, then returns an ft_object
 *   correctly initialized.
 * NOTE: The individual sequence elements are not initialized.
 */

extern void
ft_destroy(/* table */);
#ifdef notdef
ft_handle   table;
#endif
/* Deallocates the sequence and adjusts *table to remove all references
 *   to the deallocated sequence.
 */

extern void
ft_expand(/* table, by */);
#ifdef notdef
ft_handle   table;
int     by;
#endif
/* Replaces the old sequence with a new sequence that is longer (by > 0) or
 *   shorter (if by < 0), while preserving all appropriate sequence contents.
 * When the sequence increases in size, new elements are at the end.
 * NOTE: If by > 0, the new sequence elements are not initialized.
 */

extern void
ft_shift_up(/* table, first, last_plus_one, expand_by */);
#ifdef notdef
ft_handle   table;
int     first, last_plus_one, expand_by;
#endif
/* Shifts the elements in the sequence up so that seq[i],
 *   first <= i < last_plus_one, is unused.
 * The shift treats an element with position ES_INFINITY as the beginning of
 *   a range of empty elements, and stops the shift there.
 * If no empty elements can be found, the table is first expanded by expand_by
 *   and the extra elements have their position set to ES_INFINITY.
 */

extern void
ft_shift_out(/* table, first, last_plus_one */);
#ifdef notdef
ft_handle   table;
int     first, last_plus_one;
#endif
/* Shifts the elements in the sequence down so that seq[first+i] gets the
 *   value from seq[last_plus_one+i].
 * The shift treats an element with position ES_INFINITY as an empty element,
 *   and stops the shift there.
 * Elements that are invalidated at the end of the sequence have their
 *   position set to ES_INFINITY.
 */

extern void
ft_set(/* finger_table, first, last_plus_one, to, client_data */);
#ifdef notdef
ft_object    finger_table;
int      first, last_plus_one;
Es_index     to;
char        *client_data;
#endif
/* All sequence elements in [first..last_plus_one) have their positions
 *   set to 'to', and if client_data is not 0, their client data area set
 *   to *client_data.
 */

extern void
ft_set_esi_span(/* finger_table, first, last_plus_one, to, client_data */);
#ifdef notdef
ft_object    finger_table;
Es_index     first, last_plus_one, to;
char        *client_data;
#endif
/* Like ft_set, but sets all elements whose positions are in the range
 *   [first..last_plus_one).
 */

extern int
ft_bounding_index(/* finger_table, pos */);
#ifdef notdef
Ft_table    finger_table;
Es_index    pos;
#endif
/* Returns an index for finger_table that is either such that:
 *   finger_table->seq[index] <= pos < finger_table->seq[index+1], with
 *      index+1 < finger_table->last_plus_one, or;
 *   finger_table->seq[index] <= pos, with
 *      index+1 == finger_table->last_plus_one, or;
 *   finger_table->last_plus_one.
 * Note: if there are multiple occurrences of pos in the seq array, the
 *   returned index will be the index of the last occurrence.
 */

extern int
ft_index_for_position(/* finger_table, pos */);
#ifdef notdef
ft_object   finger_table;
Es_index    pos;
#endif
/* Returns an index for finger_table that is either:
 *   the smallest index such that .seq[index] = pos, with
 *      index < finger_table.last_plus_one, or;
 *   finger_table.last_plus_one
 */

extern Es_index
ft_position_for_index(/* finger_table, index */);
#ifdef notdef
ft_object   finger_table;
int     index;
#endif
/* Returns the position value of the sequence element specified by index,
 *   unless index is too large, in which case ES_CANNOT_SET is returned.
 * This is most useful when you do not want to typecast the sequence.
 */

extern void
ft_add_delta(/* finger_table, from, delta */);
#ifdef notdef
ft_object   finger_table;
int     from;
long int    delta;
#endif
/* Beginning at finger_table.seq[from], adds delta to each element until
 *   either the end of the table is reached or a position of ES_INFINITY.
 */
