X-Git-Url: https://git.stderr.nl/gitweb?a=blobdiff_plain;ds=sidebyside;f=interpreters%2Fnitfol%2Fhash.c;fp=interpreters%2Fnitfol%2Fhash.c;h=55da1a74e75caa2173c422028355e1ae67fcd5e8;hb=b1f1dc50b22b30c4d7176e1ff7c0805e80fe0724;hp=0000000000000000000000000000000000000000;hpb=50176172d18ae72d019181725c5629d45d21c548;p=projects%2Fchimara%2Fchimara.git

diff --git a/interpreters/nitfol/hash.c b/interpreters/nitfol/hash.c
new file mode 100644
index 0000000..55da1a7
--- /dev/null
+++ b/interpreters/nitfol/hash.c
@@ -0,0 +1,308 @@
+#include "nitfol.h"
+
+
+/* Modified and bugfixed for nitfol by Evin Robertson Sept 10, 1999 */
+
+
+/*
+** public domain code by Jerry Coffin, with improvements by HenkJan Wolthuis.
+**
+** Tested with Visual C 1.0 and Borland C 3.1.
+** Compiles without warnings, and seems like it should be pretty
+** portable.
+*/
+
+
+#ifdef HEADER
+/*
+** A hash table consists of an array of these buckets.  Each bucket
+** holds a copy of the key, a pointer to the data associated with the
+** key, and a pointer to the next bucket that collided with this one,
+** if there was one.
+*/
+
+typedef struct bucket {
+    char *key;
+    void *data;
+    struct bucket *next;
+} bucket;
+
+/*
+** This is what you actually declare an instance of to create a table.
+** You then call 'construct_table' with the address of this structure,
+** and a guess at the size of the table.  Note that more nodes than this
+** can be inserted in the table, but performance degrades as this
+** happens.  Performance should still be quite adequate until 2 or 3
+** times as many nodes have been inserted as the table was created with.
+*/
+
+typedef struct hash_table {
+    size_t size;
+    bucket **table;
+} hash_table;
+#endif
+
+
+/*
+** These are used in freeing a table.  Perhaps I should code up
+** something a little less grungy, but it works, so what the heck.
+*/
+typedef void (*my_function)(void *);
+static my_function function = NULL;
+static hash_table *the_table = NULL;
+
+/* Initialize the hash_table to the size asked for.  Allocates space
+** for the correct number of pointers and sets them to NULL.  If it
+** can't allocate sufficient memory, signals error by setting the size
+** of the table to 0.
+*/
+
+hash_table *n_hash_construct_table(hash_table *table, size_t size)
+{
+      size_t i;
+      bucket **temp;
+
+      table -> size  = size;
+      table -> table = (bucket * *)n_malloc(sizeof(bucket *) * size);
+      temp = table -> table;
+
+      if ( temp == NULL )
+      {
+            table -> size = 0;
+            return table;
+      }
+
+      for (i=0;i<size;i++)
+            temp[i] = NULL;
+      return table;
+}
+
+
+/*
+** Hashes a string to produce an unsigned short, which should be
+** sufficient for most purposes.
+*/
+
+static unsigned hash(const char *string)
+{
+      unsigned ret_val = 0;
+      int i;
+
+      while (*string)
+      {
+	    /* Modified by ecr to fix bug and improve method slightly */
+            ret_val <<= 1;
+            i = string[0] + (string[1] << 8);
+            ret_val ^= i;
+            string ++;
+      }
+      return ret_val;
+}
+
+/*
+** Insert 'key' into hash table.
+** Returns pointer to old data associated with the key, if any, or
+** NULL if the key wasn't in the table previously.
+*/
+
+void *n_hash_insert(const char *key, void *data, hash_table *table)
+{
+      unsigned val = hash(key) % table->size;
+      bucket *ptr;
+
+      /*
+      ** NULL means this bucket hasn't been used yet.  We'll simply
+      ** allocate space for our new bucket and put our data there, with
+      ** the table pointing at it.
+      */
+
+      if (NULL == (table->table)[val])
+      {
+            (table->table)[val] = (bucket *)n_malloc(sizeof(bucket));
+            if (NULL==(table->table)[val])
+                  return NULL;
+
+            (table->table)[val] -> key = n_strdup(key);
+            (table->table)[val] -> next = NULL;
+            (table->table)[val] -> data = data;
+            return (table->table)[val] -> data;
+      }
+
+      /*
+      ** This spot in the table is already in use.  See if the current string
+      ** has already been inserted, and if so, increment its count.
+      */
+
+      for (ptr = (table->table)[val];NULL != ptr; ptr = ptr -> next)
+            if (0 == n_strcmp(key, ptr->key))
+            {
+                  void *old_data;
+
+                  old_data = ptr->data;
+                  ptr -> data = data;
+                  return old_data;
+            }
+
+      /*
+      ** This key must not be in the table yet.  We'll add it to the head of
+      ** the list at this spot in the hash table.  Speed would be
+      ** slightly improved if the list was kept sorted instead.  In this case,
+      ** this code would be moved into the loop above, and the insertion would
+      ** take place as soon as it was determined that the present key in the
+      ** list was larger than this one.
+      */
+
+      ptr = (bucket *)n_malloc(sizeof(bucket));
+      if (NULL==ptr)
+            return 0;
+      ptr -> key = n_strdup(key);
+      ptr -> data = data;
+      ptr -> next = (table->table)[val];
+      (table->table)[val] = ptr;
+      return data;
+}
+
+
+/*
+** Look up a key and return the associated data.  Returns NULL if
+** the key is not in the table.
+*/
+
+void *n_hash_lookup(const char *key, hash_table *table)
+{
+      unsigned val = hash(key) % table->size;
+      bucket *ptr;
+
+      if (NULL == (table->table)[val])
+            return NULL;
+
+      for ( ptr = (table->table)[val];NULL != ptr; ptr = ptr->next )
+      {
+            if (0 == n_strcmp(key, ptr -> key ) )
+                  return ptr->data;
+      }
+      return NULL;
+}
+
+/*
+** Delete a key from the hash table and return associated
+** data, or NULL if not present.
+*/
+
+void *n_hash_del(const char *key, hash_table *table)
+{
+      unsigned val = hash(key) % table->size;
+      void *data;
+      bucket *ptr, *last = NULL;
+
+      if (NULL == (table->table)[val])
+            return NULL;
+
+      /*
+      ** Traverse the list, keeping track of the previous node in the list.
+      ** When we find the node to delete, we set the previous node's next
+      ** pointer to point to the node after ourself instead.  We then delete
+      ** the key from the present node, and return a pointer to the data it
+      ** contains.
+      */
+
+      for (last = NULL, ptr = (table->table)[val];
+            NULL != ptr;
+            last = ptr, ptr = ptr->next)
+      {
+            if (0 == n_strcmp(key, ptr -> key))
+            {
+                  if (last != NULL )
+                  {
+                        data = ptr -> data;
+                        last -> next = ptr -> next;
+                        n_free(ptr->key);
+                        n_free(ptr);
+                        return data;
+                  }
+
+                  /*
+                  ** If 'last' still equals NULL, it means that we need to
+                  ** delete the first node in the list. This simply consists
+                  ** of putting our own 'next' pointer in the array holding
+                  ** the head of the list.  We then dispose of the current
+                  ** node as above.
+                  */
+
+                  else
+                  {
+                        data = ptr->data;
+                        (table->table)[val] = ptr->next;
+                        n_free(ptr->key);
+                        n_free(ptr);
+                        return data;
+                  }
+            }
+      }
+
+      /*
+      ** If we get here, it means we didn't find the item in the table.
+      ** Signal this by returning NULL.
+      */
+
+      return NULL;
+}
+
+/*
+** free_table iterates the table, calling this repeatedly to free
+** each individual node.  This, in turn, calls one or two other
+** functions - one to free the storage used for the key, the other
+** passes a pointer to the data back to a function defined by the user,
+** process the data as needed.
+*/
+
+static void free_node(const char *key, void *data)
+{
+      (void) data;
+
+      if (function)
+            function(n_hash_del(key,the_table));
+      else  n_hash_del(key,the_table);
+}
+
+/*
+** Frees a complete table by iterating over it and freeing each node.
+** the second parameter is the address of a function it will call with a
+** pointer to the data associated with each node.  This function is
+** responsible for freeing the data, or doing whatever is needed with
+** it.
+*/
+
+void n_hash_free_table(hash_table *table, void (*func)(void *))
+{
+      function = func;
+      the_table = table;
+
+      n_hash_enumerate( table, free_node);
+      n_free(table->table);
+      table->table = NULL;
+      table->size = 0;
+
+      the_table = NULL;
+      function = (void (*)(void *))NULL;
+}
+
+/*
+** Simply invokes the function given as the second parameter for each
+** node in the table, passing it the key and the associated data.
+*/
+
+void n_hash_enumerate( hash_table *table, void (*func)(const char *, void *))
+{
+      unsigned i;
+      bucket *temp, *next;
+
+      for (i=0; i < table->size; i++)
+      {
+	    for (temp = (table->table)[i]; temp; temp=next)
+	    {
+                   next = temp->next; /* ecr - temp may be deleted by func */
+	           func(temp->key, temp->data);
+	    }
+      }
+}