@@@ man wip

[mLib] / struct / hash.3

diff --git a/struct/hash.3 b/struct/hash.3
index c067275..fdde662 100644 (file)
--- a/struct/hash.3
+++ b/struct/hash.3
@@ -17,8 +17,18 @@
 \h'-\w'\\$1\ 'u'\\$1\ \c
 .ft P
 ..
-.ie t .ds o \(bu
-.el .ds o o
+.ie t \{\
+.  ds o \(bu
+.  de VP
+.    sp .4v
+..
+\}
+.el \{\
+.  ds o o
+.  de VP
+.    sp
+..
+\}
 .TH hash 3 "2 August 1999" "Straylight/Edgeware" "mLib utilities library"
 .SH "NAME"
 hash \- low-level hashtable implementation
@@ -37,21 +47,21 @@ hash \- low-level hashtable implementation
 .SH "SYNOPSIS"
 .nf
 .B "#include <mLib/hash.h>"
-
+.PP
 .ta 2n
 .B "typedef struct {"
 .B "   uint32 mask;"
 .B "   hash_base **v;"
 .B "   arena *a;"
 .B "} hash_table;"
-
+.PP
 .B "typedef struct {"
 .B "   hash_base *next;"
 .B "   uint32 hash;"
 .B "} hash_base;"
-
+.PP
 .B "typedef struct { ...\& } hash_iter;"
-
+.PP
 .BI "void hash_create(hash_table *" t ", size_t " n );
 .BI "void hash_destroy(hash_table *" t );
 .BI "hash_base **hash_bin(hash_table *" t ", uint32 " hash );
@@ -59,7 +69,7 @@ hash \- low-level hashtable implementation
 .BI "void hash_remove(hash_table *" t ", hash_base *" b );
 .BI "void hash_mkiter(hash_iter *" i ", hash_table *" t );
 .BI "hash_base *hash_next(hash_iter *" i );
-
+.PP
 .BI "hash_base **HASH_BIN(hash_table *" t ", uint32 " hash );
 .BI "void HASH_MKITER(hash_iter *" i ", hash_table *" t );
 .BI "void HASH_NEXT(hash_iter *" i ", " b );
@@ -135,19 +145,20 @@ This section describes the functions and macros provided for building
 hashtables.  Code examples are given throughout.  They assume the
 following definitions:
 .VS
+.ta 2n
 /* --- A table of items --- */
-
+.VP
 typedef struct item_table {
-  hash_table t;
-  size_t load;
+       hash_table t;
+       size_t load;
 };
-
+.VP
 /* --- An item --- */
-
+.VP
 typedef struct item {
-  hash_base b;
-  const char *k;
-  /* ... */
+       hash_base b;
+       const char *k;
+       /* ... */
 } item;
 .VE
 The implementation presented here is simple but relatively bad.  The
@@ -163,10 +174,11 @@ structure to be filled in and the initial number of hash bins to create.
 .PP
 For example, an item table might be initialized like this:
 .VS
+.ta 2n
 void item_createtab(item_table *t)
 {
-  hash_create(&t->t, ITEM_INITSZ);
-  t->load = ITEM_INITLOAD;
+       hash_create(&t->t, ITEM_INITSZ);
+       t->load = ITEM_INITLOAD;
 }
 .VE
 A hashtable can be destroyed by calling
@@ -179,17 +191,18 @@ that must be done beforehand.
 The usual way to deallocate the individual hashtable items is using the
 iteration constructs described below.
 .VS
+.ta 2n +2n
 void item_destroytab(item_table *t)
 {
-  hash_iter i;
-  hash_base *b;
-  for (hash_mkiter(&i, &t->t); (b = hash_next(&i)) != 0; ) {
-    item *ii = (item *)b;
-    free(ii->k);
-    /* ... */
-    DESTROY(ii);
-  }
-  hash_destroy(&t->t);
+       hash_iter i;
+       hash_base *b;
+       for (hash_mkiter(&i, &t->t); (b = hash_next(&i)) != 0; ) {
+               item *ii = (item *)b;
+               free(ii->k);
+               /* ... */
+               DESTROY(ii);
+       }
+       hash_destroy(&t->t);
 }
 .VE
 .sp -1
@@ -208,17 +221,18 @@ arguments multiple times.
 Once the bin list has been found, it's fairly easy to search for an
 exact match.  A simple search might look something like this:
 .VS
+.ta 2n +2n +2n 20m
 item *lookup(item_table *t, const char *k)
 {
-  uint32 h = hash(k);          /* Hash @k@ somehow */
-  hash_base **bin = HASH_BIN(&t->t, h);
-  hash_base *b;
-  for (b = *bin; b; b = b->next) {
-    item *i = (item *)b;
-    if (h == i->b.hash && strcmp(k, i->k) == 0)
-      return (i);
-  }
-  return (0);
+       uint32 h = hash(k);                     /* Hash \fIk\fP somehow */
+       hash_base **bin = HASH_BIN(&t->t, h);
+       hash_base *b;
+       for (b = *bin; b; b = b->next) {
+               item *i = (item *)b;
+               if (h == i->b.hash && strcmp(k, i->k) == 0)
+                       return (i);
+       }
+       return (0);
 }
 .VE
 Insertion is also relatively trivial given the bin list head.  Insertion
@@ -228,40 +242,41 @@ it.  Extension is performed by
 which is passed only the address of the hashtable.  It returns nonzero
 if extension was successful.
 .VS
+.ta 2n +2n
 item *add(item_table *t, const char *k, /* ... */)
 {
-  item *i;
-  uint32 h;
-  hash_base **bin;
-
-  /* --- See if the item is already there --- */
-
-  if ((i =  = lookup(t, k)) != 0)
-    return (i);
-
-  /* --- Make a new hashtable item --- */
-
-  i = CREATE(item);
-  i->k = xstrdup(k);
-  /* ... */
-
-  /* --- Link it into the bin list --- */
-
-  h = i->b.hash = hash(k);
-  bin = HASH_BIN(&t->t, h);
-  i->b.next = *bin;
-  *bin = &i->b.next;
-
-  /* --- Maybe extend the hashtable --- */
-
-  if (t->load)
-    t->load--;
-  else if (hash_extend(&t->t))
-    t->load = recalc_load(t);
-
-  /* --- Done --- */
-
-  return (i);
+       item *i;
+       uint32 h;
+       hash_base **bin;
+.VP
+       /* --- See if the item is already there --- */
+.VP
+       if ((i = lookup(t, k)) != 0)
+               return (i);
+.VP
+       /* --- Make a new hashtable item --- */
+.VP
+       i = CREATE(item);
+       i->k = xstrdup(k);
+       /* ... */
+.VP
+       /* --- Link it into the bin list --- */
+.VP
+       h = i->b.hash = hash(k);
+       bin = HASH_BIN(&t->t, h);
+       i->b.next = *bin;
+       *bin = &i->b.next;
+.VP
+       /* --- Maybe extend the hashtable --- */
+.VP
+       if (t->load)
+               t->load--;
+       else if (hash_extend(&t->t))
+               t->load = recalc_load(t);
+.VP
+       /* --- Done --- */
+.VP
+       return (i);
 }
 .VE
 The