1 /***********************************************************************/
2 /* Open Visualization Data Explorer */
3 /* (C) Copyright IBM Corp. 1989,1999 */
4 /* ALL RIGHTS RESERVED */
5 /* This code licensed under the */
6 /* "IBM PUBLIC LICENSE - Open Visualization Data Explorer" */
7 /***********************************************************************/
8
9 #include <dxconfig.h>
10 #include "../base/defines.h"
11
12
13
14 #include "dict.h"
15
16 /*
17 Routines: dicttbl_init, DictInit, DictDelete, DictInsert, DictFind
18 DictSize
19
20 dicttbl_init()
21 Purpose : Initialize a dictionary table.
22 Output : A pointer to a newly allocated DictTbl returned on success.
23 0 returned on failure when can't allocate hash array.
24
25
26 DictDelete(dict,key)
27 Purpose : Remove user data indicated by key.
28 Output : a pointer equal to the last value of 'def'inserted with key
29 if the item is found. If the key'ed item was inserted with
30 a deleter then the (*deleter)(def) will be called if the
31 item is found.
32 0 if item is not found.
33
34 DictInsert(dict,key,def, deleter)
35 Purpose : Add a definition defined by key to the dictionary.
36 if 'deleter' is non-null it will be called as (*deleter)(def)
37 when the item is removed from the dictionary, or the
38 dictionary itself is deleted.
39 Output : None
40
41 DictFind(dict,key)
42 Purpose : Lookup a key in the specified dictionary.
43 Output : a pointer equal to the last value of 'def'inserted with key
44 if item is found.
45 0 if item is not found.
46
47 DictSize(dict)
48 Purpose : Find size of given dictionary.
49 Output : int value equal to number of definitions in dictionary.
50
51 Notes : Keys should be unique within a table. The last definition
52 inserted with any key is considered the current active
53 definition. This provides for the ability to stack
54 definitions.
55
56 Warnings: The data at 'datap' is never copied into the hash table.
57 Therefore, if the user alters the data at datap after
58 inserting it, the data will still be on the table but
59 will not be retrievable.
60 */
61 #include <string.h>
62 #include "dict.h"
63 #if defined(MSDOS) || defined(sun4)
64 # include <malloc.h>
65 #endif
66
67 #ifndef NULL
68 #define NULL 0
69 #endif
70
71 struct _dictitem_t {
72 struct _dictitem_t *nexti;
73 char *key;
74 void *def;
75 void (*deleter)(void*);
76 };
77
78 #define HASH_SIZE 32
79
_dict_hash(const char * str)80 static int _dict_hash(const char *str)
81 {
82 char c, *p = (char*)str;
83 int key, i, sum = 0;
84
85 for (i=0 ; (c = *p) && i<12 ; i++, p++)
86 sum = sum + c;
87
88 key = sum & (HASH_SIZE -1);
89
90 return key;
91
92 }
93
DeleteDictItem(DictItem * di)94 static void DeleteDictItem(DictItem *di)
95 {
96 if (di->deleter)
97 (*di->deleter)(di->def);
98
99 if (di->key)
100 FREE(di->key);
101
102 FREE(di);
103 }
NewDictItem(const char * key,const void * def,void (* deleter)(void *))104 static DictItem *NewDictItem(const char *key, const void *def,
105 void (*deleter)(void*))
106 {
107 DictItem *di = (DictItem*)MALLOC(sizeof(DictItem));
108
109 if (!di)
110 return NULL;
111 di->nexti = NULL;
112 di->key = strdup(key);
113 di->def = (void*)def;
114 di->deleter = deleter;
115 return di;
116 }
117
DeleteDictionary(_Dictionary * d)118 void DeleteDictionary(_Dictionary *d)
119 {
120 int i ;
121
122 for (i=0 ; i<d->size ; i++) {
123 DictItem *di = d->harr[i];
124 if (di) {
125 DictItem *next;
126 do {
127 next = di->nexti;
128 DeleteDictItem(di);
129 } while (di == next);
130 }
131 }
132 FREE(d->harr);
133 FREE(d);
134 }
NewDictionary()135 _Dictionary *NewDictionary()
136 {
137 int i;
138 _Dictionary *dict;
139
140 dict = (_Dictionary*)MALLOC(sizeof(_Dictionary));
141 if (!dict)
142 return NULL;
143 if (!(dict->harr = (DictItem**)MALLOC(HASH_SIZE*sizeof(DictItem*))))
144 return NULL;
145 dict->num_in_dict = 0;
146 dict->size = HASH_SIZE;
147 for (i=0 ; i<HASH_SIZE; i++)
148 dict->harr[i] = (DictItem*)NULL;
149
150 return(dict);
151 }
152
DictDelete(dictionary,key)153 int DictDelete(dictionary,key)
154 _Dictionary *dictionary;
155 const char *key;
156 {
157 DictItem *dlist=NULL,*next=NULL;
158 int found=0;
159 int bucket;
160
161 bucket = _dict_hash(key);
162 if (dlist == dictionary->harr[bucket]) {
163 found = !strcmp(dlist->key, key);
164 if (found) { /* First item on list */
165 dictionary->harr[bucket] = dlist->nexti;
166 }
167 else { /* Not first item on list */
168 while (dlist->nexti && !found) {
169 found = !strcmp(dlist->nexti->key,key);
170 if (!found)
171 dlist = dlist->nexti;
172 else {
173 if (next == dlist->nexti) {
174 dlist->nexti = next->nexti;
175 }
176 else
177 dlist->nexti=(DictItem*)0;
178 dlist = next;
179 dictionary->num_in_dict -= 1;
180 }
181 }
182 }
183 DeleteDictItem(dlist);
184 }
185 #ifdef debug
186 printf("delete: key = %d, found = %d\n",key,found);
187 #endif
188 return(found);
189 }
190
DictInsert(dictionary,key,def,deleter)191 int DictInsert(dictionary,key,def, deleter)
192 _Dictionary *dictionary;
193 const char *key;
194 void *def;
195 void (*deleter)(void*);
196 {
197 DictItem *dlist;
198 int bucket;
199
200 dlist = NewDictItem(key,def,deleter);
201 if (!dlist)
202 return 0;
203 bucket = _dict_hash(key);
204 dlist->nexti = dictionary->harr[bucket];
205 dictionary->harr[bucket] = dlist;
206 dictionary->num_in_dict += 1;
207 return 1;
208 }
209
DictFind(dictionary,key)210 void *DictFind(dictionary,key)
211 _Dictionary *dictionary;
212 const char *key;
213 {
214 DictItem *dlist;
215 int found=0;
216
217 dlist = dictionary->harr[_dict_hash(key)];
218 while (dlist && !found) {
219 found = !strcmp(dlist->key,key);
220 if (!found)
221 dlist = dlist->nexti;
222 else
223 return(dlist->def);
224 }
225 return(0);
226 }
227