/* (C) Copyright International Business Machines Corporation 23 January */
/* 1990.  All Rights Reserved. */
/*  */
/* See the file USERAGREEMENT distributed with this software for full */
/* terms and conditions of use. */
/* SCCS Info: @(#)tblrep.h	1.5 3/13/90 */

#ifndef tblrep_included

/*

vector: for ordered tables.  O(1) lookup_at; everything else is O(n)

*/

typedef struct {
    counter maxsize;		/* number of elements allocated. */
    counter hunksize;		/* number of elements to grow by. */
    valcell elements[ARBSIZE];	/* the elements themselves. */

} vec_trep;


typedef int vec_position;

/*

charstring: just like vector, but compacted for single-bytes valcells

*/

typedef struct {
    counter maxsize;		/* number of elements allocated. */
    counter hunksize;		/* number of elements to grow by. */
    char elements[ARBSIZE];	/* the elements themselves. */

} chs_trep;

typedef int chs_position;

#define stringval(t) (vstringval((t)->value))

#define vstringval(valc) \
   ((valc).table->tbls[ORDER_TBL].rep.chs->elements)

/*

 height-balanced AVL tree: for keyed tables.  O(log(n)) everything except
 equal, which is O(n).

*/

typedef avlnode_t *keyavl_trep;	/* the root of the AVL tree which holds the */
				/*  values. */

#define AVL_LEFT TRUE
#define AVL_RIGHT FALSE

typedef struct {
    avlnode_t *node;		/* current node */

    flag direction;		/* were we doing the left or right subtree? */

} nodepos;


typedef struct {
    int top;

    counter size;

    nodepos stk[ARBSIZE];

} avl_position;

/*

doubly-linked list: for ordered tables.  insert/remove/lookup at beginning or
end are O(1), everything else is O(n).

a dummy element is used to point to the head and tail of the list.

*/

typedef struct dublink_struct {
    struct dublink_struct *prev, *next;
				/* chain, chain, chaiaiaiain, chain of fools */

    valcell value;		/* the value for this element */

} dublink_trep;


/*

linked list -- for unordered, unkeyed tables (bags).  insert/remove are
O(1), lookups are O(n), equal is O(n**2) or O(n*log(n)), depending on
whether or not we quicksort a copy of the list before comparing.

*/

typedef struct linklist_struct {
    struct linklist_struct *next;
				/* next element. */
    valcell value;		/* the value. */

} linklist_trep;


typedef struct {
    linklist_trep *prevelem;

    linklist_trep *nextelem;

    linklist_trep *curelem;

} linklist_position;



/*

hash table: for keyed or indexed tables.  O(1) insert/remove/lookup.

*/

typedef struct hash_struct {
    struct hash_struct *next;	/* the next buck in the list */

    valcell value;		/* value of this bucket */

} hash_bucket;

typedef struct {
    counter tablesize;		/* size of the hashtable. */

    hash_bucket table[ARBSIZE];	/* the hashtable itself. */

} hash_trep;

/*

type tblrep is a union of all of the different table representations.  it is a
single-word quantity.

*/

typedef union {

    /* ordered tables */

    vec_trep *vec;		/* vector */
    chs_trep *chs;		/* charstring */
    dublink_trep *dublink;	/* doubly-linked list */

    /* keyed tables */

    keyavl_trep keyavl;		/* keyed AVL tree */
    hash_trep hash;		/* hashed keyed or indexed table */

    /* unordered, unkeyed tables */

    linklist_trep *linklist;	/* singly-linked list (bag) */

} tblrep;


/*

position: how the various table representations hold state about the current
position of a get or find loop

*/

typedef union {
    vec_position vec;		/* vector */
    chs_position chs;		/* charstring */
    linklist_position *linklist;
    avl_position *avl;

} position;

#endif
#define tblrep_included
