lib/eggdrop/hash_table.h File Reference

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_replace	(	hash_table_t *	ht,
		const void *	key,
		void *	data
	)

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 }


Data Structures
struct	hash_table_entry_b
struct	hash_table_row_t
struct	hash_table_b
Defines
#define	HASH_TABLE_STRINGS 1
#define	HASH_TABLE_INTS 2
#define	HASH_TABLE_MIXED 4
#define	HASH_TABLE_NORESIZE 8
#define	HASH_TABLE_FREE_KEY 16
#define	HASH_TABLE_RESIZE_BOUNDARY 150
Typedefs
typedef unsigned int(*	hash_table_hash_alg )(const void *key)
typedef int(*	hash_table_cmp_alg )(const void left, const void right)
typedef int(*	hash_table_node_func )(const void key, void data, void *param)
typedef struct hash_table_entry_b	hash_table_entry_t
typedef struct hash_table_b	hash_table_t
Functions
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_replace (hash_table_t ht, const 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)