/[cvs]/eggdrop1.9/src/egglib/hash_table.c
ViewVC logotype

Contents of /eggdrop1.9/src/egglib/hash_table.c

Parent Directory Parent Directory | Revision Log Revision Log | View Revision Graph Revision Graph


Revision 1.4 - (show annotations) (download) (as text)
Sun Oct 28 13:30:35 2001 UTC (17 years, 11 months ago) by ite
Branch: MAIN
CVS Tags: HEAD
Changes since 1.3: +0 -0 lines
File MIME type: text/x-chdr
FILE REMOVED
Renamed src/adns, src/compat, src/egglib to lib/adns, lib/compat, lib/egglib respectively.

1 #include <stdio.h>
2 #include <string.h>
3
4 #include "hash_table.h"
5
6 hash_table_t *hash_table_create(hash_table_hash_alg alg, hash_table_cmp_alg cmp, int nrows, int flags)
7 {
8 hash_table_t *ht;
9 int size;
10
11 if (nrows <= 0) nrows = 13; /* Give them a small table to start with. */
12
13 size = sizeof(*ht) + (nrows-1) * sizeof(hash_table_entry_t);
14 ht = calloc(1, size);
15
16 if (alg) ht->hash = alg;
17 else {
18 if (flags & HASH_TABLE_STRINGS) ht->hash = my_string_hash;
19 else if (flags & HASH_TABLE_INTS) ht->hash = my_int_hash;
20 else ht->hash = my_mixed_hash;
21 }
22 if (cmp) ht->cmp = cmp;
23 else {
24 if (flags & HASH_TABLE_INTS) ht->cmp = my_int_cmp;
25 else ht->cmp = (hash_table_cmp_alg) strcmp;
26 }
27 ht->flags = flags;
28 ht->max_rows = nrows;
29 ht->rows_in_use = 0;
30 ht->collisions = 0;
31 return(ht);
32 }
33
34 int hash_table_destroy(hash_table_t *ht)
35 {
36 return(0);
37 }
38
39 int hash_table_insert(hash_table_t *ht, void *key, void *data)
40 {
41 int idx;
42 hash_table_entry_t *entry;
43
44 idx = (ht->hash)(key) % ht->max_rows;
45 entry = ht->entries+idx;
46
47 /* Is this slot empty? */
48 if (!entry->next) {
49 /* Add one to the row counter */
50 ht->rows_in_use++;
51 } else {
52 /* No.. append new entry to end */
53 while (entry->next != entry) entry = entry->next;
54 entry->next = (hash_table_entry_t *)malloc(sizeof(*entry));
55 entry = entry->next;
56
57 /* Add one to the collision counter */
58 ht->collisions++;
59 }
60 entry->key = key;
61 entry->data = data;
62 entry->next = entry;
63 return(0);
64 }
65
66 int hash_table_find(hash_table_t *ht, void *key, void *dataptr)
67 {
68 int idx;
69 hash_table_entry_t *entry, *last;
70
71 idx = (ht->hash)(key) % ht->max_rows;
72
73 last = (hash_table_entry_t *)0;
74 for (entry = ht->entries+idx; entry->next != last; entry = entry->next) {
75 if (!ht->cmp(key, entry->key)) {
76 *(void **)dataptr = entry->data;
77 return(0);
78 }
79 last = entry;
80 }
81 return(1);
82 }
83
84 int hash_table_delete(hash_table_t *ht, void *key)
85 {
86 int idx;
87 hash_table_entry_t *entry, *last;
88
89 idx = (ht->hash)(key) % ht->max_rows;
90
91 last = (hash_table_entry_t *)0;
92 for (entry = ht->entries+idx; entry->next != last; entry = entry->next) {
93 if (!ht->cmp(key, entry->key)) {
94 if (last) {
95 /* Do we need to update the previous one? */
96 if (entry == entry->next) last->next = last;
97 else last->next = entry->next;
98 free(entry);
99 }
100 else if (entry->next != entry) {
101 /* Ok, we are the first in the chain. */
102 /* Copy the next one onto us. */
103 entry->key = entry->next->key;
104 entry->data = entry->next->data;
105 last = entry->next;
106 if (entry->next->next == entry->next) entry->next = entry;
107 else entry->next = entry->next->next;
108 /* Now free the next one (we just copied). */
109 free(last);
110 }
111 else {
112 /* We are the only entry on this row. */
113 entry->next = (hash_table_entry_t *)0;
114 }
115 return(0);
116 }
117 last = entry;
118 }
119 return(1);
120 }
121
122 int hash_table_walk(hash_table_t *ht, hash_table_node_func callback, void *param)
123 {
124 hash_table_entry_t *entry, *last;
125 int i;
126
127 for (i = 0; i < ht->max_rows; i++) {
128 last = (hash_table_entry_t *)0;
129 for (entry = ht->entries+i; entry->next != last; entry = entry->next) {
130 callback(entry->key, entry->data, param);
131 last = entry;
132 }
133 }
134 }
135
136 static int my_int_cmp(const void *left, const void *right)
137 {
138 return((int) left - (int) right);
139 }
140
141 static unsigned int my_string_hash(void *key)
142 {
143 int hash, loop, keylen;
144 unsigned char *k;
145
146 #define HASHC hash = *k++ + 65599 * hash
147 hash = 0;
148 k = (unsigned char *)key;
149 keylen = strlen((char *)key);
150
151 loop = (keylen + 8 - 1) >> 3;
152 switch (keylen & (8 - 1)) {
153 case 0:
154 do {
155 HASHC;
156 case 7:
157 HASHC;
158 case 6:
159 HASHC;
160 case 5:
161 HASHC;
162 case 4:
163 HASHC;
164 case 3:
165 HASHC;
166 case 2:
167 HASHC;
168 case 1:
169 HASHC;
170 } while (--loop);
171 }
172 return(hash);
173 }
174
175 static unsigned int my_int_hash(void *key)
176 {
177 return((unsigned int)key);
178 }
179
180 static unsigned int my_mixed_hash (void *key)
181 {
182 unsigned char *k;
183 unsigned int hash;
184
185 k = (unsigned char *)key;
186 hash = 0;
187 while (*k) {
188 hash *= 16777619;
189 hash ^= *k++;
190 }
191 return(hash);
192 }

webmaster@eggheads.org
ViewVC Help
Powered by ViewVC 1.1.23