Return to tclhash.h CVS log

Up to [Micropolis - Activity] / micropolis / src / tcl

Annotation of micropolis/src/tcl/tclhash.h, revision 1.1

1.1     ! root        1: /*
        !             2:  * tclHash.h --
        !             3:  *
        !             4:  *     This header file declares the facilities provided by the
        !             5:  *     Tcl hash table procedures.
        !             6:  *
        !             7:  * Copyright 1991 Regents of the University of California
        !             8:  * Permission to use, copy, modify, and distribute this
        !             9:  * software and its documentation for any purpose and without
        !            10:  * fee is hereby granted, provided that the above copyright
        !            11:  * notice appear in all copies.  The University of California
        !            12:  * makes no representations about the suitability of this
        !            13:  * software for any purpose.  It is provided "as is" without
        !            14:  * express or implied warranty.
        !            15:  *
        !            16:  * $Header: /sprite/src/lib/tcl/RCS/tclHash.h,v 1.3 91/08/27 11:36:04 ouster Exp $ SPRITE (Berkeley)
        !            17:  */
        !            18: 
        !            19: #ifndef _TCLHASH
        !            20: #define _TCLHASH
        !            21: 
        !            22: #ifndef _TCL
        !            23: #include <tcl.h>
        !            24: #endif
        !            25: 
        !            26: /*
        !            27:  * Structure definition for an entry in a hash table.  No-one outside
        !            28:  * Tcl should access any of these fields directly;  use the macros
        !            29:  * defined below.
        !            30:  */
        !            31: 
        !            32: typedef struct Tcl_HashEntry {
        !            33:     struct Tcl_HashEntry *nextPtr;     /* Pointer to next entry in this
        !            34:                                         * hash bucket, or NULL for end of
        !            35:                                         * chain. */
        !            36:     struct Tcl_HashTable *tablePtr;    /* Pointer to table containing entry. */
        !            37:     struct Tcl_HashEntry **bucketPtr;  /* Pointer to bucket that points to
        !            38:                                         * first entry in this entry's chain:
        !            39:                                         * used for deleting the entry. */
        !            40:     ClientData clientData;             /* Application stores something here
        !            41:                                         * with Tcl_SetHashValue. */
        !            42:     union {                            /* Key has one of these forms: */
        !            43:        char *oneWordValue;             /* One-word value for key. */
        !            44:        int words[1];                   /* Multiple integer words for key.
        !            45:                                         * The actual size will be as large
        !            46:                                         * as necessary for this table's
        !            47:                                         * keys. */
        !            48:        char string[4];                 /* String for key.  The actual size
        !            49:                                         * will be as large as needed to hold
        !            50:                                         * the key. */
        !            51:     } key;                             /* MUST BE LAST FIELD IN RECORD!! */
        !            52: } Tcl_HashEntry;
        !            53: 
        !            54: /*
        !            55:  * Structure definition for a hash table.  Must be in tcl.h so clients
        !            56:  * can allocate space for these structures, but clients should never
        !            57:  * access any fields in this structure.
        !            58:  */
        !            59: 
        !            60: #define TCL_SMALL_HASH_TABLE 4
        !            61: typedef struct Tcl_HashTable {
        !            62:     Tcl_HashEntry **buckets;           /* Pointer to bucket array.  Each
        !            63:                                         * element points to first entry in
        !            64:                                         * bucket's hash chain, or NULL. */
        !            65:     Tcl_HashEntry *staticBuckets[TCL_SMALL_HASH_TABLE];
        !            66:                                        /* Bucket array used for small tables
        !            67:                                         * (to avoid mallocs and frees). */
        !            68:     int numBuckets;                    /* Total number of buckets allocated
        !            69:                                         * at **bucketPtr. */
        !            70:     int numEntries;                    /* Total number of entries present
        !            71:                                         * in table. */
        !            72:     int rebuildSize;                   /* Enlarge table when numEntries gets
        !            73:                                         * to be this large. */
        !            74:     int downShift;                     /* Shift count used in hashing
        !            75:                                         * function.  Designed to use high-
        !            76:                                         * order bits of randomized keys. */
        !            77:     int mask;                          /* Mask value used in hashing
        !            78:                                         * function. */
        !            79:     int keyType;                       /* Type of keys used in this table. 
        !            80:                                         * It's either TCL_STRING_KEYS,
        !            81:                                         * TCL_ONE_WORD_KEYS, or an integer
        !            82:                                         * giving the number of ints in a
        !            83:                                         */
        !            84:     Tcl_HashEntry *(*findProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
        !            85:            char *key));
        !            86:     Tcl_HashEntry *(*createProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
        !            87:            char *key, int *newPtr));
        !            88: } Tcl_HashTable;
        !            89: 
        !            90: /*
        !            91:  * Structure definition for information used to keep track of searches
        !            92:  * through hash tables:
        !            93:  */
        !            94: 
        !            95: typedef struct Tcl_HashSearch {
        !            96:     Tcl_HashTable *tablePtr;           /* Table being searched. */
        !            97:     int nextIndex;                     /* Index of next bucket to be
        !            98:                                         * enumerated after present one. */
        !            99:     Tcl_HashEntry *nextEntryPtr;       /* Next entry to be enumerated in the
        !           100:                                         * the current bucket. */
        !           101: } Tcl_HashSearch;
        !           102: 
        !           103: /*
        !           104:  * Acceptable key types for hash tables:
        !           105:  */
        !           106: 
        !           107: #define TCL_STRING_KEYS                0
        !           108: #define TCL_ONE_WORD_KEYS      1
        !           109: 
        !           110: /*
        !           111:  * Macros for clients to use to access fields of hash entries:
        !           112:  */
        !           113: 
        !           114: #define Tcl_GetHashValue(h) ((h)->clientData)
        !           115: #define Tcl_SetHashValue(h, value) ((h)->clientData = (ClientData) (value))
        !           116: #define Tcl_GetHashKey(tablePtr, h) \
        !           117:     ((char *) (((tablePtr)->keyType == TCL_ONE_WORD_KEYS) ? (h)->key.oneWordValue \
        !           118:                                                : (h)->key.string))
        !           119: 
        !           120: /*
        !           121:  * Macros to use for clients to use to invoke find and create procedures
        !           122:  * for hash tables:
        !           123:  */
        !           124: 
        !           125: #define Tcl_FindHashEntry(tablePtr, key) \
        !           126:        (*((tablePtr)->findProc))(tablePtr, key)
        !           127: #define Tcl_CreateHashEntry(tablePtr, key, newPtr) \
        !           128:        (*((tablePtr)->createProc))(tablePtr, key, newPtr)
        !           129: 
        !           130: /*
        !           131:  * Exported procedures:
        !           132:  */
        !           133: 
        !           134: extern void            Tcl_DeleteHashEntry _ANSI_ARGS_((
        !           135:                            Tcl_HashEntry *entryPtr));
        !           136: extern void            Tcl_DeleteHashTable _ANSI_ARGS_((
        !           137:                            Tcl_HashTable *tablePtr));
        !           138: extern Tcl_HashEntry * Tcl_FirstHashEntry _ANSI_ARGS_((
        !           139:                            Tcl_HashTable *tablePtr,
        !           140:                            Tcl_HashSearch *searchPtr));
        !           141: extern char *          Tcl_HashStats _ANSI_ARGS_((Tcl_HashTable *tablePtr));
        !           142: extern void            Tcl_InitHashTable _ANSI_ARGS_((Tcl_HashTable *tablePtr,
        !           143:                            int keyType));
        !           144: extern Tcl_HashEntry * Tcl_NextHashEntry _ANSI_ARGS_((
        !           145:                            Tcl_HashSearch *searchPtr));
        !           146: 
        !           147: #endif /* _TCLHASH */

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.