File: hash.h

package info (click to toggle)
yorick 1.4-14
  • links: PTS
  • area: main
  • in suites: potato
  • size: 5,948 kB
  • ctags: 6,609
  • sloc: ansic: 63,898; yacc: 889; makefile: 605; sh: 65; lisp: 60; fortran: 19
file content (171 lines) | stat: -rw-r--r-- 6,508 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
/*
   HASH.H
   Declare interface to hash routines

   $Id: hash.h,v 1.1 1993/08/27 18:32:09 munro Exp $
 */
/*    Copyright (c) 1994.  The Regents of the University of California.
                    All rights reserved.  */

#ifndef HASH_H
#define HASH_H

/* ------------------------------------------------------------------------ */

typedef struct HashTable HashTable;

extern long hashIndex;  /* set by HashFind, HashAdd, etc. */

extern int HashFind(const HashTable *table, const char *name, long n);
/* Note-- n is the exact length of name, or n==0 to use strlen(name)
   Usage:
     if (HashFind(table, name, n)) {
       ... name exists in table, and was the hashIndex +1st item
           added to the table ...
     } else {
       ... name does not exist, and hashIndex is the value of the
           hashing function (a slot index) ...
     }
 */

extern int HashAdd(HashTable *table, const char *name, long n);
/* Note-- n is the exact length of name, or n==0 to use strlen(name)
   Usage:
     if (HashAdd(table, name, n)) {
       ... name existed previously in table, as the hashIndex +1st item
           added to the table ...
     } else {
       ... name did not exist previously, and is now the hashIndex +1st
           item added to the table ...
       ... use the HASH_MANAGE macro to manage any lists associated with
           this hash table, in case they need to be lengthened ...
     }
   Note well: The name is copied if added to the table, so the caller
              should dispose of it as appropriate.
 */

/* ------------------------------------------------------------------------ */

extern int hashRealloc;  /* set by HashAdd if it returned 0 and if
			    the call forced table->maxItems to grow */

#define HASH_MANAGE(table, type, list) \
  if (hashRealloc) (list)= Yrealloc((list), (table).maxItems*sizeof(type))
/* NOTE: If you use this, you need to include defmem.h or otherwise
         declare Yrealloc (same semantics as ANSI standard realloc).
   Usage:
     HashTable table;   == associates name with index into table.names ==
     Object *list;      == typically, one or more lists in addition to
			   table.names are maintained representing the
			   objects which bear the names ==
     ...
     if (HashAdd(&table, name, n)) {
       == often, it is an error to add a duplicate name ==
     } else {
       HASH_MANAGE(table, Object, list);  == lengthen list if reqd ==
       list[hashIndex]= value_of_name;
     }
 */

/* ------------------------------------------------------------------------ */

extern void HashInit(HashTable *table, int estSize);
/* Pass HashInit the estimated final nItems for the table to bypass
   the rehashing which otherwise takes place every with every factor
   of two size increase.  A HashTable with all its members 0 is also
   a legal initialization; this is the situation after HashClear.  */

extern void HashClear(HashTable *table);
/* Clear a hash table, freeing all associated memory.  */

extern void HashShrink(HashTable *table);
/* Shrink maxItems to nItems, and rehash if the number of slots
   can be reduced.  Follow this with the HASH_MANAGE macro if the
   table has associated lists.  */

extern void HashRemove(HashTable *table, long index0);
/* Removing an item from a hash table is a very expensive operation,
   unless it is one of the few elements most recently added to the
   table.  The index0 must have been returned as the hashIndex for a
   previous call to HashFind or HashAdd.  */

extern void HashSwap(HashTable *table, long index0, long index1);
/* Swaps the item->index and names corresponding to the two
   entries, to reorder the names list after an incorrectly ordered
   sequence of calls to HashAdd.  */

/* ------------------------------------------------------------------------ */

typedef struct HashItem HashItem;

struct HashTable {
  long nItems, maxItems;  /* used and actual length of names array */
  char **names;
  long nSlots;            /* length of items, or number of hash slots */
  HashItem **items;
};

struct HashItem {
  HashItem *next;  /* next item in this hash slot */
  long index;      /* index into names array in associated HashTable */
};

/* ------------------------------------------------------------------------ */

typedef struct HashXTable HashXTable;
struct HashXTable {
  long nItems, maxItems;  /* used and actual length of names array */
  long nSlots;            /* length of items, or number of hash slots */
  HashItem **items;
};

extern int HashXFind(const HashXTable *table, const void *key, long n,
		     int (*Compare)(void *keyTable,
				    long index, const void *key),
		     void *keyTable);
/* Notes-- 1. n>0 is the exact length of key (uses HashN)
           2. Compare(keyTable, index, key) should return 0 when
	      the key matches the index-th entry of the keyTable
   Usage:
     if (HashXFind(table, key, n, Compare, keyTable)) {
       ... key exists in (table,keyTable), and was the hashIndex +1st
           item added to the table ...
     } else {
       ... key does not exist, and hashIndex is the value of the
           hashing function (a slot index) ...
     }
 */

extern int HashXAdd(HashXTable *table, const char *key, long n,
		    int (*Compare)(void *keyTable,
				   long index, const void *key),
		    void *(*Index)(void *keyTable, long index),
		    void *keyTable);
/* Notes-- 1. n>0 is the exact length of key (uses HashN)
           2. Compare(keyTable, index, key) should return 0 when
	      the key matches the index-th entry of the keyTable
           3. Index(keyTable, index) should return the key for
              the index-th entry of the keyTable (required for rehash)
   Usage:
     HashXTable *table;
     KeyedObject *keyTable;
     ...
     if (HashXAdd(table, name, n, Compare, Index, keyTable)) {
       ... key existed previously in table, as the hashIndex +1st item
           added to the table ...
     } else {
       ... key did not exist previously, and is now the hashIndex +1st
           item added to the table ...
       HASH_MANAGE(*table, KeyedObject, keyTable);
       keyTable[hashIndex]= object_corresponding_to_key;
       ... use the HASH_MANAGE macro to manage other lists associated with
           this hash table, in case they need to be lengthened ...
     }
 */

extern void HashXClear(HashXTable *table);
/* Clear a hash table, freeing all associated memory.  */

/* ------------------------------------------------------------------------ */

#endif