1 /*
2 LICENSE INFORMATION:
3 This program is free software; you can redistribute it and/or
4 modify it under the terms of the GNU General Public
5 License as published by the Free Software Foundation; either
6 version 2 of the License, or (at your option) any later version.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 General Public License for more details.
12
13 You should have received a copy of the GNU General Public
14 License along with this program; if not, write to the Free Software
15 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16 Copyright (c) 2002 Bruno T. C. de Oliveira
17
18 INFORMA��ES DE LICEN�A:
19 Este programa � um software de livre distribui��o; voc� pode
20 redistribu�-lo e/ou modific�-lo sob os termos da GNU General
21 Public License, conforme publicado pela Free Software Foundation,
22 pela vers�o 2 da licen�a ou qualquer vers�o posterior.
23
24 Este programa � distribu�do na esperan�a de que ele ser� �til
25 aos seus usu�rios, por�m, SEM QUAISQUER GARANTIAS; sem sequer
26 a garantia impl�cita de COMERCIABILIDADE ou DE ADEQUA��O A
27 QUALQUER FINALIDADE ESPEC�FICA. Consulte a GNU General Public
28 License para obter mais detalhes (uma c�pia acompanha este
29 programa, armazenada no arquivo COPYING).
30 */
31
32 #include "hashdict.h"
33 #include "util.h"
34 #include <stdlib.h>
35 #include <string.h>
36 #include <stdio.h>
37 #define DEFAULT_BUCKET_COUNT 30
38
39 struct Node_ { /* each node in the linked lists */
40 char *key;
41 const void *value;
42
43 struct Node_ *next;
44 };
45 typedef struct Node_ Node;
46
47 struct HashDict_ {
48 int bucketcount; /* how many buckets in this dictionary */
49 Node *bucketheads;/* array of head nodes, one for each bucket.
50 * The data in the head node means nothing. The linked
51 * list begins with the node that head->next points to */
52 void (*value_destroyer)(void*); /* function called to destroy values.
53 * If NULL, no function is called */
54 };
55
56 /* declaration of private functions -----------------------------*/
57 static void _destroy_node(HashDict *hd, Node* n);
58 static int _which_bucket(const char *key, int bucketcount);
59 static Node* _node_lookup(HashDict *hd,
60 const char *key); /* warning: this function has counter-intuitive
61 (but useful) beheavior (q.v.) */
62 /* --------------------------------------------------------------*/
63
hashdict_create_ex(int bucketcount,void (* value_destroyer)(void *))64 HashDict* hashdict_create_ex(int bucketcount, void (*value_destroyer)(void*)) {
65 HashDict *hd = zalloc(sizeof(struct HashDict_));
66 hd->bucketcount = bucketcount;
67 hd->value_destroyer = value_destroyer;
68 hd->bucketheads = zalloc(sizeof(Node) * bucketcount);
69
70 return hd;
71 }
72
hashdict_create(void)73 HashDict* hashdict_create(void) {
74 return hashdict_create_ex(DEFAULT_BUCKET_COUNT, 0);
75 }
76
hashdict_destroy(HashDict * hd)77 void hashdict_destroy(HashDict* hd) {
78 int i; Node *n;
79 if (!hd) return;
80
81 /* destroy all nodes */
82 for (i = 0; i < hd->bucketcount; i++) {
83 while ( (n = hd->bucketheads[i].next) ) {
84 /* delete node n */
85 hd->bucketheads[i].next = n->next;
86 _destroy_node(hd, n);
87 }
88 }
89
90 free(hd->bucketheads);
91 free(hd);
92 }
93
hashdict_get(HashDict * hd,const char * key)94 void* hashdict_get(HashDict *hd, const char *key) {
95 Node *n = _node_lookup(hd, key);
96
97 /* be mindful that _node_lookup returns the node BEFORE
98 the one we are looking for */
99 return (void*) (n->next ? n->next->value : 0);
100 }
101
hashdict_set(HashDict * hd,const char * key,const void * value)102 void hashdict_set(HashDict *hd, const char *key, const void *value) {
103 Node *n;
104 if (!value) { hashdict_unset(hd, key); return; }
105
106 n = _node_lookup(hd, key);
107 if (n->next) {
108 /* node already exists: replace value */
109 if (hd->value_destroyer) (*hd->value_destroyer)((void*)n->next->value);
110 n->next->value = value;
111 }
112 else {
113 /* does not exist yet: append to list */
114 Node *newnode = zalloc(sizeof(Node));
115 newnode->key = sstrdup(key);
116 newnode->value = value;
117 newnode->next = NULL;
118 n->next = newnode;
119 }
120 }
121
hashdict_unset(HashDict * hd,const char * key)122 bool hashdict_unset(HashDict *hd, const char *key) {
123 Node *n = _node_lookup(hd, key);
124 if (n->next) {
125 _destroy_node(hd, n->next);
126 n->next = n->next->next;
127 return true; /* found and deleted */
128 }
129 return false; /* not found */
130 }
131
hashdict_write(HashDict * hd,FILE * f,void (* value_writer)(void *,FILE *))132 void hashdict_write(HashDict *hd, FILE *f, void (*value_writer)(void*, FILE*)) {
133 /* TODO */
134 }
135
hashdict_read(HashDict * hd,FILE * f,void * (* valuereader)(FILE *))136 HashDict* hashdict_read(HashDict *hd, FILE *f, void* (*valuereader)(FILE*)) {
137 /* TODO */
138 return NULL;
139 }
140
hashdict_it_start(HashDict * hd)141 HashDictIt hashdict_it_start(HashDict *hd) {
142 HashDictIt it;
143
144 /* put iterator before beginning */
145 it.pastend = false;
146 it.key = it.value = NULL;
147 it.dict = hd;
148 it.nextbucket = 0;
149 it.nextnode = NULL;
150
151 return it;
152 }
153
hashdict_it_advance(HashDictIt * hdi)154 bool hashdict_it_advance(HashDictIt *hdi) {
155 if (hdi->pastend) return false; /* already at the end */
156
157 if (hdi->nextnode) {
158 hdi->key = ((Node*)hdi->nextnode)->key;
159 hdi->value = ((Node*)hdi->nextnode)->value;
160 hdi->nextnode = ((Node*)hdi->nextnode)->next;
161 }
162 else {
163 /* go to next nonempty bucket */
164 HashDict *hd = hdi->dict;
165 int i = hdi->nextbucket;
166 while (i < hd->bucketcount && !hd->bucketheads[i].next) i++;
167
168 if (i < hd->bucketcount) {
169 /* we know hd->buckethead[i].next is not NULL */
170 hdi->key = hd->bucketheads[i].next->key;
171 hdi->value = hd->bucketheads[i].next->value;
172 hdi->nextbucket = i+1;
173 hdi->nextnode = hd->bucketheads[i].next->next;
174 }
175 else {
176 /* passed the end */
177 hdi->key = hdi->value = NULL; /* for safety */
178 hdi->pastend = true;
179 return false;
180 }
181 }
182
183 return true;
184 }
185
186 /* private functions ----------------------------------------------------- */
_node_lookup(HashDict * hd,const char * key)187 static Node* _node_lookup(HashDict *hd, const char *key) {
188 /* ATTENTION: return value is not the node you are looking for;
189 * rather, it is the node BEFORE it. This is useful for a variety
190 * of reasons, including node deletion and appending */
191
192 /* returns ptr to node n such that n->next->key is equal to <key>.
193 * If not found, returns the last node in the bucket that <key>
194 * hashes into. (in this case, the 'next' field of the return
195 * value will be NULL, since it is the last node in a list). */
196 Node *n = &(hd->bucketheads[_which_bucket(key, hd->bucketcount)]);
197 while (n->next && strcmp(n->next->key, key)) n = n->next;
198 return n;
199 }
200
_destroy_node(HashDict * hd,Node * n)201 static void _destroy_node(HashDict *hd, Node* n) {
202 if (n) {
203 if (hd->value_destroyer && n->value)
204 (*hd->value_destroyer)((void*)n->value);
205 zfree(&n->key);
206 free(n);
207 }
208 }
209
_which_bucket(const char * key,int bucketcount)210 static int _which_bucket(const char *key, int bucketcount) {
211 /* this function computes the hashcode of the given key
212 * in a dictionary with <bucketcount> buckets. If str is non-NULL
213 * and bucketcount > 0, the return value is guaranteed to be
214 * nonnegative and smaller than bucketcount. */
215
216 /* FIXME: write a serious hash function. This one is laughable. */
217
218 int x = 0;
219 while (*key) x += *(key++);
220 return x % bucketcount;
221 }
222
223