![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to hash.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / make|
Return to hash.h CVS log | Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / make |
1.1 root 1: /*
2: * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
3: * Copyright (c) 1988, 1989 by Adam de Boor
4: * Copyright (c) 1989 by Berkeley Softworks
5: * All rights reserved.
6: *
7: * This code is derived from software contributed to Berkeley by
8: * Adam de Boor.
9: *
10: * Redistribution and use in source and binary forms are permitted
11: * provided that: (1) source distributions retain this entire copyright
12: * notice and comment, and (2) distributions including binaries display
13: * the following acknowledgement: ``This product includes software
14: * developed by the University of California, Berkeley and its contributors''
15: * in the documentation or other materials provided with the distribution
16: * and in all advertising materials mentioning features or use of this
17: * software. Neither the name of the University nor the names of its
18: * contributors may be used to endorse or promote products derived
19: * from this software without specific prior written permission.
20: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
21: * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
22: * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
23: *
24: * @(#)hash.h 5.3 (Berkeley) 6/1/90
25: */
26:
27: /* hash.h --
28: *
29: * This file contains definitions used by the hash module,
30: * which maintains hash tables.
31: */
32:
33: #ifndef _HASH
34: #define _HASH
35:
36: #include "list.h"
37: /*
38: * The following defines one entry in the hash table.
39: */
40:
41: typedef struct Hash_Entry {
42: List_Links links; /* Used to link together all the
43: * entries associated with the same
44: * bucket. */
45: ClientData clientData; /* Arbitrary piece of data associated
46: * with key. */
47: union {
48: Address ptr; /* One-word key value to identify
49: * entry. */
50: int words[1]; /* N-word key value. Note: the actual
51: * size may be longer if necessary to
52: * hold the entire key. */
53: char name[4]; /* Text name of this entry. Note: the
54: * actual size may be longer if
55: * necessary to hold the whole string.
56: * This MUST be the last entry in the
57: * structure!!! */
58: } key;
59: } Hash_Entry;
60:
61: /*
62: * A hash table consists of an array of pointers to hash
63: * lists. Tables can be organized in either of three ways, depending
64: * on the type of comparison keys:
65: *
66: * Strings: these are NULL-terminated; their address
67: * is passed to HashFind as a (char *).
68: * Single-word keys: these may be anything, but must be passed
69: * to Hash_Find as an Address.
70: * Multi-word keys: these may also be anything; their address
71: * is passed to HashFind as an Address.
72: *
73: * Single-word keys are fastest, but most restrictive.
74: */
75:
76: #define HASH_STRING_KEYS 0
77: #define HASH_ONE_WORD_KEYS 1
78:
79: typedef struct Hash_Table {
80: List_Links *bucketPtr; /* Pointer to array of List_Links, one
81: * for each bucket in the table. */
82: int size; /* Actual size of array. */
83: int numEntries; /* Number of entries in the table. */
84: int downShift; /* Shift count, used in hashing function. */
85: int mask; /* Used to select bits for hashing. */
86: int keyType; /* Type of keys used in table:
87: * HASH_STRING_KEYS, HASH_ONE-WORD_KEYS,
88: * or >1 menas keyType gives number of words
89: * in keys.
90: */
91: } Hash_Table;
92:
93: /*
94: * The following structure is used by the searching routines
95: * to record where we are in the search.
96: */
97:
98: typedef struct Hash_Search {
99: Hash_Table *tablePtr; /* Table being searched. */
100: int nextIndex; /* Next bucket to check (after current). */
101: Hash_Entry *hashEntryPtr; /* Next entry to check in current bucket. */
102: List_Links *hashList; /* Hash chain currently being checked. */
103: } Hash_Search;
104:
105: /*
106: * Macros.
107: */
108:
109: /*
110: * ClientData Hash_GetValue(h)
111: * Hash_Entry *h;
112: */
113:
114: #define Hash_GetValue(h) ((h)->clientData)
115:
116: /*
117: * Hash_SetValue(h, val);
118: * HashEntry *h;
119: * char *val;
120: */
121:
122: #define Hash_SetValue(h, val) ((h)->clientData = (ClientData) (val))
123:
124: /*
125: * Hash_Size(n) returns the number of words in an object of n bytes
126: */
127:
128: #define Hash_Size(n) (((n) + sizeof (int) - 1) / sizeof (int))
129:
130: /*
131: * The following procedure declarations and macros
132: * are the only things that should be needed outside
133: * the implementation code.
134: */
135:
136: extern Hash_Entry * Hash_CreateEntry();
137: extern void Hash_DeleteTable();
138: extern void Hash_DeleteEntry();
139: extern void Hash_DeleteTable();
140: extern Hash_Entry * Hash_EnumFirst();
141: extern Hash_Entry * Hash_EnumNext();
142: extern Hash_Entry * Hash_FindEntry();
143: extern void Hash_InitTable();
144: extern void Hash_PrintStats();
145:
146: #endif _HASH
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.