projects / micropolis / blame
| Commit | Line | Data |
|---|---|---|
| 6a5fa4e0 MG |
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 */ |