git.zerfleddert.de Git - micropolis/blob - src/tcl/tclhash.h

   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 */