00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #ifndef lint
00021 static const char rcsid[] = "$Id: hash_table.c,v 1.20 2006-10-03 04:02:12 sven Exp $";
00022 #endif
00023
00024 #include <eggdrop/eggdrop.h>
00025
00026 static unsigned int my_string_hash(const void *key);
00027 static unsigned int my_int_hash(const void *key);
00028 static unsigned int my_mixed_hash (const void *key);
00029 static int my_int_cmp(const void *left, const void *right);
00030
00031 hash_table_t *hash_table_create(hash_table_hash_alg alg, hash_table_cmp_alg cmp, int nrows, int flags)
00032 {
00033 hash_table_t *ht;
00034
00035 if (nrows <= 0) nrows = 13;
00036
00037 ht = calloc(1, sizeof(*ht));
00038 ht->rows = calloc(nrows, sizeof(*ht->rows));
00039
00040 if (alg) ht->hash = alg;
00041 else {
00042 if (flags & HASH_TABLE_STRINGS) ht->hash = my_string_hash;
00043 else if (flags & HASH_TABLE_INTS) ht->hash = my_int_hash;
00044 else ht->hash = my_mixed_hash;
00045 }
00046 if (cmp) ht->cmp = cmp;
00047 else {
00048 if (flags & HASH_TABLE_INTS) ht->cmp = my_int_cmp;
00049 else ht->cmp = (hash_table_cmp_alg) strcmp;
00050 }
00051 ht->flags = flags;
00052 ht->max_rows = nrows;
00053 return(ht);
00054 }
00055
00056 int hash_table_delete(hash_table_t *ht)
00057 {
00058 hash_table_entry_t *entry, *next;
00059 hash_table_row_t *row;
00060 int i;
00061
00062 if (!ht) return(-1);
00063
00064 for (i = 0; i < ht->max_rows; i++) {
00065 row = ht->rows+i;
00066 for (entry = row->head; entry; entry = next) {
00067 next = entry->next;
00068 if (ht->flags & HASH_TABLE_FREE_KEY)
00069 free(entry->key);
00070 free(entry);
00071 }
00072 }
00073 free(ht->rows);
00074 free(ht);
00075
00076 return(0);
00077 }
00078
00079 int hash_table_check_resize(hash_table_t *ht)
00080 {
00081 if (!ht || (ht->flags & HASH_TABLE_NORESIZE)) return(-1);
00082
00083 if ((100 * ht->cells_in_use) / ht->max_rows > HASH_TABLE_RESIZE_BOUNDARY) {
00084 hash_table_resize(ht, ht->max_rows * 3);
00085 }
00086 return(0);
00087 }
00088
00089 int hash_table_resize(hash_table_t *ht, int nrows)
00090 {
00091 int i, newidx;
00092 hash_table_row_t *oldrow, *newrows;
00093 hash_table_entry_t *entry, *next;
00094
00095 if (!ht) return(-1);
00096
00097
00098 newrows = calloc(nrows, sizeof(*newrows));
00099
00100
00101 for (i = 0; i < ht->max_rows; i++) {
00102 oldrow = ht->rows+i;
00103 for (entry = oldrow->head; entry; entry = next) {
00104 next = entry->next;
00105 newidx = entry->hash % nrows;
00106 entry->next = newrows[newidx].head;
00107 newrows[newidx].head = entry;
00108 newrows[newidx].len++;
00109 }
00110 }
00111
00112 free(ht->rows);
00113 ht->rows = newrows;
00114 ht->max_rows = nrows;
00115 return(0);
00116 }
00117
00118 int hash_table_insert(hash_table_t *ht, void *key, void *data)
00119 {
00120 unsigned int hash;
00121 int idx;
00122 hash_table_entry_t *entry;
00123 hash_table_row_t *row;
00124
00125 if (!ht) return(-1);
00126
00127 hash = ht->hash(key);
00128 idx = hash % ht->max_rows;
00129 row = ht->rows+idx;
00130
00131
00132 entry = malloc(sizeof(*entry));
00133 entry->key = key;
00134 entry->data = data;
00135 entry->hash = hash;
00136
00137
00138 entry->next = row->head;
00139 row->head = entry;
00140
00141
00142 row->len++;
00143 ht->cells_in_use++;
00144
00145
00146 if (!(ht->flags & HASH_TABLE_NORESIZE)) {
00147 hash_table_check_resize(ht);
00148 }
00149
00150 return(0);
00151 }
00152
00153 int hash_table_find(hash_table_t *ht, const void *key, void *dataptr)
00154 {
00155 int idx;
00156 unsigned int hash;
00157 hash_table_entry_t *entry;
00158 hash_table_row_t *row;
00159
00160 if (!ht) return (-1);
00161
00162 hash = ht->hash(key);
00163 idx = hash % ht->max_rows;
00164 row = ht->rows+idx;
00165
00166 for (entry = row->head; entry; entry = entry->next) {
00167 if (hash == entry->hash && !ht->cmp(key, entry->key)) {
00168 *(void **)dataptr = entry->data;
00169 return(0);
00170 }
00171 }
00172 return(-1);
00173 }
00174
00175 int hash_table_remove(hash_table_t *ht, const void *key, void *dataptr)
00176 {
00177 int idx;
00178 unsigned int hash;
00179 hash_table_entry_t *entry, *last;
00180 hash_table_row_t *row;
00181
00182 if (!ht) return(-1);
00183
00184 hash = ht->hash(key);
00185 idx = hash % ht->max_rows;
00186 row = ht->rows+idx;
00187
00188 last = NULL;
00189 for (entry = row->head; entry; entry = entry->next) {
00190 if (hash == entry->hash && !ht->cmp(key, entry->key)) {
00191 if (dataptr) *(void **)dataptr = entry->data;
00192
00193
00194 if (last) last->next = entry->next;
00195 else row->head = entry->next;
00196
00197 if (ht->flags & HASH_TABLE_FREE_KEY)
00198 free(entry->key);
00199
00200 free(entry);
00201 ht->cells_in_use--;
00202 return(0);
00203 }
00204 last = entry;
00205 }
00206 return(-1);
00207 }
00208
00209 int hash_table_walk(hash_table_t *ht, hash_table_node_func callback, void *param)
00210 {
00211 hash_table_row_t *row;
00212 hash_table_entry_t *entry, *next;
00213 int i;
00214
00215 if (!ht) return(-1);
00216
00217 for (i = 0; i < ht->max_rows; i++) {
00218 row = ht->rows+i;
00219 for (entry = row->head; entry;) {
00220 next = entry->next;
00221 callback(entry->key, &entry->data, param);
00222 entry = next;
00223 }
00224 }
00225 return(0);
00226 }
00227
00228 static int my_int_cmp(const void *left, const void *right)
00229 {
00230 return((int) left - (int) right);
00231 }
00232
00233 static unsigned int my_string_hash(const void *key)
00234 {
00235 int hash, loop, keylen;
00236 const unsigned char *k;
00237
00238 #define HASHC hash = *k++ + 65599 * hash
00239 hash = 0;
00240 k = key;
00241 keylen = strlen(key);
00242
00243 if (!keylen) return(0);
00244
00245 loop = (keylen + 8 - 1) >> 3;
00246 switch (keylen & (8 - 1)) {
00247 case 0:
00248 do {
00249 HASHC;
00250 case 7:
00251 HASHC;
00252 case 6:
00253 HASHC;
00254 case 5:
00255 HASHC;
00256 case 4:
00257 HASHC;
00258 case 3:
00259 HASHC;
00260 case 2:
00261 HASHC;
00262 case 1:
00263 HASHC;
00264 } while (--loop);
00265 }
00266 return(hash);
00267 }
00268
00269 static unsigned int my_int_hash(const void *key)
00270 {
00271 return((unsigned int)key);
00272 }
00273
00274 static unsigned int my_mixed_hash (const void *key)
00275 {
00276 const unsigned char *k;
00277 unsigned int hash;
00278
00279 k = key;
00280 hash = 0;
00281 while (*k) {
00282 hash *= 16777619;
00283 hash ^= *k++;
00284 }
00285 return(hash);
00286 }