usr.bin/make/hash.h

   1 /*      $NetBSD: hash.h,v 1.9 2009/01/23 21:26:30 dsl 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     union {
  93         void          *clientPtr;       /* Arbitrary pointer */
  94         time_t        clientTime;       /* Arbitrary Time */
  95     } clientInfo;
  96     unsigned          namehash;         /* hash value of key */
  97     char              name[1];          /* key string */
  98 } Hash_Entry;
  99
 100 typedef struct Hash_Table {
 101     struct Hash_Entry **bucketPtr;/* Pointers to Hash_Entry, one
 102                                  * for each bucket in the table. */
 103     int         size;           /* Actual size of array. */
 104     int         numEntries;     /* Number of entries in the table. */
 105     int         mask;           /* Used to select bits for hashing. */
 106 } Hash_Table;
 107
 108 /*
 109  * The following structure is used by the searching routines
 110  * to record where we are in the search.
 111  */
 112
 113 typedef struct Hash_Search {
 114     Hash_Table  *tablePtr;      /* Table being searched. */
 115     int         nextIndex;      /* Next bucket to check (after current). */
 116     Hash_Entry  *hashEntryPtr;  /* Next entry to check in current bucket. */
 117 } Hash_Search;
 118
 119 /*
 120  * Macros.
 121  */
 122
 123 /*
 124  * void * Hash_GetValue(h)
 125  *     Hash_Entry *h;
 126  */
 127
 128 #define Hash_GetValue(h) ((h)->clientInfo.clientPtr)
 129 #define Hash_GetTimeValue(h) ((h)->clientInfo.clientTime)
 130
 131 /*
 132  * Hash_SetValue(h, val);
 133  *     Hash_Entry *h;
 134  *     char *val;
 135  */
 136
 137 #define Hash_SetValue(h, val) ((h)->clientInfo.clientPtr = (val))
 138 #define Hash_SetTimeValue(h, val) ((h)->clientInfo.clientTime = (val))
 139
 140 /*
 141  * Hash_Size(n) returns the number of words in an object of n bytes
 142  */
 143
 144 #define Hash_Size(n)    (((n) + sizeof (int) - 1) / sizeof (int))
 145
 146 void Hash_InitTable(Hash_Table *, int);
 147 void Hash_DeleteTable(Hash_Table *);
 148 Hash_Entry *Hash_FindEntry(Hash_Table *, const char *);
 149 Hash_Entry *Hash_CreateEntry(Hash_Table *, const char *, Boolean *);
 150 void Hash_DeleteEntry(Hash_Table *, Hash_Entry *);
 151 Hash_Entry *Hash_EnumFirst(Hash_Table *, Hash_Search *);
 152 Hash_Entry *Hash_EnumNext(Hash_Search *);
 153
 154 #endif /* _HASH */