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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
|
/* Copyright (c) 2000 Shlomi Fish
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/
/*
* fcs_hash.h - header file of Freecell Solver's internal hash implementation.
*
*/
#ifndef FC_SOLVE__FCS_HASH_H
#define FC_SOLVE__FCS_HASH_H
#ifdef __cplusplus
extern "C" {
#endif
#include "config.h"
#include "alloc.h"
#include "inline.h"
#include "bool.h"
#ifdef FCS_INLINED_HASH_COMPARISON
enum FCS_INLINED_HASH_DATA_TYPE
{
FCS_INLINED_HASH__COLUMNS,
FCS_INLINED_HASH__STATES,
};
#endif
typedef int fc_solve_hash_value_t;
struct fc_solve_hash_symlink_item_struct
{
/* A pointer to the data structure that is to be collected */
void * key;
/* We also store the hash value corresponding to this key for faster
comparisons */
fc_solve_hash_value_t hash_value;
#ifdef FCS_ENABLE_SECONDARY_HASH_VALUE
/*
* We also store a secondary hash value, which is not used for indexing,
* but is used to speed up comparison.
* */
fc_solve_hash_value_t secondary_hash_value;
#endif
/* The next item in the list */
struct fc_solve_hash_symlink_item_struct * next;
};
typedef struct fc_solve_hash_symlink_item_struct fc_solve_hash_symlink_item_t;
typedef struct
{
fc_solve_hash_symlink_item_t * first_item;
} fc_solve_hash_symlink_t;
struct fc_solve_instance_struct;
typedef struct
{
/* The vector of the hash table itself */
fc_solve_hash_symlink_t * entries;
/* The list of vacant items as freed by the garbage collector. Use
* if before allocating more. */
fc_solve_hash_symlink_item_t * list_of_vacant_items;
/* A comparison function that can be used for comparing two keys
in the collection */
#ifdef FCS_INLINED_HASH_COMPARISON
enum FCS_INLINED_HASH_DATA_TYPE hash_type;
#else
#ifdef FCS_WITH_CONTEXT_VARIABLE
int (*compare_function)(const void * key1, const void * key2, void * context);
/* A context to pass to the comparison function */
void * context;
#else
int (*compare_function)(const void * key1, const void * key2);
#endif
#endif
/* The size of the hash table */
int size;
/* A bit mask that extract the lowest bits out of the hash value */
int size_bitmask;
/* The number of elements stored inside the hash */
int num_elems;
int max_num_elems_before_resize;
fcs_compact_allocator_t allocator;
#ifdef FCS_RCS_STATES
struct fc_solve_instance_struct * instance;
#endif
} fc_solve_hash_t;
extern void
fc_solve_hash_init(
fc_solve_hash_t * hash,
#ifdef FCS_INLINED_HASH_COMPARISON
enum FCS_INLINED_HASH_DATA_TYPE hash_type
#else
#ifdef FCS_WITH_CONTEXT_VARIABLE
int (*compare_function)(const void * key1, const void * key2, void * context),
void * context
#else
int (*compare_function)(const void * key1, const void * key2)
#endif
#endif
);
/*
* Returns FALSE if the key is new and the key/val pair was inserted.
* - in that case *existing_key / *existing_val will be set to key
* and val respectively.
* Returns TRUE if the key is not new and *existing_key / *existing_val
* was set to it.
*/
extern fcs_bool_t fc_solve_hash_insert(
fc_solve_hash_t * hash,
void * key,
#ifdef FCS_RCS_STATES
void * key_id,
#endif
void * * existing_key,
fc_solve_hash_value_t hash_value
#ifdef FCS_ENABLE_SECONDARY_HASH_VALUE
, fc_solve_hash_value_t secondary_hash_value
#endif
);
static GCC_INLINE void fc_solve_hash_recycle(
fc_solve_hash_t * hash
)
{
memset(hash->entries, '\0', sizeof(hash->entries[0]) * hash->size);
hash->list_of_vacant_items = NULL;
hash->num_elems = 0;
fc_solve_compact_allocator_recycle(&(hash->allocator));
return;
}
static GCC_INLINE void fc_solve_hash_free(
fc_solve_hash_t * hash
)
{
fc_solve_compact_allocator_finish(&(hash->allocator));
free(hash->entries);
}
static GCC_INLINE void fc_solve_hash_foreach(
fc_solve_hash_t * hash,
fcs_bool_t (*should_delete_ptr)(void * key, void * context),
void * context
)
{
int i;
fc_solve_hash_symlink_item_t * * item;
fc_solve_hash_symlink_item_t * next_item;
for(i=0;i<hash->size;i++)
{
item = &(hash->entries[i].first_item);
while ((*item) != NULL)
{
if (should_delete_ptr((*item)->key, context))
{
next_item = (*item)->next;
/* Garbage collect (*item). TODO : actually make use of the
* items. */
(*item)->next = hash->list_of_vacant_items;
hash->list_of_vacant_items = (*item);
/* Skip the item in the chain. */
(*item) = next_item;
hash->num_elems--;
}
else
{
item = &((*item)->next);
}
}
}
}
#ifdef __cplusplus
}
#endif
#endif /* FC_SOLVE__FCS_HASH_H */
|