@@@ 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
 ..
 \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
 .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>"
 .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;"
 .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;"
 .B "typedef struct {"
 .B "   hash_base *next;"
 .B "   uint32 hash;"
 .B "} hash_base;"

-
+.PP

 .B "typedef struct { ...\& } hash_iter;"
 .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 );
 .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 );
 .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 );
 .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
 hashtables.  Code examples are given throughout.  They assume the
 following definitions:
 .VS

+.ta 2n

 /* --- A table of items --- */
 /* --- A table of items --- */

-
+.VP

 typedef struct item_table {
 typedef struct item_table {

-  hash_table t;
-  size_t load;
+       hash_table t;
+       size_t load;

 };
 };

-
+.VP

 /* --- An item --- */
 /* --- An item --- */

-
+.VP

 typedef struct item {
 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
 } 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
 .PP
 For example, an item table might be initialized like this:
 .VS

+.ta 2n

 void item_createtab(item_table *t)
 {
 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
 }
 .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
 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)
 {
 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
 }
 .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
 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)
 {
 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
 }
 .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
 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 *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
 }
 .VE
 The