1 /* hash.c - hash tables for opkg
2
3 Steven M. Ayer, Jamey Hicks
4
5 Copyright (C) 2002 Compaq Computer Corporation
6
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.
11
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.
16 */
17
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include "hash_table.h"
22 #include "opkg_message.h"
23 #include "libbb/libbb.h"
24
djb2_hash(const unsigned char * str)25 static unsigned long djb2_hash(const unsigned char *str)
26 {
27 unsigned long hash = 5381;
28 int c;
29 while ((c = *str++))
30 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
31 return hash;
32 }
33
hash_index(hash_table_t * hash,const char * key)34 static int hash_index(hash_table_t * hash, const char *key)
35 {
36 return djb2_hash((const unsigned char *)key) % hash->n_buckets;
37 }
38
39 /*
40 * this is an open table keyed by strings
41 */
hash_table_init(const char * name,hash_table_t * hash,int len)42 void hash_table_init(const char *name, hash_table_t * hash, int len)
43 {
44 if (hash->entries != NULL) {
45 opkg_msg(ERROR, "Internal error: non empty hash table.\n");
46 return;
47 }
48
49 memset(hash, 0, sizeof(hash_table_t));
50
51 hash->name = name;
52 hash->n_buckets = len;
53 hash->entries = xcalloc(hash->n_buckets, sizeof(hash_entry_t));
54 }
55
hash_print_stats(hash_table_t * hash)56 void hash_print_stats(hash_table_t * hash)
57 {
58 printf("hash_table: %s, %d bytes\n"
59 "\tn_buckets=%d, n_elements=%d, n_collisions=%d\n"
60 "\tmax_bucket_len=%d, n_used_buckets=%d, ave_bucket_len=%.2f\n"
61 "\tn_hits=%d, n_misses=%d\n",
62 hash->name,
63 hash->n_buckets * (int)sizeof(hash_entry_t),
64 hash->n_buckets,
65 hash->n_elements,
66 hash->n_collisions,
67 hash->max_bucket_len,
68 hash->n_used_buckets,
69 (hash->n_used_buckets ?
70 ((float)hash->n_elements) / hash->n_used_buckets : 0.0f),
71 hash->n_hits, hash->n_misses);
72 }
73
hash_table_deinit(hash_table_t * hash)74 void hash_table_deinit(hash_table_t * hash)
75 {
76 int i;
77 if (!hash)
78 return;
79
80 /* free the reminaing entries */
81 for (i = 0; i < hash->n_buckets; i++) {
82 hash_entry_t *hash_entry = (hash->entries + i);
83 free(hash_entry->key);
84 /* skip the first entry as this is part of the array */
85 hash_entry = hash_entry->next;
86 while (hash_entry) {
87 hash_entry_t *old = hash_entry;
88 hash_entry = hash_entry->next;
89 free(old->key);
90 free(old);
91 }
92 }
93
94 free(hash->entries);
95
96 hash->entries = NULL;
97 hash->n_buckets = 0;
98 }
99
hash_table_get(hash_table_t * hash,const char * key)100 void *hash_table_get(hash_table_t * hash, const char *key)
101 {
102 int ndx = hash_index(hash, key);
103 hash_entry_t *hash_entry = hash->entries + ndx;
104 while (hash_entry) {
105 if (hash_entry->key) {
106 if (strcmp(key, hash_entry->key) == 0) {
107 hash->n_hits++;
108 return hash_entry->data;
109 }
110 }
111 hash_entry = hash_entry->next;
112 }
113 hash->n_misses++;
114 return NULL;
115 }
116
hash_table_insert(hash_table_t * hash,const char * key,void * value)117 int hash_table_insert(hash_table_t * hash, const char *key, void *value)
118 {
119 int bucket_len = 0;
120 int ndx = hash_index(hash, key);
121 hash_entry_t *hash_entry = hash->entries + ndx;
122 if (hash_entry->key) {
123 if (strcmp(hash_entry->key, key) == 0) {
124 /* alread in table, update the value */
125 hash_entry->data = value;
126 return 0;
127 } else {
128 /*
129 * if this is a collision, we have to go to the end of the ll,
130 * then add a new entry
131 * before we can hook up the value
132 */
133 while (hash_entry->next) {
134 hash_entry = hash_entry->next;
135 if (strcmp(hash_entry->key, key) == 0) {
136 hash_entry->data = value;
137 return 0;
138 }
139 bucket_len++;
140 }
141 hash_entry->next = xcalloc(1, sizeof(hash_entry_t));
142 hash_entry = hash_entry->next;
143 hash_entry->next = NULL;
144
145 hash->n_collisions++;
146 if (++bucket_len > hash->max_bucket_len)
147 hash->max_bucket_len = bucket_len;
148 }
149 } else
150 hash->n_used_buckets++;
151
152 hash->n_elements++;
153 hash_entry->key = xstrdup(key);
154 hash_entry->data = value;
155
156 return 0;
157 }
158
hash_table_remove(hash_table_t * hash,const char * key)159 int hash_table_remove(hash_table_t * hash, const char *key)
160 {
161 int ndx = hash_index(hash, key);
162 hash_entry_t *hash_entry = hash->entries + ndx;
163 hash_entry_t *next_entry = NULL, *last_entry = NULL;
164 while (hash_entry) {
165 if (hash_entry->key) {
166 if (strcmp(key, hash_entry->key) == 0) {
167 free(hash_entry->key);
168 if (last_entry) {
169 last_entry->next = hash_entry->next;
170 free(hash_entry);
171 } else {
172 next_entry = hash_entry->next;
173 if (next_entry) {
174 memmove(hash_entry, next_entry,
175 sizeof(hash_entry_t));
176 free(next_entry);
177 } else {
178 memset(hash_entry, 0,
179 sizeof(hash_entry_t));
180 }
181 }
182 return 1;
183 }
184 }
185 last_entry = hash_entry;
186 hash_entry = hash_entry->next;
187 }
188 return 0;
189 }
190
hash_table_foreach(hash_table_t * hash,void (* f)(const char * key,void * entry,void * data),void * data)191 void hash_table_foreach(hash_table_t * hash,
192 void (*f) (const char *key, void *entry, void *data),
193 void *data)
194 {
195 int i;
196 if (!hash || !f)
197 return;
198
199 for (i = 0; i < hash->n_buckets; i++) {
200 hash_entry_t *hash_entry = (hash->entries + i);
201 do {
202 if (hash_entry->key) {
203 f(hash_entry->key, hash_entry->data, data);
204 }
205 } while ((hash_entry = hash_entry->next));
206 }
207 }
208