--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hash.c	Mon Aug 13 08:45:50 2007 +0200
@@ -0,0 +1,490 @@
+/* Hash tables.
+   Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc.
+
+This file is part of XEmacs.
+
+XEmacs is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 2, or (at your option) any
+later version.
+
+XEmacs is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with XEmacs; see the file COPYING.  If not, write to
+the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.  */
+
+/* Synched up with: Not in FSF. */
+
+#ifdef emacs
+#include <config.h>
+#include "lisp.h"
+
+#define NULL_ENTRY (LISP_TO_VOID (Qnil))
+
+#else /* !emacs */
+
+#define NULL_ENTRY ((void *) 1)
+
+#endif /* !emacs */
+
+#include <string.h>
+#include "hash.h"
+#include "elhash.h"
+
+static CONST int 
+primes []={
+  13,
+  29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 
+  761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 
+  8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 
+  62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 
+  389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319,
+  2009191, 2411033, 2893249
+};
+
+/* strings code */
+
+/* from base/generic-hash.cc, and hence from Dragon book, p436 */
+unsigned long
+string_hash (CONST void *xv)
+{ 
+  unsigned int h = 0;
+  unsigned int g;
+  unsigned CONST char *x = (unsigned CONST char *) xv;
+
+  if (!x) return 0;
+
+  while (*x != 0)
+    {
+      h = (h << 4) + *x++;
+      if ((g = h & 0xf0000000) != 0)
+	h = (h ^ (g >> 24)) ^ g;
+    }
+
+  return h;
+}
+
+unsigned long
+memory_hash (CONST void *xv, int size)
+{ 
+  unsigned int h = 0;
+  unsigned int g;
+  unsigned CONST char *x = (unsigned CONST char *) xv;
+
+  if (!x) return 0;
+
+  while (size > 0)
+    {
+      h = (h << 4) + *x++;
+      if ((g = h & 0xf0000000) != 0)
+	h = (h ^ (g >> 24)) ^ g;
+      size--;
+    }
+
+  return h;
+}
+
+static int 
+string_eq (CONST void *st1v, CONST void *st2v)
+{
+  CONST char *st1 = (CONST char *)st1v;
+  CONST char *st2 = (CONST char *)st2v;
+
+  if (!st1)
+    return (st2)?0:1;
+  else if (!st2)
+    return 0;
+  else
+    return !strcmp (st1, st2);
+}
+
+
+static unsigned int 
+prime_size (unsigned int size)
+{
+  unsigned int i;
+  CONST int lim = countof (primes);
+  for (i = 0; i < lim; i++)
+    if (size <= primes [i]) return primes [i];
+  return primes [lim - 1];
+}
+
+static void rehash (hentry *harray, c_hashtable ht, unsigned int size);
+
+#define KEYS_DIFFER_P(old, new, testfun) \
+  ((testfun)?(((old) == (new))?0:(!(testfun ((old), new)))):((old) != (new)))
+
+CONST void *
+gethash (CONST void *key, c_hashtable hash, CONST void **ret_value)
+{
+  hentry *harray = hash->harray;
+  int (*test_function) (CONST void *, CONST void *) = hash->test_function;
+  unsigned int hsize = hash->size;
+  unsigned int hcode_initial = 
+    (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key);
+  unsigned int hcode = hcode_initial % hsize;
+  hentry *e = &harray [hcode];
+  CONST void *e_key = e->key;
+
+  if (!key) 
+    {
+      *ret_value = hash->zero_entry;
+      return (void *) hash->zero_set;
+    }
+    
+  if ((e_key)?
+      (KEYS_DIFFER_P (e_key, key, test_function)):
+      (e->contents == NULL_ENTRY))
+    {
+      unsigned int h2 = hsize - 2;
+      unsigned int incr = 1 + (hcode_initial % h2);
+      do
+        {
+          hcode = hcode + incr;
+          if (hcode >= hsize) hcode = hcode - hsize;
+          e = &harray [hcode];
+          e_key = e->key;
+        } 
+      while ((e_key)?
+             (KEYS_DIFFER_P (e_key, key, test_function)):
+             (e->contents == NULL_ENTRY));
+    }
+
+  *ret_value = e->contents;
+  return e->key;
+}
+
+void 
+clrhash (c_hashtable hash)
+{
+  memset (hash->harray, 0, sizeof (hentry) * hash->size);
+  hash->zero_entry = 0;
+  hash->zero_set = 0;
+  hash->fullness = 0;
+}
+
+void
+free_hashtable (c_hashtable hash)
+{
+#ifdef emacs
+  if (!NILP (hash->elisp_table))
+    return;
+#endif
+  xfree (hash->harray);
+  xfree (hash);
+}
+
+c_hashtable
+make_hashtable (unsigned int hsize)
+{
+  c_hashtable res = (c_hashtable) xmalloc (sizeof (struct _C_hashtable));
+  memset (res, 0, sizeof (struct _C_hashtable));
+  res->size = prime_size ((13 * hsize) / 10);
+  res->harray = (hentry *) xmalloc (sizeof (hentry) * res->size);
+#ifdef emacs
+  res->elisp_table = Qnil;
+#endif
+  clrhash (res);
+  return res;
+}
+
+c_hashtable
+make_general_hashtable (unsigned int hsize,
+			unsigned long (*hash_function) (CONST void *),
+			int (*test_function) (CONST void *, CONST void *))
+{
+  c_hashtable res = (c_hashtable) xmalloc (sizeof (struct _C_hashtable));
+  memset (res, 0, sizeof (struct _C_hashtable));
+  res->size = prime_size ((13 * hsize) / 10);
+  res->harray = (hentry *) xmalloc (sizeof (hentry) * res->size);
+  res->hash_function = hash_function;
+  res->test_function = test_function;
+#ifdef emacs
+  res->elisp_table = Qnil;
+#endif
+  clrhash (res);
+  return res;
+}
+
+c_hashtable 
+make_strings_hashtable (unsigned int hsize)
+{
+  return make_general_hashtable (hsize, string_hash, string_eq);
+}
+
+#ifdef emacs
+unsigned int
+compute_harray_size (unsigned int hsize)
+{
+  return prime_size ((13 * hsize) / 10);
+}
+#endif
+
+void
+copy_hash (c_hashtable dest, c_hashtable src)
+{
+#ifdef emacs
+  /* if these are not the same, then we are losing here */
+  if ((NILP (dest->elisp_table)) != (NILP (src->elisp_table)))
+    {
+      error ("Incompatible hashtable types to copy_hash.");
+      return;
+    }
+#endif
+
+  if (dest->size != src->size)
+    {
+#ifdef emacs
+      if (!NILP (dest->elisp_table))
+        elisp_hvector_free (dest->harray, dest->elisp_table);
+      else
+#endif
+        xfree (dest->harray);
+
+      dest->size = src->size;
+#ifdef emacs
+      if (!NILP (dest->elisp_table))
+        dest->harray = 
+          (hentry *) elisp_hvector_malloc
+            (sizeof (hentry) * dest->size, dest->elisp_table);
+      else
+#endif
+        dest->harray = (hentry *) xmalloc (sizeof (hentry) * dest->size);
+    }
+  dest->fullness = src->fullness;
+  dest->zero_entry = src->zero_entry;
+  dest->zero_set = src->zero_set;
+  dest->hash_function = src->hash_function;
+  dest->test_function = src->test_function;
+  memcpy (dest->harray, src->harray, sizeof (hentry) * dest->size);
+}
+  
+static void
+grow_hashtable (c_hashtable hash, unsigned int new_size)
+{
+  unsigned int old_hsize = hash->size;
+  hentry *old_harray = hash->harray;
+  unsigned int new_hsize = prime_size (new_size);
+  hentry *new_harray;
+
+#ifdef emacs
+  /* We test for Qzero to facilitate free-hook.c.  That module creates
+     a hashtable very very early, at which point Qnil has not yet
+     been set and is thus all zeroes.  Qzero is "automatically"
+     initialized at startup because its correct value is also all
+     zeroes. */
+  if (!NILP (hash->elisp_table) && !ZEROP (hash->elisp_table))
+    new_harray = (hentry *) elisp_hvector_malloc (sizeof (hentry) * new_hsize,
+						  hash->elisp_table);
+  else
+#endif
+    new_harray =
+      (hentry *) xmalloc (sizeof (hentry) * new_hsize);
+
+  hash->size = new_hsize;
+  hash->harray = new_harray;
+
+  /* do the rehash on the "grown" table */
+  {
+    long old_zero_set = hash->zero_set;
+    void *old_zero_entry = hash->zero_entry;
+    clrhash (hash);
+    hash->zero_set = old_zero_set;
+    hash->zero_entry = old_zero_entry;
+    rehash (old_harray, hash, old_hsize);
+  }
+
+#ifdef emacs
+  if (!NILP (hash->elisp_table) && !ZEROP (hash->elisp_table))
+    elisp_hvector_free (old_harray, hash->elisp_table);
+  else
+#endif
+    xfree (old_harray);
+}
+
+void
+expand_hashtable (c_hashtable hash, unsigned int needed_size)
+{
+  unsigned int hsize = hash->size;
+  int comfortable_size = (13 * needed_size) / 10;
+  if (hsize < comfortable_size)
+    grow_hashtable (hash, comfortable_size + 1);
+}
+
+void 
+puthash (CONST void *key, void *cont, c_hashtable hash)
+{
+  unsigned int hsize = hash->size;
+  int (*test_function) (CONST void *, CONST void *) = hash->test_function;
+  unsigned int fullness = hash->fullness;
+  hentry *harray;
+  CONST void *e_key;
+  hentry *e;
+  unsigned int hcode_initial = 
+    (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key);
+  unsigned int hcode;
+  unsigned int incr = 0;
+  unsigned int h2;
+  CONST void *oldcontents;
+
+  if (!key) 
+    {
+      hash->zero_entry = cont;      
+      hash->zero_set = 1;
+      return;
+    }
+
+  if (hsize < (1 + ((13 * fullness) / 10)))
+    {
+      grow_hashtable (hash, hsize + 1);
+      hsize = hash->size;
+      fullness = hash->fullness;
+    }
+
+  harray= hash->harray;
+  h2 = hsize - 2;
+
+  hcode = hcode_initial % hsize;
+  
+  e_key = harray [hcode].key;
+  if (e_key && (KEYS_DIFFER_P (e_key, key, test_function)))
+    {
+      h2 = hsize - 2;
+      incr = 1 + (hcode_initial % h2);
+      do
+        {
+          hcode = hcode + incr;
+          if (hcode >= hsize) hcode = hcode - hsize;
+          e_key = harray [hcode].key;
+        } 
+      while (e_key && (KEYS_DIFFER_P (e_key, key, test_function)));
+    }
+  oldcontents = harray [hcode].contents;
+  harray [hcode].key = key;
+  harray [hcode].contents = cont;
+  /* if the entry that we used was a deleted entry,
+     check for a non deleted entry of the same key,
+     then delete it */
+  if (!e_key && (oldcontents == NULL_ENTRY))
+    {
+      if (!incr) incr = 1 + ((unsigned long) key % h2);
+
+      do
+        {
+          hcode = hcode + incr;
+          if (hcode >= hsize) hcode = hcode - hsize;
+          e = &harray [hcode];
+          e_key = e->key;
+        }
+      while ((e_key)?
+             (KEYS_DIFFER_P (e_key, key, test_function)):
+             (e->contents == NULL_ENTRY));
+
+      if (e_key)
+        {
+          e->key = 0;
+          e->contents = NULL_ENTRY;
+        }
+    }
+
+  /* only increment the fullness when we used up a new hentry */
+  if (!e_key || (KEYS_DIFFER_P (e_key, key, test_function)))
+    hash->fullness++;
+}
+
+static void
+rehash (hentry *harray, c_hashtable hash, unsigned int size)
+{
+  hentry *limit = harray + size;
+  hentry *e;
+  for (e = harray; e < limit; e++)
+    {
+      if (e->key)
+	puthash (e->key, e->contents, hash);
+    }
+}
+
+void 
+remhash (CONST void *key, c_hashtable hash)
+{
+  hentry *harray = hash->harray;
+  int (*test_function) (CONST void*, CONST void*) = hash->test_function;
+  unsigned int hsize = hash->size;
+  unsigned int hcode_initial = 
+    (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key);
+  unsigned int hcode = hcode_initial % hsize;
+  hentry *e = &harray [hcode];
+  CONST void *e_key = e->key;
+
+  if (!key) 
+    {
+      hash->zero_entry = 0;
+      hash->zero_set = 0;
+      return;
+    }
+
+  if ((e_key)?
+      (KEYS_DIFFER_P (e_key, key, test_function)):
+      (e->contents == NULL_ENTRY))
+    {
+      unsigned int h2 = hsize - 2;
+      unsigned int incr = 1 + (hcode_initial % h2);
+      do
+        {
+          hcode = hcode + incr;
+          if (hcode >= hsize) hcode = hcode - hsize;
+          e = &harray [hcode];
+          e_key = e->key;
+        }
+      while ((e_key)?
+             (KEYS_DIFFER_P (e_key, key, test_function)):
+             (e->contents == NULL_ENTRY));
+    }
+  if (e_key)
+    {
+      e->key = 0;
+      e->contents = NULL_ENTRY;
+      /* Note: you can't do fullness-- here, it breaks the world. */
+    }
+}
+
+void 
+maphash (maphash_function mf, c_hashtable hash, void *arg)
+{
+  hentry *e;
+  hentry *limit;
+  
+  if (hash->zero_set) 
+    ((*mf) (0, hash->zero_entry, arg));
+
+  for (e = hash->harray, limit = e + hash->size; e < limit; e++)
+    {
+      if (e->key)
+	((*mf) (e->key, e->contents, arg));
+    }
+}
+
+void 
+map_remhash (remhash_predicate predicate, c_hashtable hash, void *arg)
+{
+  hentry *e;
+  hentry *limit;
+  
+  if (hash->zero_set && ((*predicate) (0, hash->zero_entry, arg)))
+    {
+      hash->zero_set = 0;
+      hash->zero_entry = 0;
+    }
+
+  for (e = hash->harray, limit = e + hash->size; e < limit; e++)
+    if ((*predicate) (e->key, e->contents, arg))
+      {
+        e->key = 0;
+        e->contents = NULL_ENTRY;
+      }
+}