zephyr/zwgc/dictionary.c

   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
   3  * client.
   4  *
   5  *      Created by:     Marc Horowitz <marc@athena.mit.edu>
   6  *
   7  *      $Id: dictionary.c,v 1.2 1999/01/22 23:20:14 ghudson Exp $
   8  *
   9  *      Copyright (c) 1989 by the Massachusetts Institute of Technology.
  10  *      For copying and distribution information, see the file
  11  *      "mit-copyright.h".
  12  */
  13
  14 #include <sysdep.h>
  15
  16 #if (!defined(lint) && !defined(SABER))
  17 static const char rcsid_dictionary_c[] = "$Id: dictionary.c,v 1.2 1999/01/22 23:20:14 ghudson Exp $";
  18 #endif
  19
  20 /*
  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.
  24  *
  25  * Overview:
  26  *
  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.
  34  *
  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
  38  *          handling.
  39  *
  40  *    Dictionarys are mutable.
  41  *
  42  * Implementation:
  43  *
  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.
  47  */
  48
  49 #include "TYPE_T_dictionary.h"
  50 #include "new_string.h"
  51 #include "new_memory.h"
  52
  53 #ifndef NULL
  54 #define NULL 0
  55 #endif
  56
  57 /*
  58  *    TYPE_T_dictionary TYPE_T_dictionary_Create(int size):
  59  *        Requires: size > 0
  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.
  67  */
  68
  69 TYPE_T_dictionary TYPE_T_dictionary_Create(size)
  70      int size;
  71 {
  72     int i;
  73     TYPE_T_dictionary result;
  74
  75     result = (TYPE_T_dictionary)malloc(sizeof(struct _TYPE_T_dictionary));
  76     result->size = size;
  77     result->slots = (TYPE_T_dictionary_binding **)malloc(
  78                      size*sizeof(TYPE_T_dictionary_binding *));
  79
  80     for (i=0; i<size; i++)
  81       result->slots[i] = NULL;
  82
  83     return(result);
  84 }
  85
  86 /*
  87  *    void TYPE_T_dictionary_Destroy(TYPE_T_dictionary d):
  88  *        Requires: d is a non-destroyed TYPE_T_dictionary
  89  *        Modifies: d
  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.
  95  */
  96
  97 void TYPE_T_dictionary_Destroy(d)
  98      TYPE_T_dictionary d;
  99 {
 100     int i;
 101     TYPE_T_dictionary_binding *binding_ptr, *new_binding_ptr;
 102
 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);
 108             free(binding_ptr);
 109             binding_ptr = new_binding_ptr;
 110         }
 111     }
 112     free(d->slots);
 113     free(d);
 114 }
 115
 116 /*
 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
 124  *                 writable by proc.
 125  */
 126
 127 void TYPE_T_dictionary_Enumerate(d, proc)
 128      TYPE_T_dictionary d;
 129      void (*proc)(/* TYPE_T_dictionary_binding *b */);
 130 {
 131     int i;
 132     TYPE_T_dictionary_binding *binding_ptr;
 133
 134     for (i=0; i<d->size; i++) {
 135         binding_ptr = d->slots[i];
 136         while (binding_ptr) {
 137             proc(binding_ptr);
 138             binding_ptr = binding_ptr->next;
 139         }
 140     }
 141 }
 142
 143 /*
 144  *  Private routine:
 145  *
 146  *    unsigned int dictionary__hash(char *s):
 147  *        Effects: Hashs s to an unsigned integer.  This number mod the
 148  *                 hash table size is supposed to roughly evenly distribute
 149  *                 keys over the table's slots.
 150  */
 151
 152 static unsigned int dictionary__hash(s)
 153      char *s;
 154 {
 155     unsigned int result = 0;
 156
 157     if (!s)
 158       return(result);
 159
 160     while (s[0]) {
 161         result <<= 1;
 162         result += s[0];
 163         s++;
 164     }
 165
 166     return(result);
 167 }
 168
 169 /*
 170  *    TYPE_T_dictionary_binding *TYPE_T_dictionary_Lookup(TYPE_T_dictionary d,
 171  *                                                        char *key):
 172  *        Effects: If key is not bound in d, returns 0.  Othersize,
 173  *                 returns a pointer to the binding that binds key.
 174  *                 Note the access restrictions on bindings...
 175  */
 176
 177 TYPE_T_dictionary_binding *TYPE_T_dictionary_Lookup(d, key)
 178      TYPE_T_dictionary d;
 179      char *key;
 180 {
 181     TYPE_T_dictionary_binding *binding_ptr;
 182
 183     binding_ptr = d->slots[dictionary__hash(key)%(d->size)];
 184     while (binding_ptr) {
 185         if (string_Eq(key, binding_ptr->key))
 186           return(binding_ptr);
 187         binding_ptr = binding_ptr->next;
 188     }
 189
 190     return(NULL);
 191 }
 192
 193 /*
 194  *    TYPE_T_dictionary_binding *TYPE_T_dictionary_Define(TYPE_T_dictionary d,
 195  *                                            char *key,
 196  *                                            int *already_existed):
 197  *        Modifies: d
 198  *        Effects: If key is bound in d, returns a pointer to the binding
 199  *                 that binds key.  Otherwise, adds a binding of key to
 200  *                 d and returns its address.  If already_existed is non-zero
 201  *                 then *already_existed is set to 0 if key was not
 202  *                 previously bound in d and 1 otherwise.
 203  *                 Note the access restrictions on bindings...  Note also
 204  *                 that the value that key is bounded to if a binding is
 205  *                 created is undefined.  The caller should set the value
 206  *                 in this case.
 207  */
 208
 209 TYPE_T_dictionary_binding *TYPE_T_dictionary_Define(d, key, already_existed)
 210      TYPE_T_dictionary d;
 211      char *key;
 212      int *already_existed;
 213 {
 214     TYPE_T_dictionary_binding **ptr_to_the_slot, *binding_ptr;
 215
 216     ptr_to_the_slot = &(d->slots[dictionary__hash(key)%(d->size)]);
 217
 218     binding_ptr = *ptr_to_the_slot;
 219     while (binding_ptr) {
 220         if (string_Eq(binding_ptr->key, key)) {
 221             if (already_existed)
 222               *already_existed = 1;
 223             return(binding_ptr);
 224         }
 225         binding_ptr = binding_ptr->next;
 226     }
 227
 228     if (already_existed)
 229       *already_existed = 0;
 230     binding_ptr = (TYPE_T_dictionary_binding *)malloc(
 231                                         sizeof(TYPE_T_dictionary_binding));
 232     binding_ptr->next = *ptr_to_the_slot;
 233     binding_ptr->key = string_Copy(key);
 234     *ptr_to_the_slot = binding_ptr;
 235     return(binding_ptr);
 236 }
 237
 238 /*
 239  *    void TYPE_T_dictionary_Delete(TYPE_T_dictionary d,
 240  *                                  TYPE_T_dictionary_binding *b):
 241  *        Requires: *b is a binding in d.
 242  *        Modifies: d
 243  *        Effects: Removes the binding *b from d.  Note that if
 244  *                 b->value needs to be freed, it should be freed
 245  *                 before making this call.
 246  */
 247
 248 void TYPE_T_dictionary_Delete(d, b)
 249      TYPE_T_dictionary d;
 250      TYPE_T_dictionary_binding *b;
 251 {
 252     TYPE_T_dictionary_binding **ptr_to_binding_ptr;
 253
 254     ptr_to_binding_ptr = &(d->slots[dictionary__hash(b->key)%(d->size)]);
 255
 256     while (*ptr_to_binding_ptr != b)
 257       ptr_to_binding_ptr = &((*ptr_to_binding_ptr)->next);
 258
 259     *ptr_to_binding_ptr = b->next;
 260     free(b->key);
 261     free(b);
 262 }