1 /* hash.c - hash tables for opkg
3 Steven M. Ayer, Jamey Hicks
5 Copyright (C) 2002 Compaq Computer Corporation
7 This program is free software; you can redistribute it and/or
8 modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 2, or (at
10 your option) any later version.
12 This program is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
22 #include "hash_table.h"
23 #include "opkg_message.h"
24 #include "libbb/libbb.h"
28 djb2_hash(const unsigned char *str)
30 unsigned long hash = 5381;
33 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
38 hash_index(hash_table_t *hash, const char *key)
40 return djb2_hash((const unsigned char *)key) % hash->n_buckets;
44 * this is an open table keyed by strings
47 hash_table_init(const char *name, hash_table_t *hash, int len)
49 if (hash->entries != NULL) {
50 fprintf(stderr, "ERROR: %s called on a non empty hash table\n",
55 memset(hash, 0, sizeof(hash_table_t));
58 hash->n_buckets = len;
59 hash->entries = xcalloc(hash->n_buckets, sizeof(hash_entry_t));
63 hash_print_stats(hash_table_t *hash)
65 printf("hash_table: %s, %d bytes\n"
66 "\tn_buckets=%d, n_elements=%d, n_collisions=%d\n"
67 "\tmax_bucket_len=%d, n_used_buckets=%d, ave_bucket_len=%.2f\n"
68 "\tn_hits=%d, n_misses=%d\n",
70 hash->n_buckets*(int)sizeof(hash_entry_t),
76 (hash->n_used_buckets ?
77 ((float)hash->n_elements)/hash->n_used_buckets : 0.0f),
82 void hash_table_deinit(hash_table_t *hash)
88 /* free the reminaing entries */
89 for (i = 0; i < hash->n_buckets; i++) {
90 hash_entry_t *hash_entry = (hash->entries + i);
91 free (hash_entry->key);
92 /* skip the first entry as this is part of the array */
93 hash_entry = hash_entry->next;
96 hash_entry_t *old = hash_entry;
97 hash_entry = hash_entry->next;
103 free (hash->entries);
105 hash->entries = NULL;
109 void *hash_table_get(hash_table_t *hash, const char *key)
111 int ndx= hash_index(hash, key);
112 hash_entry_t *hash_entry = hash->entries + ndx;
117 if (strcmp(key, hash_entry->key) == 0) {
118 // opkg_message(NULL, OPKG_DEBUG, "Function: %s. Key found for '%s' \n", __FUNCTION__, key);
120 return hash_entry->data;
123 hash_entry = hash_entry->next;
129 int hash_table_insert(hash_table_t *hash, const char *key, void *value)
132 int ndx= hash_index(hash, key);
133 hash_entry_t *hash_entry = hash->entries + ndx;
134 if (hash_entry->key) {
135 if (strcmp(hash_entry->key, key) == 0) {
136 /* alread in table, update the value */
137 hash_entry->data = value;
141 * if this is a collision, we have to go to the end of the ll,
142 * then add a new entry
143 * before we can hook up the value
145 while (hash_entry->next) {
146 hash_entry = hash_entry->next;
147 if (strcmp(hash_entry->key, key) == 0) {
148 hash_entry->data = value;
153 hash_entry->next = xcalloc(1, sizeof(hash_entry_t));
154 hash_entry = hash_entry->next;
155 hash_entry->next = NULL;
157 hash->n_collisions++;
158 if (++bucket_len > hash->max_bucket_len)
159 hash->max_bucket_len = bucket_len;
162 hash->n_used_buckets++;
165 hash_entry->key = xstrdup(key);
166 hash_entry->data = value;
171 int hash_table_remove(hash_table_t *hash, const char *key)
173 int ndx= hash_index(hash, key);
174 hash_entry_t *hash_entry = hash->entries + ndx;
175 hash_entry_t *next_entry=NULL, *last_entry=NULL;
180 if (strcmp(key, hash_entry->key) == 0) {
181 free(hash_entry->key);
183 last_entry->next = hash_entry->next;
186 next_entry = hash_entry->next;
188 memmove(hash_entry, next_entry, sizeof(hash_entry_t));
191 memset(hash_entry, 0 , sizeof(hash_entry_t));
197 last_entry = hash_entry;
198 hash_entry = hash_entry->next;
203 void hash_table_foreach(hash_table_t *hash, void (*f)(const char *key, void *entry, void *data), void *data)
209 for (i = 0; i < hash->n_buckets; i++) {
210 hash_entry_t *hash_entry = (hash->entries + i);
212 if(hash_entry->key) {
213 f(hash_entry->key, hash_entry->data, data);
215 } while((hash_entry = hash_entry->next));