/* tclInt.h */

typedef struct Dict Dict;

typedef struct List {
    int refCount;
    int maxElemCount;		/* Total number of element array slots. */
    int elemCount;		/* Current number of list elements. */
    int canonicalFlag;		/* Set if the string representation was
				 * derived from the list representation. May
				 * be ignored if there is no string rep at
				 * all.*/
    Tcl_Obj *elements;		/* First list element; the struct is grown to
				 * accomodate all elements. */
    Dict *dict;			/* Dict index over the list, or NULL if this
				 * list does not presently have a dict
				 * representation. */
} List;

/* tclDictObj.c */

typedef struct DictEntry {
    int next;		    /* Index of the next entry in this hash bucket, or
			     * -1 for end of chain. Indexes point into the
			     * entries array. */
    unsigned long hash;	    /* This entry's hash value. */
    int key;		    /* The key, which is an index into elements.
                             * Because elements is an alternating key/value
                             * list, key is always an even number. The value
                             * is implicit: add one to key. Half key is the
                             * upper bound of entry's index in the allocation
                             * array. If the list does not contain duplicate
                             * keys, half key is also equal to the index. */
} DictEntry;

#define DICT_STATIC_BUCKETS 4
#define DICT_STATIC_ENTRIES 12

struct Dict {
    int *buckets;	    /* Pointer to bucket array. Each element is the
			     * bucket head entry's index into the entries
			     * array, or -1 if the bucket is empty. */
    DictEntry *entries;	    /* Pointer to entry array. */
    int *allocation;	    /* Partitioned list tracking the allocation of
			     * entries, containing indexes into entries. The
			     * first numEntries values are the indexes of
			     * allocated entries, in the order they were
			     * created. The remaining values are the indexes
			     * of unused entries, in arbitrary order. */
    int maxBuckets;	    /* Length of the buckets array. */
    int numEntries;	    /* Number of entries present in table. Equal to
			     * elemCount unless there are duplicate keys in
			     * the elements array. */
    int maxEntries;	    /* Length of the entries and allocation arrays.
			     * When numEntries exceeds this, the table is
			     * enlarged. */
    unsigned long mask;	    /* Mask value used in hashing function. */
    unsigned int downShift; /* Shift count used in hashing function. Designed
			     * to use high-order bits of randomized keys. */
    int staticBuckets[DICT_STATIC_BUCKETS];
			    /* Bucket array used for small dicts to avoid
			     * malloc. When the dict is small, buckets points
			     * to this array. */
    DictEntry staticEntries[DICT_STATIC_ENTRIES];
			    /* Entry array used for small dicts to avoid
			     * malloc. When the dict is small, entries points
			     * to this array. */
    Tcl_Obj *chain;	    /* Linked list used for invalidating the string
			     * reps of updated nested dictionaries. */
};

/*

operating on values:
lot contains lval key        ;# true if lval contains key
lot difference ?lval ...?    ;# symmetric difference
lot empty ?lval ...?         ;# true if all lots are empty
lot equal lval ?lval ...?    ;# true if all lots are equal
lot exclude lval ?key ...?   ;# remove some keys
lot include lval ?key ...?   ;# add some keys
lot index lval index         ;# index'th key
lot info lval                ;# statistics
lot intersect ?lval ...?     ;# intersection between lots
lot search lval key          ;# index of key
lot size lval                ;# number of keys
lot subset lval lval         ;# true if second is subset
lot subtract lval ?lval ...? ;# remove keys
lot superset lval lval       ;# true if second is superset
lot union ?lval ...?         ;# union between lots

operating on variables:
lot set lvar ?key ...?       ;# set some keys
lot unset lvar ?key ...?     ;# unset some keys

other:
lot create ?key ...?         ;# construct a lot

*/