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
|
/* $Id$ */
#ifndef QUEUE_H
#define QUEUE_H
//#define NOFREE
//#define QUEUE_DEBUG
//#define HASH_DEBUG
//#define HASH_STATS
typedef struct Queue Queue;
typedef bool Queue_PushProc(Queue* q, void* item, int priority);
typedef void* Queue_PopProc(Queue* q);
typedef bool Queue_DeleteProc(Queue* q, void* item, int priority);
typedef void Queue_ClearProc(Queue* q, bool free_values);
typedef void Queue_FreeProc(Queue* q, bool free_values);
typedef struct InsSortNode InsSortNode;
struct InsSortNode {
void* item;
int priority;
InsSortNode* next;
};
typedef struct BinaryHeapNode BinaryHeapNode;
struct BinaryHeapNode {
void* item;
int priority;
};
struct Queue{
/*
* Pushes an element into the queue, at the appropriate place for the queue.
* Requires the queue pointer to be of an appropriate type, of course.
*/
Queue_PushProc* push;
/*
* Pops the first element from the queue. What exactly is the first element,
* is defined by the exact type of queue.
*/
Queue_PopProc* pop;
/*
* Deletes the item from the queue. priority should be specified if
* known, which speeds up the deleting for some queue's. Should be -1
* if not known.
*/
Queue_DeleteProc* del;
/* Clears the queue, by removing all values from it. It's state is
* effectively reset. If free_items is true, each of the items cleared
* in this way are free()'d.
*/
Queue_ClearProc* clear;
/* Frees the queue, by reclaiming all memory allocated by it. After
* this it is no longer usable. If free_items is true, any remaining
* items are free()'d too.
*/
Queue_FreeProc* free;
union {
struct {
uint max_size;
uint size;
void** elements;
} stack;
struct {
uint max_size;
uint head; /* The index where the last element should be inserted */
uint tail; /* The index where the next element should be read */
void** elements;
} fifo;
struct {
InsSortNode* first;
} inssort;
struct {
uint max_size;
uint size;
uint blocks; /* The amount of blocks for which space is reserved in elements */
BinaryHeapNode** elements;
} binaryheap;
} data;
/* If true, this struct will be free'd when the
* Queue is deleted. */
bool freeq;
};
/* Initializes a stack and allocates internal memory. */
void init_Stack(Queue* q, uint max_size);
/* Allocate a new stack with a maximum of max_size elements. */
Queue* new_Stack(uint max_size);
/*
* Fifo
*/
/* Initializes a fifo and allocates internal memory for maximum of max_size
* elements */
void init_Fifo(Queue* q, uint max_size);
/* Allocate a new fifo and initializes it with a maximum of max_size elements. */
Queue* new_Fifo(uint max_size);
Queue* new_Fifo_in_buffer(uint max_size, void* buffer);
int build_Fifo(void* buffer, uint size);
/*
* Insertion Sorter
*/
/* Initializes a inssort and allocates internal memory. There is no maximum
* size */
void init_InsSort(Queue* q);
/* Allocate a new fifo and initializes it. There is no maximum size */
Queue* new_InsSort(void);
/*
* Binary Heap
* For information, see:
* http://www.policyalmanac.org/games/binaryHeaps.htm
*/
/* The amount of elements that will be malloc'd at a time */
#define BINARY_HEAP_BLOCKSIZE_BITS 10
/* Initializes a binary heap and allocates internal memory for maximum of
* max_size elements */
void init_BinaryHeap(Queue* q, uint max_size);
/* Allocate a new binary heap and initializes it with a maximum of max_size
* elements. */
Queue* new_BinaryHeap(uint max_size);
/*
* Hash
*/
typedef struct HashNode HashNode;
struct HashNode {
uint key1;
uint key2;
void* value;
HashNode* next;
};
/**
* Generates a hash code from the given key pair. You should make sure that
* the resulting range is clearly defined.
*/
typedef uint Hash_HashProc(uint key1, uint key2);
typedef struct Hash {
/* The hash function used */
Hash_HashProc* hash;
/* The amount of items in the hash */
uint size;
/* The number of buckets allocated */
uint num_buckets;
/* A pointer to an array of num_buckets buckets. */
HashNode* buckets;
/* A pointer to an array of numbuckets booleans, which will be true if
* there are any Nodes in the bucket */
bool* buckets_in_use;
/* If true, buckets will be freed in delete_hash */
bool freeb;
/* If true, the pointer to this struct will be freed in delete_hash */
bool freeh;
} Hash;
/* Call these function to manipulate a hash */
/* Deletes the value with the specified key pair from the hash and returns
* that value. Returns NULL when the value was not present. The value returned
* is _not_ free()'d! */
void* Hash_Delete(Hash* h, uint key1, uint key2);
/* Sets the value associated with the given key pair to the given value.
* Returns the old value if the value was replaced, NULL when it was not yet present. */
void* Hash_Set(Hash* h, uint key1, uint key2, void* value);
/* Gets the value associated with the given key pair, or NULL when it is not
* present. */
void* Hash_Get(const Hash* h, uint key1, uint key2);
/* Call these function to create/destroy a hash */
/* Builds a new hash, with num_buckets buckets. Make sure that hash() always
* returns a hash less than num_buckets! Call delete_hash after use */
Hash* new_Hash(Hash_HashProc* hash, int num_buckets);
/* Builds a new hash in an existing struct. Make sure that hash() always
* returns a hash less than num_buckets! Call delete_hash after use */
void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets);
/*
* Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash
* & friends. If free is true, it will call free() on all the values that
* are left in the hash.
*/
void delete_Hash(Hash* h, bool free_values);
/*
* Cleans the hash, but keeps the memory allocated
*/
void clear_Hash(Hash* h, bool free_values);
/*
* Gets the current size of the Hash
*/
uint Hash_Size(const Hash* h);
#endif /* QUEUE_H */
|
