1 // This file is part of Freecell Solver. It is subject to the license terms in
2 // the COPYING.txt file found in the top-level directory of this distribution
3 // and at http://fc-solve.shlomifish.org/docs/distro/COPYING.html . No part of
4 // Freecell Solver, including this file, may be copied, modified, propagated,
5 // or distributed except according to the terms contained in the COPYING file.
6 //
7 // Copyright (c) 2000 Shlomi Fish
8 // fcs_hash.h - header file of Freecell Solver's internal hash implementation.
9 #pragma once
10
11 #ifdef __cplusplus
12 extern "C" {
13 #endif
14
15 #include "meta_alloc.h"
16 #include "rinutils/rinutils.h"
17
18 #ifdef FCS_INLINED_HASH_COMPARISON
19 enum FCS_INLINED_HASH_DATA_TYPE
20 {
21 FCS_INLINED_HASH__COLUMNS,
22 FCS_INLINED_HASH__STATES,
23 };
24 #endif
25
26 typedef size_t fcs_hash_value;
27
28 struct fc_solve_hash_symlink_item_struct
29 {
30 void *key;
31 // We also store the hash value corresponding to this key for faster
32 // comparisons
33 fcs_hash_value hash_value;
34 struct fc_solve_hash_symlink_item_struct *next;
35 };
36
37 typedef struct fc_solve_hash_symlink_item_struct hash_item;
38
39 typedef struct
40 {
41 hash_item *first_item;
42 } hash_table_entry;
43
44 struct fc_solve_instance_struct;
45
46 #ifndef FCS_INLINED_HASH_COMPARISON
47 #ifdef FCS_WITH_CONTEXT_VARIABLE
48 typedef int (*hash_compare_function)(
49 const void *const, const void *const, void *context);
50 #else
51 typedef int (*hash_compare_function)(const void *const, const void *const);
52 #endif
53 #endif
54
55 typedef struct
56 {
57 // The vector of the hash table itself
58 hash_table_entry *entries;
59 #ifndef FCS_WITHOUT_TRIM_MAX_STORED_STATES
60 // The list of vacant items as freed by the garbage collector. Use
61 // it before allocating more.
62 hash_item *list_of_vacant_items;
63 #endif
64 #ifdef FCS_INLINED_HASH_COMPARISON
65 enum FCS_INLINED_HASH_DATA_TYPE hash_type;
66 #else
67 hash_compare_function compare_function;
68 #ifdef FCS_WITH_CONTEXT_VARIABLE
69 // A context to pass to the comparison function
70 void *context;
71 #else
72 #endif
73 #endif
74
75 size_t size;
76
77 // A bit mask that extract the lowest bits out of the hash value
78 size_t size_bitmask;
79 // The number of elements stored inside the hash
80 size_t num_elems;
81
82 size_t max_num_elems_before_resize;
83
84 compact_allocator allocator;
85 #ifdef FCS_RCS_STATES
86 struct fc_solve_instance_struct *instance;
87 #endif
88 } hash_table;
89
fcs_hash_set_max_num_elems(hash_table * const hash,const size_t new_size)90 static inline void fcs_hash_set_max_num_elems(
91 hash_table *const hash, const size_t new_size)
92 {
93 hash->max_num_elems_before_resize = (new_size << 1);
94 }
95
fc_solve_hash_init(meta_allocator * const meta_alloc,hash_table * const hash,const enum FCS_INLINED_HASH_DATA_TYPE hash_type)96 static inline void fc_solve_hash_init(
97 meta_allocator *const meta_alloc, hash_table *const hash,
98 #ifdef FCS_INLINED_HASH_COMPARISON
99 const enum FCS_INLINED_HASH_DATA_TYPE hash_type
100 #else
101 hash_compare_function compare_function
102 #ifdef FCS_WITH_CONTEXT_VARIABLE
103 ,
104 void *const context
105 #else
106 #endif
107 #endif
108 )
109 {
110 const typeof(hash->size) initial_hash_size = 2048;
111
112 hash->size = initial_hash_size;
113 hash->size_bitmask = initial_hash_size - 1;
114 fcs_hash_set_max_num_elems(hash, initial_hash_size);
115
116 hash->num_elems = 0;
117
118 hash->entries =
119 (hash_table_entry *)calloc(initial_hash_size, sizeof(hash->entries[0]));
120
121 #ifndef FCS_WITHOUT_TRIM_MAX_STORED_STATES
122 hash->list_of_vacant_items = NULL;
123 #endif
124
125 #ifdef FCS_INLINED_HASH_COMPARISON
126 hash->hash_type = hash_type;
127 #else
128 hash->compare_function = compare_function;
129 #ifdef FCS_WITH_CONTEXT_VARIABLE
130 hash->context = context;
131 #endif
132 #endif
133
134 fc_solve_compact_allocator_init(&(hash->allocator), meta_alloc);
135 }
136
fc_solve_hash_recycle(hash_table * const hash)137 static inline void fc_solve_hash_recycle(hash_table *const hash)
138 {
139 fc_solve_compact_allocator_recycle(&(hash->allocator));
140 memset(hash->entries, '\0', sizeof(hash->entries[0]) * hash->size);
141 hash->num_elems = 0;
142 }
143
fc_solve_hash_free(hash_table * const hash)144 static inline void fc_solve_hash_free(hash_table *const hash)
145 {
146 fc_solve_compact_allocator_finish(&(hash->allocator));
147 free(hash->entries);
148 hash->entries = NULL;
149 }
150
151 #ifndef FCS_WITHOUT_TRIM_MAX_STORED_STATES
fc_solve_hash_foreach(hash_table * const hash,bool (* should_delete_ptr)(void * const key,void * const context),void * const context)152 static inline void fc_solve_hash_foreach(hash_table *const hash,
153 bool (*should_delete_ptr)(void *const key, void *const context),
154 void *const context)
155 {
156 const_SLOT(size, hash);
157 var_AUTO(entries, hash->entries);
158 for (size_t i = 0; i < size; ++i)
159 {
160 hash_item **item = &(entries[i].first_item);
161 while ((*item) != NULL)
162 {
163 if (should_delete_ptr((*item)->key, context))
164 {
165 hash_item *const next_item = (*item)->next;
166 (*item)->next = hash->list_of_vacant_items;
167 hash->list_of_vacant_items = (*item);
168 // Skip the item in the chain.
169 (*item) = next_item;
170
171 --(hash->num_elems);
172 }
173 else
174 {
175 item = &((*item)->next);
176 }
177 }
178 }
179 }
180 #endif
181
182 #ifdef __cplusplus
183 }
184 #endif
185