BSD 4_3_Reno release

[unix-history] / usr / src / usr.bin / make / hash.h

diff --git a/usr/src/usr.bin/make/hash.h b/usr/src/usr.bin/make/hash.h
index 7156981..053ca53 100644 (file)
--- a/usr/src/usr.bin/make/hash.h
+++ b/usr/src/usr.bin/make/hash.h
@@ -7,9 +7,21 @@
  * This code is derived from software contributed to Berkeley by
  * Adam de Boor.
  *
  * This code is derived from software contributed to Berkeley by
  * Adam de Boor.
  *

- * %sccs.include.redist.c%
+ * Redistribution and use in source and binary forms are permitted
+ * provided that: (1) source distributions retain this entire copyright
+ * notice and comment, and (2) distributions including binaries display
+ * the following acknowledgement:  ``This product includes software
+ * developed by the University of California, Berkeley and its contributors''
+ * in the documentation or other materials provided with the distribution
+ * and in all advertising materials mentioning features or use of this
+ * software. Neither the name of the University nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.

  *
  *

- *     @(#)hash.h      5.4 (Berkeley) %G%
+ *     @(#)hash.h      5.3 (Berkeley) 6/1/90

  */
 
 /* hash.h --
  */
 
 /* hash.h --


@@ -21,26 +33,61 @@
 #ifndef        _HASH
 #define        _HASH
 
 #ifndef        _HASH
 #define        _HASH
 

+#include "list.h"

 /* 
  * The following defines one entry in the hash table.
  */
 
 typedef struct Hash_Entry {
 /* 
  * The following defines one entry in the hash table.
  */
 
 typedef struct Hash_Entry {

-    struct Hash_Entry *next;           /* Used to link together all the
+    List_Links       links;            /* Used to link together all the

                                         * entries associated with the same
                                         * bucket. */
     ClientData       clientData;       /* Arbitrary piece of data associated
                                         * with key. */
                                         * entries associated with the same
                                         * bucket. */
     ClientData       clientData;       /* Arbitrary piece of data associated
                                         * with key. */

-    unsigned         namehash;         /* hash value of key */
-    char             name[1];          /* key string */
+    union {
+       Address  ptr;                   /* One-word key value to identify
+                                        * entry. */
+       int words[1];                   /* N-word key value.  Note: the actual
+                                        * size may be longer if necessary to
+                                        * hold the entire key. */
+       char     name[4];               /* Text name of this entry.  Note: the
+                                        * actual size may be longer if
+                                        * necessary to hold the whole string.
+                                        * This MUST be the last entry in the
+                                        * structure!!! */
+    } key;

 } Hash_Entry;
 
 } Hash_Entry;
 

+/* 
+ * A hash table consists of an array of pointers to hash
+ * lists.  Tables can be organized in either of three ways, depending
+ * on the type of comparison keys:
+ *
+ *     Strings:          these are NULL-terminated; their address
+ *                       is passed to HashFind as a (char *).
+ *     Single-word keys: these may be anything, but must be passed
+ *                       to Hash_Find as an Address.
+ *     Multi-word keys:  these may also be anything; their address
+ *                       is passed to HashFind as an Address.
+ *
+ *     Single-word keys are fastest, but most restrictive.
+ */
+ 
+#define HASH_STRING_KEYS       0
+#define HASH_ONE_WORD_KEYS     1
+

 typedef struct Hash_Table {
 typedef struct Hash_Table {

-    struct Hash_Entry **bucketPtr;/* Pointers to Hash_Entry, one
+    List_Links         *bucketPtr;     /* Pointer to array of List_Links, one

                                 * for each bucket in the table. */
     int        size;           /* Actual size of array. */
     int        numEntries;     /* Number of entries in the table. */
                                 * for each bucket in the table. */
     int        size;           /* Actual size of array. */
     int        numEntries;     /* Number of entries in the table. */

+    int        downShift;      /* Shift count, used in hashing function. */

     int        mask;           /* Used to select bits for hashing. */
     int        mask;           /* Used to select bits for hashing. */

+    int        keyType;        /* Type of keys used in table:
+                                * HASH_STRING_KEYS, HASH_ONE-WORD_KEYS,
+                                * or >1 menas keyType gives number of words
+                                * in keys.
+                                */

 } Hash_Table;
 
 /* 
 } Hash_Table;
 
 /* 


@@ -52,6 +99,7 @@ typedef struct Hash_Search {
     Hash_Table  *tablePtr;     /* Table being searched. */
     int        nextIndex;      /* Next bucket to check (after current). */
     Hash_Entry         *hashEntryPtr;  /* Next entry to check in current bucket. */
     Hash_Table  *tablePtr;     /* Table being searched. */
     int        nextIndex;      /* Next bucket to check (after current). */
     Hash_Entry         *hashEntryPtr;  /* Next entry to check in current bucket. */

+    List_Links *hashList;      /* Hash chain currently being checked. */

 } Hash_Search;
 
 /*
 } Hash_Search;
 
 /*


@@ -67,7 +115,7 @@ typedef struct Hash_Search {
 
 /* 
  * Hash_SetValue(h, val); 
 
 /* 
  * Hash_SetValue(h, val); 

- *     Hash_Entry *h; 
+ *     HashEntry *h; 

  *     char *val; 
  */
 
  *     char *val; 
  */