bin/bmake/hash.h

   1 /*      $NetBSD: hash.h,v 1.11 2016/06/07 00:40:00 sjg Exp $    */
   2
   3 /*
   4  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
   5  *
   6  * This code is derived from software contributed to Berkeley by
   7  * Adam de Boor.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  * 3. Neither the name of the University nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  *
  33  *      from: @(#)hash.h        8.1 (Berkeley) 6/6/93
  34  */
  35
  36 /*
  37  * Copyright (c) 1988, 1989 by Adam de Boor
  38  * Copyright (c) 1989 by Berkeley Softworks
  39  * All rights reserved.
  40  *
  41  * This code is derived from software contributed to Berkeley by
  42  * Adam de Boor.
  43  *
  44  * Redistribution and use in source and binary forms, with or without
  45  * modification, are permitted provided that the following conditions
  46  * are met:
  47  * 1. Redistributions of source code must retain the above copyright
  48  *    notice, this list of conditions and the following disclaimer.
  49  * 2. Redistributions in binary form must reproduce the above copyright
  50  *    notice, this list of conditions and the following disclaimer in the
  51  *    documentation and/or other materials provided with the distribution.
  52  * 3. All advertising materials mentioning features or use of this software
  53  *    must display the following acknowledgement:
  54  *      This product includes software developed by the University of
  55  *      California, Berkeley and its contributors.
  56  * 4. Neither the name of the University nor the names of its contributors
  57  *    may be used to endorse or promote products derived from this software
  58  *    without specific prior written permission.
  59  *
  60  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  61  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  62  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  63  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  64  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  65  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  66  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  67  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  68  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  69  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  70  * SUCH DAMAGE.
  71  *
  72  *      from: @(#)hash.h        8.1 (Berkeley) 6/6/93
  73  */
  74
  75 /* hash.h --
  76  *
  77  *      This file contains definitions used by the hash module,
  78  *      which maintains hash tables.
  79  */
  80
  81 #ifndef _HASH
  82 #define _HASH
  83
  84 /*
  85  * The following defines one entry in the hash table.
  86  */
  87
  88 typedef struct Hash_Entry {
  89     struct Hash_Entry *next;            /* Used to link together all the
  90                                          * entries associated with the same
  91                                          * bucket. */
  92     void              *clientPtr;       /* Arbitrary pointer */
  93     unsigned          namehash;         /* hash value of key */
  94     char              name[1];          /* key string */
  95 } Hash_Entry;
  96
  97 typedef struct Hash_Table {
  98     struct Hash_Entry **bucketPtr;/* Pointers to Hash_Entry, one
  99                                  * for each bucket in the table. */
 100     int         size;           /* Actual size of array. */
 101     int         numEntries;     /* Number of entries in the table. */
 102     int         mask;           /* Used to select bits for hashing. */
 103 } Hash_Table;
 104
 105 /*
 106  * The following structure is used by the searching routines
 107  * to record where we are in the search.
 108  */
 109
 110 typedef struct Hash_Search {
 111     Hash_Table  *tablePtr;      /* Table being searched. */
 112     int         nextIndex;      /* Next bucket to check (after current). */
 113     Hash_Entry  *hashEntryPtr;  /* Next entry to check in current bucket. */
 114 } Hash_Search;
 115
 116 /*
 117  * Macros.
 118  */
 119
 120 /*
 121  * void * Hash_GetValue(h)
 122  *     Hash_Entry *h;
 123  */
 124
 125 #define Hash_GetValue(h) ((h)->clientPtr)
 126
 127 /*
 128  * Hash_SetValue(h, val);
 129  *     Hash_Entry *h;
 130  *     char *val;
 131  */
 132
 133 #define Hash_SetValue(h, val) ((h)->clientPtr = (val))
 134
 135 /*
 136  * Hash_Size(n) returns the number of words in an object of n bytes
 137  */
 138
 139 #define Hash_Size(n)    (((n) + sizeof (int) - 1) / sizeof (int))
 140
 141 void Hash_InitTable(Hash_Table *, int);
 142 void Hash_DeleteTable(Hash_Table *);
 143 Hash_Entry *Hash_FindEntry(Hash_Table *, const char *);
 144 Hash_Entry *Hash_CreateEntry(Hash_Table *, const char *, Boolean *);
 145 void Hash_DeleteEntry(Hash_Table *, Hash_Entry *);
 146 Hash_Entry *Hash_EnumFirst(Hash_Table *, Hash_Search *);
 147 Hash_Entry *Hash_EnumNext(Hash_Search *);
 148
 149 #endif /* _HASH */