1 /* This file is part of the Project Athena Zephyr Notification System.
2 * It is one of the source files comprising zwgc, the Zephyr WindowGram
5 * Created by: Marc Horowitz <marc@athena.mit.edu>
9 * Copyright (c) 1989 by the Massachusetts Institute of Technology.
10 * For copying and distribution information, see the file
16 #if (!defined(lint) && !defined(SABER))
17 static const char rcsid_dictionary_c[] = "$Id$";
21 * dictionary - a module implementing a generic dictionary. That is,
22 * any type can be used for the values that keys are bound to.
23 * Keys are always strings.
27 * A dictionary is a set of bindings which bind values of some
28 * type (this type is the generic parameter of the dictionary) to
29 * strings. At most one value can be bound to any one string.
30 * The value that a string is bound to can be changed later.
31 * Bindings can also be deleted later. It is also possible to
32 * enumerate all of the bindings in a dictionary. Dictionarys
33 * are heap based and must be created & destroyed accordingly.
35 * Note: This module assumes that malloc NEVER returns 0 for reasonable
36 * requests. It is the users responsibility to either ensure that
37 * this happens or supply a version of malloc with error
40 * Dictionarys are mutable.
44 * A standard chaining hash table is used to implement dictionarys.
45 * Each dictionary has an associated size (# of slots), allowing
46 * different size dictionaries as needed.
49 #include "TYPE_T_dictionary.h"
50 #include "new_string.h"
51 #include "new_memory.h"
58 * TYPE_T_dictionary TYPE_T_dictionary_Create(int size):
60 * Effects: Returns a new empty dictionary containing no bindings.
61 * The returned dictionary must be destroyed using
62 * TYPE_T_dictionary_Destroy. Size is a time vs space
63 * parameter. For this implementation, space used is
64 * proportional to size and time used is proportional
65 * to number of bindings divided by size. It is preferable
66 * that size is a prime number.
70 TYPE_T_dictionary_Create(int size)
73 TYPE_T_dictionary result;
75 result = (TYPE_T_dictionary)malloc(sizeof(struct _TYPE_T_dictionary));
77 result->slots = (TYPE_T_dictionary_binding **)malloc(
78 size*sizeof(TYPE_T_dictionary_binding *));
80 for (i=0; i<size; i++)
81 result->slots[i] = NULL;
87 * void TYPE_T_dictionary_Destroy(TYPE_T_dictionary d):
88 * Requires: d is a non-destroyed TYPE_T_dictionary
90 * Effects: Destroys dictionary d freeing up the space it consumes.
91 * Dictionary d should never be referenced again. Note that
92 * free is NOT called on the values of the bindings. If
93 * this is needed, the client must do this first using
94 * TYPE_T_dictionary_Enumerate.
98 TYPE_T_dictionary_Destroy(TYPE_T_dictionary d)
101 TYPE_T_dictionary_binding *binding_ptr, *new_binding_ptr;
103 for (i=0; i<d->size; i++) {
104 binding_ptr = d->slots[i];
105 while (binding_ptr) {
106 new_binding_ptr = binding_ptr->next;
107 free(binding_ptr->key);
109 binding_ptr = new_binding_ptr;
117 * void TYPE_T_dictionary_Enumerate(TYPE_T_dictionary d; void (*proc)()):
118 * Requires: proc is a void procedure taking 1 argument, a
119 * TYPE_T_dictionary_binding pointer, which does not
120 * make any calls using dictionary d.
121 * Effects: Calls proc once with each binding in dictionary d.
122 * Order of bindings passed is undefined. Note that
123 * only the value field of the binding should be considered
127 void TYPE_T_dictionary_Enumerate(TYPE_T_dictionary d,
128 void (*proc)(TYPE_T_dictionary_binding *))
131 TYPE_T_dictionary_binding *binding_ptr;
133 for (i=0; i<d->size; i++) {
134 binding_ptr = d->slots[i];
135 while (binding_ptr) {
137 binding_ptr = binding_ptr->next;
145 * unsigned int dictionary__hash(char *s):
146 * Effects: Hashs s to an unsigned integer. This number mod the
147 * hash table size is supposed to roughly evenly distribute
148 * keys over the table's slots.
152 dictionary__hash(char *s)
154 unsigned int result = 0;
169 * TYPE_T_dictionary_binding *TYPE_T_dictionary_Lookup(TYPE_T_dictionary d,
171 * Effects: If key is not bound in d, returns 0. Othersize,
172 * returns a pointer to the binding that binds key.
173 * Note the access restrictions on bindings...
176 TYPE_T_dictionary_binding *
177 TYPE_T_dictionary_Lookup(TYPE_T_dictionary d,
180 TYPE_T_dictionary_binding *binding_ptr;
182 binding_ptr = d->slots[dictionary__hash(key)%(d->size)];
183 while (binding_ptr) {
184 if (string_Eq(key, binding_ptr->key))
186 binding_ptr = binding_ptr->next;
193 * TYPE_T_dictionary_binding *TYPE_T_dictionary_Define(TYPE_T_dictionary d,
195 * int *already_existed):
197 * Effects: If key is bound in d, returns a pointer to the binding
198 * that binds key. Otherwise, adds a binding of key to
199 * d and returns its address. If already_existed is non-zero
200 * then *already_existed is set to 0 if key was not
201 * previously bound in d and 1 otherwise.
202 * Note the access restrictions on bindings... Note also
203 * that the value that key is bounded to if a binding is
204 * created is undefined. The caller should set the value
208 TYPE_T_dictionary_binding *
209 TYPE_T_dictionary_Define(TYPE_T_dictionary d,
211 int *already_existed)
213 TYPE_T_dictionary_binding **ptr_to_the_slot, *binding_ptr;
215 ptr_to_the_slot = &(d->slots[dictionary__hash(key)%(d->size)]);
217 binding_ptr = *ptr_to_the_slot;
218 while (binding_ptr) {
219 if (string_Eq(binding_ptr->key, key)) {
221 *already_existed = 1;
224 binding_ptr = binding_ptr->next;
228 *already_existed = 0;
229 binding_ptr = (TYPE_T_dictionary_binding *)malloc(
230 sizeof(TYPE_T_dictionary_binding));
231 binding_ptr->next = *ptr_to_the_slot;
232 binding_ptr->key = string_Copy(key);
233 *ptr_to_the_slot = binding_ptr;
238 * void TYPE_T_dictionary_Delete(TYPE_T_dictionary d,
239 * TYPE_T_dictionary_binding *b):
240 * Requires: *b is a binding in d.
242 * Effects: Removes the binding *b from d. Note that if
243 * b->value needs to be freed, it should be freed
244 * before making this call.
247 void TYPE_T_dictionary_Delete(TYPE_T_dictionary d,
248 TYPE_T_dictionary_binding *b)
250 TYPE_T_dictionary_binding **ptr_to_binding_ptr;
252 ptr_to_binding_ptr = &(d->slots[dictionary__hash(b->key)%(d->size)]);
254 while (*ptr_to_binding_ptr != b)
255 ptr_to_binding_ptr = &((*ptr_to_binding_ptr)->next);
257 *ptr_to_binding_ptr = b->next;