[Minor] [minor commit] r673 - trunk/gc

jimb at red-bean.com jimb at red-bean.com
Tue Oct 24 05:38:55 CDT 2006


Author: jimb
Date: Tue Oct 24 05:38:55 2006
New Revision: 673

Modified:
   trunk/gc/hash-tables.c
   trunk/gc/hash-tables.h

Log:
Move the definitions of the hash table types into gc/hash-tables.h, so other
modules can muck about with hash table contents directly if they dare.


Modified: trunk/gc/hash-tables.c
==============================================================================
--- trunk/gc/hash-tables.c	(original)
+++ trunk/gc/hash-tables.c	Tue Oct 24 05:38:55 2006
@@ -84,52 +84,6 @@
 static mn_ref_t *hash_array_label;
 
 
-/* The wrapper object for hash tables.  This part is not thrown away
-   when we resize a hash table.  */
-struct hash_table
-{
-  /* Attached label for this object.  */
-  tagged_t label;
-
-  /* The population of the hash table.  We re-size the hash table as
-     needed to keep the hash table between 1/8 and 1/2 occupancy.  At
-     1/2 occupancy, if the hash function distributes keys randomly
-     across the table, one expects to probe twice, on average, before
-     finding the right entry.  */
-  size_t population;
-
-  /* The number of times we've resized the table.  */
-  int resizings;
-
-  /* The table itself.  This is always a reference to a hash_array
-     object.  */
-  tagged_t array;
-};
-
-
-/* The actual hash array.  This part is replaced when we resize.  */
-struct hash_array
-{
-  /* Attached label for this object.  */
-  tagged_t label;
-
-  /* The length of the array.
-     This is in elements, not associations.  Divide by two to get 
-     the number of associations in the array.  */
-  size_t length;
-
-  /* A flag which the garbage collector sets when it scans the object,
-     possibly changing the addresses of the objects it contains.  */
-  bool scanned;
-
-  /* The elements.
-     These are actually key/value pairs ("associations"): even-indexed
-     elements are keys, and subsequent elements are values.  So the
-     whole hash array holds LENGTH / 2 key / value pairs.  */
-  tagged_t elements[];
-};
-     
-
 
 /* Tagging and untagging.  */
 
@@ -147,8 +101,8 @@
 }
 
 
-static struct hash_table *
-untag_hash_table (tagged_t table)
+struct hash_table *
+mn__untag_hash_table (tagged_t table)
 {
   return mn__untag_labeled_object (table);
 }
@@ -159,7 +113,7 @@
 {
   check (mn__is_hash_table (table));
 
-  return untag_hash_table (table);
+  return mn__untag_hash_table (table);
 }
 
 
@@ -170,8 +124,8 @@
 }
 
 
