1 /* 2 * $Id: hash.h,v 1.1 2005-09-18 22:04:07 dhmunro Exp $ 3 * Declare interface to hash routines 4 */ 5 /* Copyright (c) 2005, The Regents of the University of California. 6 * All rights reserved. 7 * This file is part of yorick (http://yorick.sourceforge.net). 8 * Read the accompanying LICENSE file for details. 9 */ 10 11 #ifndef HASH_H 12 #define HASH_H 13 14 #include "plugin.h" 15 16 /* ------------------------------------------------------------------------ */ 17 18 typedef struct HashTable HashTable; 19 20 PLUG_API long hashIndex; /* set by HashFind, HashAdd, etc. */ 21 22 PLUG_API int HashFind(const HashTable *table, const char *name, long n); 23 /* Note-- n is the exact length of name, or n==0 to use strlen(name) 24 Usage: 25 if (HashFind(table, name, n)) { 26 ... name exists in table, and was the hashIndex +1st item 27 added to the table ... 28 } else { 29 ... name does not exist, and hashIndex is the value of the 30 hashing function (a slot index) ... 31 } 32 */ 33 34 PLUG_API int HashAdd(HashTable *table, const char *name, long n); 35 /* Note-- n is the exact length of name, or n==0 to use strlen(name) 36 Usage: 37 if (HashAdd(table, name, n)) { 38 ... name existed previously in table, as the hashIndex +1st item 39 added to the table ... 40 } else { 41 ... name did not exist previously, and is now the hashIndex +1st 42 item added to the table ... 43 ... use the HASH_MANAGE macro to manage any lists associated with 44 this hash table, in case they need to be lengthened ... 45 } 46 Note well: The name is copied if added to the table, so the caller 47 should dispose of it as appropriate. 48 */ 49 50 /* ------------------------------------------------------------------------ */ 51 52 PLUG_API int hashRealloc; /* set by HashAdd if it returned 0 and if 53 the call forced table->maxItems to grow */ 54 55 #define HASH_MANAGE(table, type, list) \ 56 if (hashRealloc) (list)= p_realloc((list), (table).maxItems*sizeof(type)) 57 /* NOTE: If you use this, you need to include defmem.h or otherwise 58 declare Yrealloc (same semantics as ANSI standard realloc). 59 Usage: 60 HashTable table; == associates name with index into table.names == 61 Object *list; == typically, one or more lists in addition to 62 table.names are maintained representing the 63 objects which bear the names == 64 ... 65 if (HashAdd(&table, name, n)) { 66 == often, it is an error to add a duplicate name == 67 } else { 68 HASH_MANAGE(table, Object, list); == lengthen list if reqd == 69 list[hashIndex]= value_of_name; 70 } 71 */ 72 73 /* ------------------------------------------------------------------------ */ 74 75 PLUG_API void HashInit(HashTable *table, int estSize); 76 /* Pass HashInit the estimated final nItems for the table to bypass 77 the rehashing which otherwise takes place every with every factor 78 of two size increase. A HashTable with all its members 0 is also 79 a legal initialization; this is the situation after HashClear. */ 80 81 PLUG_API void HashClear(HashTable *table); 82 /* Clear a hash table, freeing all associated memory. */ 83 84 PLUG_API void HashShrink(HashTable *table); 85 /* Shrink maxItems to nItems, and rehash if the number of slots 86 can be reduced. Follow this with the HASH_MANAGE macro if the 87 table has associated lists. */ 88 89 PLUG_API void HashRemove(HashTable *table, long index0); 90 /* Removing an item from a hash table is a very expensive operation, 91 unless it is one of the few elements most recently added to the 92 table. The index0 must have been returned as the hashIndex for a 93 previous call to HashFind or HashAdd. */ 94 95 PLUG_API void HashSwap(HashTable *table, long index0, long index1); 96 /* Swaps the item->index and names corresponding to the two 97 entries, to reorder the names list after an incorrectly ordered 98 sequence of calls to HashAdd. */ 99 100 /* ------------------------------------------------------------------------ */ 101 102 typedef struct HashItem HashItem; 103 104 struct HashTable { 105 long nItems, maxItems; /* used and actual length of names array */ 106 char **names; 107 long nSlots; /* length of items, or number of hash slots */ 108 HashItem **items; 109 }; 110 111 struct HashItem { 112 HashItem *next; /* next item in this hash slot */ 113 long index; /* index into names array in associated HashTable */ 114 }; 115 116 /* ------------------------------------------------------------------------ */ 117 118 typedef struct HashXTable HashXTable; 119 struct HashXTable { 120 long nItems, maxItems; /* used and actual length of names array */ 121 long nSlots; /* length of items, or number of hash slots */ 122 HashItem **items; 123 }; 124 125 PLUG_API int HashXFind(const HashXTable *table, const void *key, long n, 126 int (*Compare)(void *keyTable, 127 long index, const void *key), 128 void *keyTable); 129 /* Notes-- 1. n>0 is the exact length of key (uses HashN) 130 2. Compare(keyTable, index, key) should return 0 when 131 the key matches the index-th entry of the keyTable 132 Usage: 133 if (HashXFind(table, key, n, Compare, keyTable)) { 134 ... key exists in (table,keyTable), and was the hashIndex +1st 135 item added to the table ... 136 } else { 137 ... key does not exist, and hashIndex is the value of the 138 hashing function (a slot index) ... 139 } 140 */ 141 142 PLUG_API int HashXAdd(HashXTable *table, const char *key, long n, 143 int (*Compare)(void *keyTable, 144 long index, const void *key), 145 void *(*Index)(void *keyTable, long index), 146 void *keyTable); 147 /* Notes-- 1. n>0 is the exact length of key (uses HashN) 148 2. Compare(keyTable, index, key) should return 0 when 149 the key matches the index-th entry of the keyTable 150 3. Index(keyTable, index) should return the key for 151 the index-th entry of the keyTable (required for rehash) 152 Usage: 153 HashXTable *table; 154 KeyedObject *keyTable; 155 ... 156 if (HashXAdd(table, name, n, Compare, Index, keyTable)) { 157 ... key existed previously in table, as the hashIndex +1st item 158 added to the table ... 159 } else { 160 ... key did not exist previously, and is now the hashIndex +1st 161 item added to the table ... 162 HASH_MANAGE(*table, KeyedObject, keyTable); 163 keyTable[hashIndex]= object_corresponding_to_key; 164 ... use the HASH_MANAGE macro to manage other lists associated with 165 this hash table, in case they need to be lengthened ... 166 } 167 */ 168 169 PLUG_API void HashXClear(HashXTable *table); 170 /* Clear a hash table, freeing all associated memory. */ 171 172 /* ------------------------------------------------------------------------ */ 173 174 #endif 175