New files.

diff --git a/cos-hash.c b/cos-hash.c
new file mode 100644 (file)
index 0000000..37acf1c
--- /dev/null
+++ b/cos-hash.c
@@ -0,0 +1,182 @@
+/* Copyright (C) 2013 MORIOKA Tomohiko
+   This file is part of the CONCORD Library.
+
+   The CONCORD Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The CONCORD Library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the CONCORD Library; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+   02111-1307 USA.  */
+
+#include <stdlib.h>
+#include "cos.h"
+#include "cos-i.h"
+#include "concord-name.h"
+#include "cos-hash.h"
+#include "hash-i.h"
+
+COS_Hash_Table
+cos_make_hash_table ()
+{
+  return concord_make_hash_table (256);
+}
+
+void
+cos_destroy_hash_table (COS_Hash_Table table)
+{
+  size_t i;
+
+  for (i = 0; i < table->size; i++)
+    {
+      COS_Hash_Table_Entry entry = table->data[i];
+
+      if (entry.key != NULL)
+       {
+         cos_release_object (entry.key);
+         cos_release_object (entry.value);
+       }
+    }
+  concord_destroy_hash_table (table);
+}
+
+unsigned long cos_symbol_hash_string (COS_String string);
+
+/* #### for a 64-bit machine, we should substitute a prime just over 2^32 */
+#define GOOD_HASH 65599 /* prime number just over 2^16; Dragon book, p. 435 */
+#define HASH2(a,b)               (GOOD_HASH * (a)                     + (b))
+#define HASH3(a,b,c)             (GOOD_HASH * HASH2 (a,b)             + (c))
+#define HASH4(a,b,c,d)           (GOOD_HASH * HASH3 (a,b,c)           + (d))
+#define HASH5(a,b,c,d,e)         (GOOD_HASH * HASH4 (a,b,c,d)         + (e))
+#define HASH6(a,b,c,d,e,f)       (GOOD_HASH * HASH5 (a,b,c,d,e)       + (f))
+#define HASH7(a,b,c,d,e,f,g)     (GOOD_HASH * HASH6 (a,b,c,d,e,f)     + (g))
+#define HASH8(a,b,c,d,e,f,g,h)   (GOOD_HASH * HASH7 (a,b,c,d,e,f,g)   + (h))
+#define HASH9(a,b,c,d,e,f,g,h,i) (GOOD_HASH * HASH8 (a,b,c,d,e,f,g,h) + (i))
+
+static size_t
+cos_hash_object0 (COS_object obj, int depth)
+{
+  if ( obj == NULL )
+    return 0;
+  else if ( COS_OBJECT_INT_P (obj) )
+    return cos_int_value (obj);
+  else if ( COS_OBJECT_CHAR_P (obj) )
+    return cos_char_id (obj);
+  else if ( COS_OBJECT_STRING_P (obj) )
+    return cos_symbol_hash_string (obj);
+  else if ( COS_OBJECT_SYMBOL_P (obj) )
+    return cos_symbol_hash_string (cos_symbol_name (obj));
+  else if ( COS_OBJECT_CONS_P (obj) )
+    {
+      if ( depth > 5 )
+       return 0;
+      else
+       return HASH2 (cos_hash_object0 (cos_car (obj), depth + 1),
+                     cos_hash_object0 (cos_cdr (obj), depth + 1));
+    }
+
+  return (size_t)obj;
+}
+
+size_t
+cos_hash_object (COS_object obj)
+{
+  return cos_hash_object0 (obj, 0);
+}
+
+int
+cos_hash_table_put (COS_Hash_Table table,
+                   COS_object key, COS_object value)
+{
+  unsigned long i, index;
+  COS_Hash_Table_Entry* entry;
+
+  if (table == NULL)
+    return -1;
+
+  index = cos_hash_object (key) % table->size;
+  for (i = index; i < table->size; i++)
+    {
+      entry = &table->data[i];
+      if (entry->key == NULL)
+       {
+         cos_retain_object (key);
+         cos_retain_object (value);
+         entry->key = key;
+         entry->value = value;
+         return 0;
+       }
+      else if (entry->key == key)
+       {
+         cos_release_object (entry->value);
+         cos_retain_object (value);
+         entry->value = value;
+         return 0;
+       }
+    }
+  if (cos_hash_table_grow (table) == 0)
+    return cos_hash_table_put (table, key, value);
+  return -1;
+}
+
+COS_object
+cos_hash_table_get (COS_Hash_Table table, COS_object key)
+{
+  unsigned long i, index;
+  COS_Hash_Table_Entry* entry;
+
+  if (table == NULL)
+    return NULL;
+
+  index = cos_hash_object (key) % table->size;
+  for (i = index; i < table->size; i++)
+    {
+      entry = &table->data[i];
+      if (entry->key == NULL)
+       return NULL;
+      else if (entry->key == key)
+       return entry->value;
+    }
+  return NULL;
+}
+
+int
+cos_hash_table_grow (COS_Hash_Table table)
+{
+  COS_Hash_Table new_table
+    = concord_make_hash_table ( table->size * 2
+                               /* - (table->size * 4 / 5) */ );
+  size_t i;
+
+  if (new_table == NULL)
+    return -1;
+
+  for (i = 0; i < table->size; i++)
+    {
+      COS_Hash_Table_Entry* entry = &table->data[i];
+
+      if ( (entry->key != NULL) && (entry->value != NULL) )
+       {
+         int status
+           = cos_hash_table_put (new_table, entry->key, entry->value);
+
+         if (status != 0)
+           {
+             concord_destroy_hash_table (new_table);
+             return -1;
+           }
+       }
+    }
+  free (table->data);
+  table->size = new_table->size;
+  table->data = new_table->data;
+  free (new_table);
+  return 0;
+}

diff --git a/hash-i.h b/hash-i.h
new file mode 100644 (file)
index 0000000..5ee3238
--- /dev/null
+++ b/hash-i.h
@@ -0,0 +1,54 @@
+/* Copyright (C) 2003, 2004, 2005, 2006, 2013 MORIOKA Tomohiko
+   This file is part of the CONCORD Library.
+
+   The CONCORD Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The CONCORD Library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the CONCORD Library; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+   02111-1307 USA.  */
+
+#ifndef _HASH_I_H
+#define _HASH_I_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+#if 0
+}
+#endif
+
+struct CONCORD_HASH_TABLE_ENTRY
+{
+  void *key;
+  void *value;
+};
+
+struct CONCORD_HASH_TABLE
+{
+  size_t size;
+  CONCORD_HASH_TABLE_ENTRY *data;
+};
+
+CONCORD_HASH_TABLE* concord_make_hash_table (size_t size);
+
+void concord_destroy_hash_table (CONCORD_HASH_TABLE* hash);
+
+unsigned long concord_hash_c_string (const unsigned char *ptr);
+
+#if 0
+{
+#endif
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* !_HASH_I_H */