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
|
/*
* fcs_hash.h - header file of Freecell Solver's internal hash implementation.
*
* Written by Shlomi Fish (shlomif@vipe.technion.ac.il), 2000
*
* This file is in the public domain (it's uncopyrighted).
*/
#ifndef FC_SOLVE__FCS_HASH_H
#define FC_SOLVE__FCS_HASH_H
#ifdef __cplusplus
extern "C" {
#endif
#include "alloc.h"
#include "lookup2.h"
typedef int SFO_hash_value_t;
struct SFO_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 */
SFO_hash_value_t hash_value;
/*
* We also store a secondary hash value, which is not used for indexing,
* but is used to speed up comparison.
* */
SFO_hash_value_t secondary_hash_value;
/* The next item in the list */
struct SFO_hash_symlink_item_struct * next;
};
typedef struct SFO_hash_symlink_item_struct SFO_hash_symlink_item_t;
struct SFO_hash_symlink_struct
{
SFO_hash_symlink_item_t * first_item;
};
typedef struct SFO_hash_symlink_struct SFO_hash_symlink_t;
struct SFO_hash_struct
{
/* The vector of the hash table itself */
SFO_hash_symlink_t * entries;
/* A comparison function that can be used for comparing two keys
in the collection */
int (*compare_function)(const void * key1, const void * key2, void * context);
/* 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;
/* A context to pass to the comparison function */
void * context;
fcs_compact_allocator_t * allocator;
};
typedef struct SFO_hash_struct SFO_hash_t;
SFO_hash_t * freecell_solver_hash_init(
SFO_hash_value_t wanted_size,
int (*compare_function)(const void * key1, const void * key2, void * context),
void * context
);
void * freecell_solver_hash_insert(
SFO_hash_t * hash,
void * key,
SFO_hash_value_t hash_value,
SFO_hash_value_t secondary_hash_value,
int optimize_for_caching
);
void freecell_solver_hash_free(
SFO_hash_t * hash
);
void freecell_solver_hash_free_with_callback(
SFO_hash_t * hash,
void (*function_ptr)(void * key, void * context)
);
#ifdef __cplusplus
}
#endif
#endif /* FC_SOLVE__FCS_HASH_H */
|
