Initial revision

5 files changed, 566 insertions, 0 deletions

diff --git a/zwgc/Dictionary/dictionary.c b/zwgc/Dictionary/dictionary.c
new file mode 100644
index 0000000..f9962f3
--- /dev/null
+++ b/zwgc/Dictionary/dictionary.c
@@ -0,0 +1,261 @@
+/* This file is part of the Project Athena Zephyr Notification System.
+ * It is one of the source files comprising zwgc, the Zephyr WindowGram
+ * client.
+ *
+ *      Created by:     Marc Horowitz <marc@athena.mit.edu>
+ *
+ *      $Source$
+ *      $Author$
+ *
+ *      Copyright (c) 1989 by the Massachusetts Institute of Technology.
+ *      For copying and distribution information, see the file
+ *      "mit-copyright.h".
+ */
+
+#if (!defined(lint) && !defined(SABER))
+static char rcsid_dictionary_c[] = "$Id$";
+#endif
+
+/*
+ * dictionary - a module implementing a generic dictionary.  That is,
+ *              any type can be used for the values that keys are bound to.
+ *              Keys are always strings.
+ *
+ * Overview:
+ *
+ *        A dictionary is a set of bindings which bind values of some
+ *    type (this type is the generic parameter of the dictionary) to
+ *    strings.  At most one value can be bound to any one string.
+ *    The value that a string is bound to can be changed later.
+ *    Bindings can also be deleted later.  It is also possible to
+ *    enumerate all of the bindings in a dictionary.  Dictionarys
+ *    are heap based and must be created & destroyed accordingly.
+ *
+ *    Note: This module assumes that malloc NEVER returns 0 for reasonable
+ *          requests.  It is the users responsibility to either ensure that
+ *          this happens or supply a version of malloc with error
+ *          handling.
+ *
+ *    Dictionarys are mutable.
+ *
+ * Implementation:
+ *
+ *        A standard chaining hash table is used to implement dictionarys.
+ *    Each dictionary has an associated size (# of slots), allowing
+ *    different size dictionaries as needed.
+ */
+
+#include "TYPE_T_dictionary.h"
+#include "new_string.h"
+#include "new_memory.h"
+
+#ifndef NULL
+#define NULL 0
+#endif
+
+/*
+ *    TYPE_T_dictionary TYPE_T_dictionary_Create(int size):
+ *        Requires: size > 0
+ *        Effects: Returns a new empty dictionary containing no bindings.
+ *                 The returned dictionary must be destroyed using
+ *                 TYPE_T_dictionary_Destroy.  Size is a time vs space
+ *                 parameter.  For this implementation, space used is
+ *                 proportional to size and time used is proportional
+ *                 to number of bindings divided by size.  It is preferable
+ *                 that size is a prime number.
+ */
+
+TYPE_T_dictionary TYPE_T_dictionary_Create(size)
+     int size;
+{
+    int i;
+    TYPE_T_dictionary result;
+
+    result = (TYPE_T_dictionary)malloc(sizeof(struct _TYPE_T_dictionary));
+    result->size = size;
+    result->slots = (TYPE_T_dictionary_binding **)malloc(
+		     size*sizeof(TYPE_T_dictionary_binding *));
+
+    for (i=0; i<size; i++)
+      result->slots[i] = NULL;
+
+    return(result);
+}
+
+/*
+ *    void TYPE_T_dictionary_Destroy(TYPE_T_dictionary d):
+ *        Requires: d is a non-destroyed TYPE_T_dictionary
+ *        Modifies: d
+ *        Effects: Destroys dictionary d freeing up the space it consumes.
+ *                 Dictionary d should never be referenced again.  Note that
+ *                 free is NOT called on the values of the bindings.  If
+ *                 this is needed, the client must do this first using
+ *                 TYPE_T_dictionary_Enumerate.
+ */
+
+void TYPE_T_dictionary_Destroy(d)
+     TYPE_T_dictionary d;
+{
+    int i;
+    TYPE_T_dictionary_binding *binding_ptr, *new_binding_ptr;
+
+    for (i=0; i<d->size; i++) {
+	binding_ptr = d->slots[i];
+	while (binding_ptr) {
+	    new_binding_ptr = binding_ptr->next;
+	    free(binding_ptr->key);
+	    free(binding_ptr);
+	    binding_ptr = new_binding_ptr;
+	}
+    }
+    free(d->slots);
+    free(d);
+}
+
+/*
+ *    void TYPE_T_dictionary_Enumerate(TYPE_T_dictionary d; void (*proc)()):
+ *        Requires: proc is a void procedure taking 1 argument, a
+ *                  TYPE_T_dictionary_binding pointer, which does not
+ *                  make any calls using dictionary d.
+ *        Effects: Calls proc once with each binding in dictionary d.
+ *                 Order of bindings passed is undefined.  Note that
+ *                 only the value field of the binding should be considered
+ *                 writable by proc.
+ */
+
+void TYPE_T_dictionary_Enumerate(d, proc)
+     TYPE_T_dictionary d;
+     void (*proc)(/* TYPE_T_dictionary_binding *b */);
+{
+    int i;
+    TYPE_T_dictionary_binding *binding_ptr;
+
+    for (i=0; i<d->size; i++) {
+	binding_ptr = d->slots[i];
+	while (binding_ptr) {
+	    proc(binding_ptr);
+	    binding_ptr = binding_ptr->next;
+	}
+    }
+}
+
+/*
+ *  Private routine:
+ *
+ *    unsigned int dictionary__hash(char *s):
+ *        Effects: Hashs s to an unsigned integer.  This number mod the
+ *                 hash table size is supposed to roughly evenly distribute
+ *                 keys over the table's slots.
+ */
+
+static unsigned int dictionary__hash(s)
+     char *s;
+{
+    unsigned int result = 0;
+
+    if (!s)
+      return(result);
+
+    while (s[0]) {
+        result <<= 1;
+        result += s[0];
+        s++;
+    }
+
+    return(result);
+}
+
+/*
+ *    TYPE_T_dictionary_binding *TYPE_T_dictionary_Lookup(TYPE_T_dictionary d,
+ *                                                        char *key):
+ *        Effects: If key is not bound in d, returns 0.  Othersize,
+ *                 returns a pointer to the binding that binds key.
+ *                 Note the access restrictions on bindings...
+ */
+
+TYPE_T_dictionary_binding *TYPE_T_dictionary_Lookup(d, key)
+     TYPE_T_dictionary d;
+     char *key;
+{
+    TYPE_T_dictionary_binding *binding_ptr;
+
+    binding_ptr = d->slots[dictionary__hash(key)%(d->size)];
+    while (binding_ptr) {
+	if (string_Eq(key, binding_ptr->key))
+	  return(binding_ptr);
+	binding_ptr = binding_ptr->next;
+    }
+
+    return(NULL);
+}
+
+/*
+ *    TYPE_T_dictionary_binding *TYPE_T_dictionary_Define(TYPE_T_dictionary d,
+ *                                            char *key,
+ *                                            int *already_existed):
+ *        Modifies: d
+ *        Effects: If key is bound in d, returns a pointer to the binding
+ *                 that binds key.  Otherwise, adds a binding of key to
+ *                 d and returns its address.  If already_existed is non-zero
+ *                 then *already_existed is set to 0 if key was not
+ *                 previously bound in d and 1 otherwise.
+ *                 Note the access restrictions on bindings...  Note also
+ *                 that the value that key is bounded to if a binding is
+ *                 created is undefined.  The caller should set the value
+ *                 in this case.
+ */
+
+TYPE_T_dictionary_binding *TYPE_T_dictionary_Define(d, key, already_existed)
+     TYPE_T_dictionary d;
+     char *key;
+     int *already_existed;
+{
+    TYPE_T_dictionary_binding **ptr_to_the_slot, *binding_ptr;
+
+    ptr_to_the_slot = &(d->slots[dictionary__hash(key)%(d->size)]);
+
+    binding_ptr = *ptr_to_the_slot;
+    while (binding_ptr) {
+	if (string_Eq(binding_ptr->key, key)) {
+	    if (already_existed)
+	      *already_existed = 1;
+	    return(binding_ptr);
+	}
+	binding_ptr = binding_ptr->next;
+    }
+
+    if (already_existed)
+      *already_existed = 0;
+    binding_ptr = (TYPE_T_dictionary_binding *)malloc(
+				        sizeof(TYPE_T_dictionary_binding));
+    binding_ptr->next = *ptr_to_the_slot;
+    binding_ptr->key = string_Copy(key);
+    *ptr_to_the_slot = binding_ptr;
+    return(binding_ptr);
+}
+
+/*
+ *    void TYPE_T_dictionary_Delete(TYPE_T_dictionary d,
+ *                                  TYPE_T_dictionary_binding *b):
+ *        Requires: *b is a binding in d.
+ *        Modifies: d
+ *        Effects: Removes the binding *b from d.  Note that if 
+ *                 b->value needs to be freed, it should be freed
+ *                 before making this call.
+ */
+
+void TYPE_T_dictionary_Delete(d, b)
+     TYPE_T_dictionary d;
+     TYPE_T_dictionary_binding *b;
+{
+    TYPE_T_dictionary_binding **ptr_to_binding_ptr;
+
+    ptr_to_binding_ptr = &(d->slots[dictionary__hash(b->key)%(d->size)]);
+
+    while (*ptr_to_binding_ptr != b)
+      ptr_to_binding_ptr = &((*ptr_to_binding_ptr)->next);
+
+    *ptr_to_binding_ptr = b->next;
+    free(b->key);
+    free(b);
+}
diff --git a/zwgc/Dictionary/dictionary.h b/zwgc/Dictionary/dictionary.h
new file mode 100644
index 0000000..3299825
--- /dev/null
+++ b/zwgc/Dictionary/dictionary.h
@@ -0,0 +1,111 @@
+/* This file is part of the Project Athena Zephyr Notification System.
+ * It is one of the source files comprising zwgc, the Zephyr WindowGram
+ * client.
+ *
+ *      Created by:     Marc Horowitz <marc@athena.mit.edu>
+ *
+ *      $Source$
+ *      $Author$
+ *	$Id$
+ *
+ *      Copyright (c) 1989 by the Massachusetts Institute of Technology.
+ *      For copying and distribution information, see the file
+ *      "mit-copyright.h".
+ */
+
+#ifndef TYPE_T_dictionary_TYPE
+#define TYPE_T_dictionary_TYPE
+
+typedef struct _TYPE_T_dictionary_binding {
+    struct _TYPE_T_dictionary_binding *next;       /* PRIVATE */
+    char *key;                                     /* READ-ONLY */
+    TYPE_T value;
+} TYPE_T_dictionary_binding;
+
+typedef struct _TYPE_T_dictionary {                /* PRIVATE */
+    int size;
+    TYPE_T_dictionary_binding **slots;
+} *TYPE_T_dictionary;
+
+/*
+ *    TYPE_T_dictionary TYPE_T_dictionary_Create(int size):
+ *        Requires: size > 0
+ *        Effects: Returns a new empty dictionary containing no bindings.
+ *                 The returned dictionary must be destroyed using
+ *                 TYPE_T_dictionary_Destroy.  Size is a time vs space
+ *                 parameter.  For this implementation, space used is
+ *                 proportional to size and time used is proportional
+ *                 to number of bindings divided by size.  It is preferable
+ *                 that size is a prime number.
+ */
+
+extern TYPE_T_dictionary TYPE_T_dictionary_Create(/* int size */);
+
+/*
+ *    void TYPE_T_dictionary_Destroy(TYPE_T_dictionary d):
+ *        Requires: d is a non-destroyed TYPE_T_dictionary
+ *        Modifies: d
+ *        Effects: Destroys dictionary d freeing up the space it consumes.
+ *                 Dictionary d should never be referenced again.  Note that
+ *                 free is NOT called on the values of the bindings.  If
+ *                 this is needed, the client must do this first using
+ *                 TYPE_T_dictionary_Enumerate.
+ */
+
+extern void TYPE_T_dictionary_Destroy(/* TYPE_T_dictionary d */);
+
+/*
+ *    void TYPE_T_dictionary_Enumerate(TYPE_T_dictionary d; void (*proc)()):
+ *        Requires: proc is a void procedure taking 1 argument, a
+ *                  TYPE_T_dictionary_binding pointer, which does not
+ *                  make any calls using dictionary d.
+ *        Effects: Calls proc once with each binding in dictionary d.
+ *                 Order of bindings passed is undefined.  Note that
+ *                 only the value field of the binding should be considered
+ *                 writable by proc.
+ */
+
+extern void TYPE_T_dictionary_Enumerate(/* TYPE_T_dictionary d, 
+					   void (*proc)() */);
+
+/*
+ *    TYPE_T_dictionary_binding *TYPE_T_dictionary_Lookup(TYPE_T_dictionary d,
+ *                                                        char *key):
+ *        Effects: If key is not bound in d, returns 0.  Othersize,
+ *                 returns a pointer to the binding that binds key.
+ *                 Note the access restrictions on bindings...
+ */
+
+extern TYPE_T_dictionary_binding *TYPE_T_dictionary_Lookup(/* d, key */);
+
+/*
+ *    TYPE_T_dictionary_binding *TYPE_T_dictionary_Define(TYPE_T_dictionary d,
+ *                                            char *key,
+ *                                            int *already_existed):
+ *        Modifies: d
+ *        Effects: If key is bound in d, returns a pointer to the binding
+ *                 that binds key.  Otherwise, adds a binding of key to
+ *                 d and returns its address.  If already_existed is non-zero
+ *                 then *already_existed is set to 0 if key was not
+ *                 previously bound in d and 1 otherwise.
+ *                 Note the access restrictions on bindings...  Note also
+ *                 that the value that key is bounded to if a binding is
+ *                 created is undefined.  The caller should set the value
+ *                 in this case.
+ */
+
+extern TYPE_T_dictionary_binding *TYPE_T_dictionary_Define();
+
+/*
+ *    void TYPE_T_dictionary_Delete(TYPE_T_dictionary d,
+ *                                  TYPE_T_dictionary_binding *b):
+ *        Requires: *b is a binding in d.
+ *        Modifies: d
+ *        Effects: Removes the binding *b from d.  Note that if 
+ *                 b->value needs to be freed, it should be freed
+ *                 before making this call.
+ */
+
+extern void TYPE_T_dictionary_Delete();
+
+#endif
diff --git a/zwgc/Dictionary/generate_dictionary_instance b/zwgc/Dictionary/generate_dictionary_instance
new file mode 100755
index 0000000..dce0bfb
--- /dev/null
+++ b/zwgc/Dictionary/generate_dictionary_instance
@@ -0,0 +1,35 @@
+#!/bin/csh -f
+# This file is part of the Project Athena Zephyr Notification System.
+# It is a tool used in the compilation of zwgc, the Zephyr WindowGram
+# client.
+#
+#      Created by:     Marc Horowitz <marc@athena.mit.edu>
+#
+#      $Source$
+#      $Author$
+#	$Id$
+#
+#      Copyright (c) 1989 by the Massachusetts Institute of Technology.
+#      For copying and distribution information, see the file
+#      "mit-copyright.h".
+#
+
+set source=/afs/athena.mit.edu/astaff/project/zephyr/@sys/zwgc/zwgc.dev/Dictionary
+
+if (z$1x == zx) then
+	echo "usage: generate_dictionary_instance <typename> [<include file>]"
+	exit 1
+endif
+if (-r $source/dictionary.c) then
+else
+	echo "generate_dictionary_instance: unable to open" $source/dictionary.c
+	exit 2
+endif
+
+if (z$2x == zx) then
+	echo > $1_dictionary.h
+else
+	echo "#include" '"'$2'"' > $1_dictionary.h
+endif
+sed "s/TYPE_T/$1/g" $source/dictionary.h >> $1_dictionary.h
+sed "s/TYPE_T/$1/g" $source/dictionary.c > $1_dictionary.c
diff --git a/zwgc/Dictionary/string_dictionary_aux.c b/zwgc/Dictionary/string_dictionary_aux.c
new file mode 100644
index 0000000..c17c157
--- /dev/null
+++ b/zwgc/Dictionary/string_dictionary_aux.c
@@ -0,0 +1,101 @@
+/* This file is part of the Project Athena Zephyr Notification System.
+ * It is one of the source files comprising zwgc, the Zephyr WindowGram
+ * client.
+ *
+ *      Created by:     Marc Horowitz <marc@athena.mit.edu>
+ *
+ *      $Source$
+ *      $Author$
+ *
+ *      Copyright (c) 1989 by the Massachusetts Institute of Technology.
+ *      For copying and distribution information, see the file
+ *      "mit-copyright.h".
+ */
+
+#if (!defined(lint) && !defined(SABER))
+static char rcsid_string_dictionary_aux_c[] = "$Id$";
+#endif
+
+/*
+ * string_dictionary_aux - a module implementing convenience routines for use
+ *                         with string_dictionarys
+ *
+ * Overview:
+ *
+ *       This module implements Fetch and Set operations on
+ *    string_dictionaries which take the place of Define and Lookup for
+ *    most uses.  The importance difference between them and Define and
+ *    Lookup is that they maintain the invariant that all the value strings
+ *    in a string_dictionary are on the heap.  In particular, they do
+ *    free's and string_Copy's whenever needed.  Also implemented is
+ *    SafeDestroy which does a Destroy after freeing all the value strings
+ *    in a string_dictionary.
+ */
+
+#include "new_memory.h"
+#include "string_dictionary.h"
+
+/*
+ *    void string_dictionary_Set(string_dictionary d, string key,string value):
+ *        Modifies: d
+ *        Effects: Binds key to value in d.  Automatically free's the
+ *                 previous value of key, if any.  Value is copied on the
+ *                 heap.
+ */
+
+void string__dictionary_Set(d, key, value)
+     string_dictionary d;
+     string key;
+     string value;
+{
+    string_dictionary_binding *binding;
+    int already_exists;
+
+    binding = string_dictionary_Define(d, key, &already_exists);
+    if (already_exists)
+      free(binding->value);
+
+    binding->value = string_Copy(value);
+}
+
+/*
+ *    char *string_dictionary_Fetch(string_dictionary d, string key)
+ *        Effects: If key is not bound in d, returns 0.  Otherwise,
+ *                 returns the value that key is bound to.  
+ *                 Note that the returned string if any should not be
+ *                 freed or modified in any way.  Note also that it may
+ *                 disappear later if key is rebound.
+ */
+
+char *string_dictionary_Fetch(d, key)
+     string_dictionary d;
+     string key;
+{
+    string_dictionary_binding *binding;
+
+    binding = string_dictionary_Lookup(d, key);
+    if (!binding)
+      return(0);
+
+    return(binding->value);
+}
+
+/*
+ *    void string_dictionary_SafeDestroy(string_dictionary d)
+ *        Modifies: d
+ *        Effects: Like string_dictionary_Destroy except first frees
+ *                 all value's in the dictionary.
+ */
+
+static void free_value_of_binding(b)
+     string_dictionary_binding *b;
+{
+    free(b->value);
+}
+
+void string_dictionary_SafeDestroy(d)
+     string_dictionary d;
+{
+    string_dictionary_Enumerate(d, free_value_of_binding);
+    string_dictionary_Destroy(d);
+}
diff --git a/zwgc/Dictionary/string_dictionary_aux.h b/zwgc/Dictionary/string_dictionary_aux.h
new file mode 100644
index 0000000..2098095
--- /dev/null
+++ b/zwgc/Dictionary/string_dictionary_aux.h
@@ -0,0 +1,58 @@
+/* This file is part of the Project Athena Zephyr Notification System.
+ * It is one of the source files comprising zwgc, the Zephyr WindowGram
+ * client.
+ *
+ *      Created by:     Marc Horowitz <marc@athena.mit.edu>
+ *
+ *      $Source$
+ *      $Author$
+ *	$Id$
+ *
+ *      Copyright (c) 1989 by the Massachusetts Institute of Technology.
+ *      For copying and distribution information, see the file
+ *      "mit-copyright.h".
+ */
+
+#ifndef string_dictionary_aux_MODULE
+#define string_dictionary_aux_MODULE
+
+#include "new_memory.h"
+#include "string_dictionary.h"
+
+/*
+ *    void string_dictionary_Set(string_dictionary d, string key,string value):
+ *        Modifies: d
+ *        Effects: Binds key to value in d.  Automatically free's the
+ *                 previous value of key, if any.  Value is copied on the
+ *                 heap.
+ */
+
+extern void string__dictionary_Set();
+#ifdef DEBUG_MEMORY
+#define string_dictionary_Set(a,b,c)         (set_module(__FILE__,__LINE__),\
+					      string__dictionary_Set(a,b,c))
+#else
+#define string_dictionary_Set(a,b,c)         string__dictionary_Set(a,b,c)
+#endif
+
+/*
+ *    char *string_dictionary_Fetch(string_dictionary d, string key)
+ *        Effects: If key is not bound in d, returns 0.  Otherwise,
+ *                 returns the value that key is bound to.  
+ *                 Note that the returned string if any should not be
+ *                 freed or modified in any way.  Note also that it may
+ *                 disappear later if key is rebound.
+ */
+
+extern char *string_dictionary_Fetch();
+
+/*
+ *    void string_dictionary_SafeDestroy(string_dictionary d)
+ *        Modifies: d
+ *        Effects: Like string_dictionary_Destroy except first frees
+ *                 all value's in the dictionary.
+ */
+
+extern void string_dictionary_SafeDestroy();
+
+#endif