projects / unix-history / blobdiff
? search:
summary | tags | clone url | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
BSD 4_4 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 053ca53..9679a87 100644 (file)
--- a/usr/src/usr.bin/make/hash.h
+++ b/usr/src/usr.bin/make/hash.h
@@ -1,27 +1,41 @@
 /*
 /*
- * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
- * Copyright (c) 1988, 1989 by Adam de Boor
+ * Copyright (c) 1988, 1989, 1990, 1993
+ *     The Regents of the University of California.  All rights reserved.
  * Copyright (c) 1989 by Berkeley Softworks
  * All rights reserved.
  *
  * This code is derived from software contributed to Berkeley by
  * Adam de Boor.
  *
  * Copyright (c) 1989 by Berkeley Softworks
  * All rights reserved.
  *
  * This code is derived from software contributed to Berkeley by
  * Adam de Boor.
  *
- * 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.
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *     This product includes software developed by the University of
+ *     California, Berkeley and its contributors.
+ * 4. 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.
  *
  *
- *     @(#)hash.h      5.3 (Berkeley) 6/1/90
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *     @(#)hash.h      8.1 (Berkeley) 6/6/93
  */
 
 /* hash.h --
  */
 
 /* hash.h --
@@ -33,61 +47,26 @@
 #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 {
-    List_Links       links;            /* Used to link together all the
+    struct Hash_Entry *next;           /* 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. */
-    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;
+    unsigned         namehash;         /* hash value of key */
+    char             name[1];          /* key string */
 } 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 {
-    List_Links         *bucketPtr;     /* Pointer to array of List_Links, one
+    struct Hash_Entry **bucketPtr;/* Pointers to Hash_Entry, 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;
 
 /* 
@@ -99,7 +78,6 @@ 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;
 
 /*
@@ -115,7 +93,7 @@ typedef struct Hash_Search {
 
 /* 
  * Hash_SetValue(h, val); 
 
 /* 
  * Hash_SetValue(h, val); 
- *     HashEntry *h; 
+ *     Hash_Entry *h; 
  *     char *val; 
  */
 
  *     char *val; 
  */
 
@@ -127,20 +105,12 @@ typedef struct Hash_Search {
 
 #define        Hash_Size(n)    (((n) + sizeof (int) - 1) / sizeof (int))
 
 
 #define        Hash_Size(n)    (((n) + sizeof (int) - 1) / sizeof (int))
 
-/*
- * The following procedure declarations and macros
- * are the only things that should be needed outside
- * the implementation code.
- */
+Hash_Entry     *Hash_CreateEntry __P((Hash_Table *, char *, Boolean *));
+void            Hash_DeleteEntry __P((Hash_Table *, Hash_Entry *));
+void            Hash_DeleteTable __P((Hash_Table *));
+Hash_Entry     *Hash_EnumFirst __P((Hash_Table *, Hash_Search *));
+Hash_Entry     *Hash_EnumNext __P((Hash_Search *));
+Hash_Entry     *Hash_FindEntry __P((Hash_Table *, char *));
+void            Hash_InitTable __P((Hash_Table *, int));
 
 
-extern Hash_Entry *    Hash_CreateEntry();
-extern void            Hash_DeleteTable();
-extern void            Hash_DeleteEntry();
-extern void            Hash_DeleteTable();
-extern Hash_Entry *    Hash_EnumFirst();
-extern Hash_Entry *    Hash_EnumNext();
-extern Hash_Entry *    Hash_FindEntry();
-extern void            Hash_InitTable();
-extern void            Hash_PrintStats();
-
-#endif _HASH
+#endif /* _HASH */
Continuous source code history from original PDP-7 UNIX to FreeBSD 2, the first fully unencumbered FreeBSD release.