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
|
/*
* Copyright (C) 2003 Serge van den Boom
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of version 2 of the GNU General Public License as
* published by the Free Software Foundation.
* Nota bene: later versions of the GNU General Public License do not apply
* to this program.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
// The 'already included' check must be done slightly more complicated
// than usually. This file may be included directly only once,
// but it may be included my derivative HashTable definitions that use
// this file as a template more than once.
#if !defined(_HASHTABLE_H) || defined(HASHTABLE_GENERIC)
#if defined(HASHTABLE_)
# define HASHTABLE_GENERIC
#endif
#include "types.h"
#include "uioport.h"
// Define to enable profiling.
#define HashTable_PROFILE
// You can use inline hash functions for extra speed, by using this file as
// a template.
// To do this, make a new .h and .c file. In the .h file, define the macros
// (and typedefs) from the HASHTABLE_ block below.
// In the .c file, #define HASHTABLE_INTERNAL, #include the .h file
// and hashtable.c (in this order), and add the necessary functions.
// If you do not need to free the Value, you can define HashTable_FREEVALUE
// as a no-op.
#ifndef HASHTABLE_
# define HASHTABLE_(identifier) HashTable ## _ ## identifier
typedef void HashTable_Key;
typedef void HashTable_Value;
# define HashTable_HASH(hashTable, hashValue) \
(hashTable)->hashFunction(hashValue)
# define HashTable_EQUAL(hashTable, hashKey1, hashKey2) \
(hashTable)->equalFunction(hashKey1, hashKey2)
# define HashTable_COPY(hashTable, hashKey) \
(hashTable)->copyFunction(hashKey)
# define HashTable_FREEKEY(hashTable, hashKey) \
(hashTable)->freeKeyFunction(hashKey)
# define HashTable_FREEVALUE(hashTable, hashValue) \
(hashTable)->freeValueFunction(hashValue)
#endif
typedef uio_uint32 (*HASHTABLE_(HashFunction))(const HASHTABLE_(Key) *);
typedef uio_bool (*HASHTABLE_(EqualFunction))(const HASHTABLE_(Key) *,
const HASHTABLE_(Key) *);
typedef HASHTABLE_(Value) *(*HASHTABLE_(CopyFunction))(
const HASHTABLE_(Key) *);
typedef void (*HASHTABLE_(FreeKeyFunction))(HASHTABLE_(Key) *);
typedef void (*HASHTABLE_(FreeValueFunction))(HASHTABLE_(Value) *);
typedef struct HASHTABLE_(HashTable) HASHTABLE_(HashTable);
typedef struct HASHTABLE_(HashEntry) HASHTABLE_(HashEntry);
typedef struct HASHTABLE_(Iterator) HASHTABLE_(Iterator);
struct HASHTABLE_(HashTable) {
HASHTABLE_(HashFunction) hashFunction;
// Function creating a uio_uint32 hash of a key.
HASHTABLE_(EqualFunction) equalFunction;
// Function used to compare two keys.
HASHTABLE_(CopyFunction) copyFunction;
// Function used to copy a key.
HASHTABLE_(FreeKeyFunction) freeKeyFunction;
// Function used to free a key.
HASHTABLE_(FreeValueFunction) freeValueFunction;
// Function used to free a value. Called when an entry is
// removed using the remove function, or for entries
// still in the HashTable when the HashTable is deleted.
double minFillQuotient;
// How much of half of the hashtable needs to be filled
// before resizing to size/2.
double maxFillQuotient;
// How much of the hashTable needs to be filled before
// resizing to size*2.
uio_uint32 minSize;
// Resize to size/2 when below this size.
uio_uint32 maxSize;
// Resize to size*2 when above this size.
uio_uint32 size;
// The number of buckets in the hash table.
uio_uint32 hashMask;
// Mask to take on a the calculated hash value, to make it
// fit into the table.
HASHTABLE_(HashEntry) **entries;
// The actual entries
uio_uint32 numEntries;
#ifdef HashTable_PROFILE
uio_uint32 numCollisions;
#endif
};
struct HASHTABLE_(HashEntry) {
uio_uint32 hash;
HASHTABLE_(Key) *key;
HASHTABLE_(Value) *value;
HASHTABLE_(HashEntry) *next;
};
struct HASHTABLE_(Iterator) {
const HASHTABLE_(HashTable) *hashTable;
uio_uint32 bucketNr;
HASHTABLE_(HashEntry) *entry;
};
HASHTABLE_(HashTable) *HASHTABLE_(newHashTable)(
HASHTABLE_(HashFunction) hashFunction,
HASHTABLE_(EqualFunction) equalFunction,
HASHTABLE_(CopyFunction) copyFunction,
HASHTABLE_(FreeKeyFunction) freeKeyFunction,
HASHTABLE_(FreeValueFunction) freeValueFunction,
uio_uint32 initialSize,
double minFillQuotient, double maxFillQuotient);
uio_bool HASHTABLE_(add)(HASHTABLE_(HashTable) *hashTable,
const HASHTABLE_(Key) *key, HASHTABLE_(Value) *value);
uio_bool HASHTABLE_(remove)(HASHTABLE_(HashTable) *hashTable,
const HASHTABLE_(Key) *key);
HASHTABLE_(Value) *HASHTABLE_(find)(
HASHTABLE_(HashTable) *hashTable, const HASHTABLE_(Key) *key);
uio_uint32 HASHTABLE_(count)(const HASHTABLE_(HashTable) *hashTable);
void HASHTABLE_(deleteHashTable)(HASHTABLE_(HashTable) *hashTable);
HASHTABLE_(Iterator) *HASHTABLE_(getIterator)(
const HASHTABLE_(HashTable) *hashTable);
int HASHTABLE_(iteratorDone)(const HASHTABLE_(Iterator) *iterator);
HASHTABLE_(Key) *HASHTABLE_(iteratorKey)(HASHTABLE_(Iterator) *iterator);
HASHTABLE_(Value) *HASHTABLE_(iteratorValue)(HASHTABLE_(Iterator) *iterator);
HASHTABLE_(Iterator) *HASHTABLE_(iteratorNext)(HASHTABLE_(Iterator) *iterator);
void HASHTABLE_(freeIterator)(HASHTABLE_(Iterator) *iterator);
#ifndef HASHTABLE_INTERNAL
# undef HASHTABLE_
#endif
#endif /* !defined(_HASHTABLE_H) || defined(HASHTABLE_GENERIC) */
|
