#include <eggdrop/eggdrop.h>
Go to the source code of this file.
Defines | |
#define | HASHC hash = *k++ + 65599 * hash |
Functions | |
static unsigned int | my_string_hash (const void *key) |
static unsigned int | my_int_hash (const void *key) |
static unsigned int | my_mixed_hash (const void *key) |
static int | my_int_cmp (const void *left, const void *right) |
hash_table_t * | hash_table_create (hash_table_hash_alg alg, hash_table_cmp_alg cmp, int nrows, int flags) |
int | hash_table_delete (hash_table_t *ht) |
int | hash_table_check_resize (hash_table_t *ht) |
int | hash_table_resize (hash_table_t *ht, int nrows) |
int | hash_table_insert (hash_table_t *ht, void *key, void *data) |
int | hash_table_find (hash_table_t *ht, const void *key, void *dataptr) |
int | hash_table_remove (hash_table_t *ht, const void *key, void *dataptr) |
int | hash_table_walk (hash_table_t *ht, hash_table_node_func callback, void *param) |
Variables | |
static const char | rcsid [] = "$Id: hash_table.c,v 1.20 2006-10-03 04:02:12 sven Exp $" |
#define HASHC hash = *k++ + 65599 * hash |
Referenced by my_string_hash().
int hash_table_check_resize | ( | hash_table_t * | ht | ) |
Definition at line 79 of file hash_table.c.
References hash_table_b::cells_in_use, hash_table_b::flags, HASH_TABLE_NORESIZE, hash_table_resize(), HASH_TABLE_RESIZE_BOUNDARY, and hash_table_b::max_rows.
Referenced by hash_table_insert().
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 }
hash_table_t* hash_table_create | ( | hash_table_hash_alg | alg, | |
hash_table_cmp_alg | cmp, | |||
int | nrows, | |||
int | flags | |||
) |
Definition at line 31 of file hash_table.c.
References hash_table_b::cmp, hash_table_b::flags, hash_table_b::hash, HASH_TABLE_INTS, HASH_TABLE_STRINGS, hash_table_b::max_rows, my_int_cmp(), my_int_hash(), my_mixed_hash(), my_string_hash(), and hash_table_b::rows.
Referenced by botnet_init(), partychan_init(), uhost_cache_init(), and user_init().
00032 { 00033 hash_table_t *ht; 00034 00035 if (nrows <= 0) nrows = 13; /* Give them a small table to start with. */ 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 }
int hash_table_delete | ( | hash_table_t * | ht | ) |
Definition at line 56 of file hash_table.c.
References hash_table_b::flags, HASH_TABLE_FREE_KEY, hash_table_row_t::head, hash_table_entry_b::key, hash_table_b::max_rows, hash_table_entry_b::next, garbage_list::next, and hash_table_b::rows.
Referenced by botnet_shutdown(), partychan_shutdown(), uhost_cache_destroy(), and user_shutdown().
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 }
int hash_table_find | ( | hash_table_t * | ht, | |
const void * | key, | |||
void * | dataptr | |||
) |
Definition at line 153 of file hash_table.c.
References hash_table_b::cmp, hash_table_entry_b::data, hash_table_entry_b::hash, hash_table_b::hash, hash_table_row_t::head, hash_table_entry_b::key, hash_table_b::max_rows, hash_table_entry_b::next, and hash_table_b::rows.
Referenced by botnet_lookup(), cache_lookup(), partychan_lookup_cid(), uhost_cache_addref(), user_get_uid(), user_lookup_by_handle(), user_lookup_by_irchost(), user_lookup_by_irchost_nocache(), and user_lookup_by_uid().
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 }
int hash_table_insert | ( | hash_table_t * | ht, | |
void * | key, | |||
void * | data | |||
) |
Definition at line 118 of file hash_table.c.
References hash_table_b::cells_in_use, hash_table_entry_b::data, hash_table_b::flags, hash_table_entry_b::hash, hash_table_b::hash, hash_table_check_resize(), HASH_TABLE_NORESIZE, hash_table_row_t::head, hash_table_entry_b::key, hash_table_row_t::len, hash_table_b::max_rows, hash_table_entry_b::next, and hash_table_b::rows.
Referenced by botnet_new(), real_user_new(), uhost_cache_addref(), uhost_cache_swap(), user_change_handle(), and user_lookup_by_irchost().
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 /* Allocate an entry. */ 00132 entry = malloc(sizeof(*entry)); 00133 entry->key = key; 00134 entry->data = data; 00135 entry->hash = hash; 00136 00137 /* Insert it into the list. */ 00138 entry->next = row->head; 00139 row->head = entry; 00140 00141 /* Update stats. */ 00142 row->len++; 00143 ht->cells_in_use++; 00144 00145 /* See if we need to update the table. */ 00146 if (!(ht->flags & HASH_TABLE_NORESIZE)) { 00147 hash_table_check_resize(ht); 00148 } 00149 00150 return(0); 00151 }
int hash_table_remove | ( | hash_table_t * | ht, | |
const void * | key, | |||
void * | dataptr | |||
) |
Definition at line 175 of file hash_table.c.
References hash_table_b::cells_in_use, hash_table_b::cmp, hash_table_entry_b::data, hash_table_b::flags, hash_table_entry_b::hash, hash_table_b::hash, HASH_TABLE_FREE_KEY, hash_table_row_t::head, hash_table_entry_b::key, hash_table_b::max_rows, hash_table_entry_b::next, NULL, and hash_table_b::rows.
Referenced by botnet_really_delete(), cache_rand_cleanup(), cache_user_del(), partychan_delete(), uhost_cache_decref(), uhost_cache_swap(), user_change_handle(), and user_delete().
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 /* Remove it from the row's list. */ 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 }
int hash_table_resize | ( | hash_table_t * | ht, | |
int | nrows | |||
) |
Definition at line 89 of file hash_table.c.
References hash_table_entry_b::hash, hash_table_row_t::head, hash_table_row_t::len, hash_table_b::max_rows, hash_table_entry_b::next, garbage_list::next, and hash_table_b::rows.
Referenced by hash_table_check_resize().
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 /* First allocate the new rows. */ 00098 newrows = calloc(nrows, sizeof(*newrows)); 00099 00100 /* Now populate it with the old entries. */ 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 }
int hash_table_walk | ( | hash_table_t * | ht, | |
hash_table_node_func | callback, | |||
void * | param | |||
) |
Definition at line 209 of file hash_table.c.
References hash_table_entry_b::data, hash_table_row_t::head, hash_table_entry_b::key, hash_table_b::max_rows, hash_table_entry_b::next, garbage_list::next, and hash_table_b::rows.
Referenced by cache_rand_cleanup(), cache_user_del(), partyline_cmd_match_attr(), partyline_cmd_match_ircmask(), uhost_cache_destroy(), user_add_ircmask(), user_save(), user_shutdown(), and user_walk().
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 }
static int my_int_cmp | ( | const void * | left, | |
const void * | right | |||
) | [static] |
static unsigned int my_int_hash | ( | const void * | key | ) | [static] |
static unsigned int my_mixed_hash | ( | const void * | key | ) | [static] |
Definition at line 274 of file hash_table.c.
Referenced by hash_table_create().
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 }
static unsigned int my_string_hash | ( | const void * | key | ) | [static] |
Definition at line 233 of file hash_table.c.
References HASHC.
Referenced by hash_table_create().
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 }
const char rcsid[] = "$Id: hash_table.c,v 1.20 2006-10-03 04:02:12 sven Exp $" [static] |
Definition at line 21 of file hash_table.c.