-static struct hash_array *
-untag_hash_array (tagged_t array)
+struct hash_array *
+mn__untag_hash_array (tagged_t array)
 {
   check (is_hash_array (array));
 
@@ -235,7 +189,7 @@
 static void
 hash_table_debug_print (FILE *f, tagged_t obj)
 {
-  struct hash_table *t = untag_hash_table (obj);
+  struct hash_table *t = mn__untag_hash_table (obj);
 
   fprintf (f, "#{hash table (pop=%zu) ", t->population);
   mn__debug_print_obj (f, t->array);
@@ -250,7 +204,7 @@
 static void
 hash_array_debug_print (FILE *f, tagged_t obj)
 {
-  struct hash_array *a = untag_hash_array (obj);
+  struct hash_array *a = mn__untag_hash_array (obj);
   size_t population = 0;
   int i;
   bool any = false;
@@ -336,7 +290,7 @@
 validate_hash_table (struct hash_table *t)
 {
   check (is_hash_array (t->array));
-  struct hash_array *a = untag_hash_array (t->array);
+  struct hash_array *a = mn__untag_hash_array (t->array);
   size_t population = validate_hash_array (a);
 
   check (t->population == population);
@@ -625,7 +579,7 @@
 static void
 resize (mn_call_t *c, struct hash_table *table)
 {
-  struct hash_array *old = untag_hash_array (table->array);
+  struct hash_array *old = mn__untag_hash_array (table->array);
   struct hash_array *new
     = make_hash_array (c, 2 * best_size (table->population));
   copy_array (new, old, table);
@@ -730,7 +684,7 @@
 mn__hash_table_put (mn_call_t *c, tagged_t table, tagged_t key, tagged_t value)
 {
   struct hash_table *t = check_hash_table (table);
-  struct hash_array *a = untag_hash_array (t->array);
+  struct hash_array *a = mn__untag_hash_array (t->array);
 
   /* We don't know yet whether this put will actually add another
      association to the table, or whether it's just replacing an
@@ -741,7 +695,7 @@
   if (t->population >= a->length / 4)
     {
       resize (c, t);
-      a = untag_hash_array (t->array);
+      a = mn__untag_hash_array (t->array);
     }
 
   /* If our array has been disturbed by the collector, the keys may
@@ -785,7 +739,7 @@
 mn__hash_table_get (mn_call_t *c, tagged_t table, tagged_t key)
 {
   struct hash_table *t = check_hash_table (table);
-  struct hash_array *a = untag_hash_array (t->array);
+  struct hash_array *a = mn__untag_hash_array (t->array);
 
   /* If our array has been disturbed by the collector, the keys may
      have changed their hash values; rehash it.  */
@@ -829,7 +783,7 @@
   mn__begin_incoherent (c);
   {
     struct hash_table *t = check_hash_table (table->obj);
-    struct hash_array *a = untag_hash_array (t->array);
+    struct hash_array *a = mn__untag_hash_array (t->array);
 
     /* We don't know yet whether this remove will actually delete an
        association from the table, or whether it's just trying to
@@ -840,7 +794,7 @@
     if (t->population <= a->length / 16)
       {
         resize (c, t);
-        a = untag_hash_array (t->array);
+        a = mn__untag_hash_array (t->array);
       }
     else if (a->scanned)
       rehash (a);
@@ -901,9 +855,9 @@
 {
   int i;
   struct hash_table *st = check_hash_table (src);
-  struct hash_array *sa = untag_hash_array (st->array);
+  struct hash_array *sa = mn__untag_hash_array (st->array);
   struct hash_table *dt = check_hash_table (dest);
-  struct hash_array *da = untag_hash_array (dt->array);
+  struct hash_array *da = mn__untag_hash_array (dt->array);
 
   /* Let Sp be st->population, and Dp be dt->population, at present.
      After a copy, DEST's population will be at most Sp + Dp, and at
@@ -927,7 +881,7 @@
   if (dt->population >= da->length / 4)
     {
       resize (c, dt);
-      da = untag_hash_array (dt->array);
+      da = mn__untag_hash_array (dt->array);
     }
 
   /* If DEST's array has been disturbed by the collector, rehash it.
@@ -989,7 +943,7 @@
   mn__begin_incoherent (c);
   {
     struct hash_table *t = check_hash_table (hash_ref->obj);
-    struct hash_array *a = untag_hash_array (t->array);
+    struct hash_array *a = mn__untag_hash_array (t->array);
 
     stats->population = t->population;
     stats->size = a->length / 2;

Modified: trunk/gc/hash-tables.h
==============================================================================
--- trunk/gc/hash-tables.h	(original)
+++ trunk/gc/hash-tables.h	Tue Oct 24 05:38:55 2006
@@ -5,12 +5,63 @@
 
 #include "minor/essentials.h"
 
+
+/* The wrapper object for hash tables.  This part is not thrown away
+   when we resize a hash table.  */
+struct hash_table
+{
+  /* Attached label for this object.  */
+  tagged_t label;
+
+  /* The population of the hash table.  We re-size the hash table as
+     needed to keep the hash table between 1/8 and 1/2 occupancy.  At
+     1/2 occupancy, if the hash function distributes keys randomly
+     across the table, one expects to probe twice, on average, before
+     finding the right entry.  */
+  size_t population;
+
+  /* The number of times we've resized the table.  */
+  int resizings;
+
+  /* The table itself.  This is always a reference to a hash_array
+     object.  */
+  tagged_t array;
+};
+
+
+/* The actual hash array.  This part is replaced when we resize.  */
+struct hash_array
+{
+  /* Attached label for this object.  */
+  tagged_t label;
+
+  /* The length of the array.
+     This is in elements, not associations.  Divide by two to get 
+     the number of associations in the array.  */
+  size_t length;
+
+  /* A flag which the garbage collector sets when it scans the object,
+     possibly changing the addresses of the objects it contains.  */
+  bool scanned;
+
+  /* The elements.
+     These are actually key/value pairs ("associations"): even-indexed
+     elements are keys, and subsequent elements are values.  So the
+     whole hash array holds LENGTH / 2 key / value pairs.  */
+  tagged_t elements[];
+};
+     
+
 /* Return true if OBJ is a hash table, false otherwise.  */
 bool mn__is_hash_table (tagged_t obj);
 
 /* Return an empty eqv hash table.  */
 tagged_t mn__make_eqv_hash_table (mn_call_t *);
 
+/* Untag the hash tables and arrays.  */
+struct hash_table *mn__untag_hash_table (tagged_t table);
+struct hash_array *mn__untag_hash_array (tagged_t array);
+
 /* Associate VALUE with KEY in TABLE.  If TABLE is not a hash table,
    abort.  */
 void mn__hash_table_put (mn_call_t *,



More information about the Minor mailing list