10 //#define HASH_DEBUG |
10 //#define HASH_DEBUG |
11 //#define HASH_STATS |
11 //#define HASH_STATS |
12 |
12 |
13 |
13 |
14 struct Queue; |
14 struct Queue; |
15 typedef bool Queue_PushProc(Queue* q, void* item, int priority); |
15 typedef bool Queue_PushProc(Queue *q, void *item, int priority); |
16 typedef void* Queue_PopProc(Queue* q); |
16 typedef void* Queue_PopProc(Queue *q); |
17 typedef bool Queue_DeleteProc(Queue* q, void* item, int priority); |
17 typedef bool Queue_DeleteProc(Queue *q, void* item, int priority); |
18 typedef void Queue_ClearProc(Queue* q, bool free_values); |
18 typedef void Queue_ClearProc(Queue *q, bool free_values); |
19 typedef void Queue_FreeProc(Queue* q, bool free_values); |
19 typedef void Queue_FreeProc(Queue *q, bool free_values); |
20 |
20 |
21 struct InsSortNode { |
21 struct InsSortNode { |
22 void* item; |
22 void *item; |
23 int priority; |
23 int priority; |
24 InsSortNode* next; |
24 InsSortNode* next; |
25 }; |
25 }; |
26 |
26 |
27 struct BinaryHeapNode { |
27 struct BinaryHeapNode { |
28 void* item; |
28 void *item; |
29 int priority; |
29 int priority; |
30 }; |
30 }; |
31 |
31 |
32 |
32 |
33 struct Queue{ |
33 struct Queue{ |
34 /* |
34 /* |
35 * Pushes an element into the queue, at the appropriate place for the queue. |
35 * Pushes an element into the queue, at the appropriate place for the queue. |
36 * Requires the queue pointer to be of an appropriate type, of course. |
36 * Requires the queue pointer to be of an appropriate type, of course. |
37 */ |
37 */ |
38 Queue_PushProc* push; |
38 Queue_PushProc *push; |
39 /* |
39 /* |
40 * Pops the first element from the queue. What exactly is the first element, |
40 * Pops the first element from the queue. What exactly is the first element, |
41 * is defined by the exact type of queue. |
41 * is defined by the exact type of queue. |
42 */ |
42 */ |
43 Queue_PopProc* pop; |
43 Queue_PopProc *pop; |
44 /* |
44 /* |
45 * Deletes the item from the queue. priority should be specified if |
45 * Deletes the item from the queue. priority should be specified if |
46 * known, which speeds up the deleting for some queue's. Should be -1 |
46 * known, which speeds up the deleting for some queue's. Should be -1 |
47 * if not known. |
47 * if not known. |
48 */ |
48 */ |
49 Queue_DeleteProc* del; |
49 Queue_DeleteProc *del; |
50 |
50 |
51 /* Clears the queue, by removing all values from it. It's state is |
51 /* Clears the queue, by removing all values from it. It's state is |
52 * effectively reset. If free_items is true, each of the items cleared |
52 * effectively reset. If free_items is true, each of the items cleared |
53 * in this way are free()'d. |
53 * in this way are free()'d. |
54 */ |
54 */ |
55 Queue_ClearProc* clear; |
55 Queue_ClearProc *clear; |
56 /* Frees the queue, by reclaiming all memory allocated by it. After |
56 /* Frees the queue, by reclaiming all memory allocated by it. After |
57 * this it is no longer usable. If free_items is true, any remaining |
57 * this it is no longer usable. If free_items is true, any remaining |
58 * items are free()'d too. |
58 * items are free()'d too. |
59 */ |
59 */ |
60 Queue_FreeProc* free; |
60 Queue_FreeProc *free; |
61 |
61 |
62 union { |
62 union { |
63 struct { |
63 struct { |
64 InsSortNode* first; |
64 InsSortNode *first; |
65 } inssort; |
65 } inssort; |
66 struct { |
66 struct { |
67 uint max_size; |
67 uint max_size; |
68 uint size; |
68 uint size; |
69 uint blocks; ///< The amount of blocks for which space is reserved in elements |
69 uint blocks; ///< The amount of blocks for which space is reserved in elements |
70 BinaryHeapNode** elements; |
70 BinaryHeapNode **elements; |
71 } binaryheap; |
71 } binaryheap; |
72 } data; |
72 } data; |
73 }; |
73 }; |
74 |
74 |
75 |
75 |
91 /* The amount of elements that will be malloc'd at a time */ |
91 /* The amount of elements that will be malloc'd at a time */ |
92 #define BINARY_HEAP_BLOCKSIZE_BITS 10 |
92 #define BINARY_HEAP_BLOCKSIZE_BITS 10 |
93 |
93 |
94 /** Initializes a binary heap and allocates internal memory for maximum of |
94 /** Initializes a binary heap and allocates internal memory for maximum of |
95 * max_size elements */ |
95 * max_size elements */ |
96 void init_BinaryHeap(Queue* q, uint max_size); |
96 void init_BinaryHeap(Queue *q, uint max_size); |
97 |
97 |
98 |
98 |
99 /* |
99 /* |
100 * Hash |
100 * Hash |
101 */ |
101 */ |
102 struct HashNode { |
102 struct HashNode { |
103 uint key1; |
103 uint key1; |
104 uint key2; |
104 uint key2; |
105 void* value; |
105 void *value; |
106 HashNode* next; |
106 HashNode *next; |
107 }; |
107 }; |
108 /** |
108 /** |
109 * Generates a hash code from the given key pair. You should make sure that |
109 * Generates a hash code from the given key pair. You should make sure that |
110 * the resulting range is clearly defined. |
110 * the resulting range is clearly defined. |
111 */ |
111 */ |
112 typedef uint Hash_HashProc(uint key1, uint key2); |
112 typedef uint Hash_HashProc(uint key1, uint key2); |
113 struct Hash { |
113 struct Hash { |
114 /* The hash function used */ |
114 /* The hash function used */ |
115 Hash_HashProc* hash; |
115 Hash_HashProc *hash; |
116 /* The amount of items in the hash */ |
116 /* The amount of items in the hash */ |
117 uint size; |
117 uint size; |
118 /* The number of buckets allocated */ |
118 /* The number of buckets allocated */ |
119 uint num_buckets; |
119 uint num_buckets; |
120 /* A pointer to an array of num_buckets buckets. */ |
120 /* A pointer to an array of num_buckets buckets. */ |
121 HashNode* buckets; |
121 HashNode *buckets; |
122 /* A pointer to an array of numbuckets booleans, which will be true if |
122 /* A pointer to an array of numbuckets booleans, which will be true if |
123 * there are any Nodes in the bucket */ |
123 * there are any Nodes in the bucket */ |
124 bool* buckets_in_use; |
124 bool *buckets_in_use; |
125 }; |
125 }; |
126 |
126 |
127 /* Call these function to manipulate a hash */ |
127 /* Call these function to manipulate a hash */ |
128 |
128 |
129 /** Deletes the value with the specified key pair from the hash and returns |
129 /** Deletes the value with the specified key pair from the hash and returns |
130 * that value. Returns NULL when the value was not present. The value returned |
130 * that value. Returns NULL when the value was not present. The value returned |
131 * is _not_ free()'d! */ |
131 * is _not_ free()'d! */ |
132 void* Hash_Delete(Hash* h, uint key1, uint key2); |
132 void *Hash_Delete(Hash *h, uint key1, uint key2); |
133 /** Sets the value associated with the given key pair to the given value. |
133 /** Sets the value associated with the given key pair to the given value. |
134 * Returns the old value if the value was replaced, NULL when it was not yet present. */ |
134 * Returns the old value if the value was replaced, NULL when it was not yet present. */ |
135 void* Hash_Set(Hash* h, uint key1, uint key2, void* value); |
135 void *Hash_Set(Hash *h, uint key1, uint key2, void *value); |
136 /** Gets the value associated with the given key pair, or NULL when it is not |
136 /** Gets the value associated with the given key pair, or NULL when it is not |
137 * present. */ |
137 * present. */ |
138 void* Hash_Get(const Hash* h, uint key1, uint key2); |
138 void *Hash_Get(const Hash *h, uint key1, uint key2); |
139 |
139 |
140 /* Call these function to create/destroy a hash */ |
140 /* Call these function to create/destroy a hash */ |
141 |
141 |
142 /** Builds a new hash in an existing struct. Make sure that hash() always |
142 /** Builds a new hash in an existing struct. Make sure that hash() always |
143 * returns a hash less than num_buckets! Call delete_hash after use */ |
143 * returns a hash less than num_buckets! Call delete_hash after use */ |
144 void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets); |
144 void init_Hash(Hash *h, Hash_HashProc *hash, uint num_buckets); |
145 /** |
145 /** |
146 * Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash |
146 * Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash |
147 * & friends. If free is true, it will call free() on all the values that |
147 * & friends. If free is true, it will call free() on all the values that |
148 * are left in the hash. |
148 * are left in the hash. |
149 */ |
149 */ |
150 void delete_Hash(Hash* h, bool free_values); |
150 void delete_Hash(Hash *h, bool free_values); |
151 /** |
151 /** |
152 * Cleans the hash, but keeps the memory allocated |
152 * Cleans the hash, but keeps the memory allocated |
153 */ |
153 */ |
154 void clear_Hash(Hash* h, bool free_values); |
154 void clear_Hash(Hash *h, bool free_values); |
155 /** |
155 /** |
156 * Gets the current size of the Hash |
156 * Gets the current size of the Hash |
157 */ |
157 */ |
158 uint Hash_Size(const Hash* h); |
158 uint Hash_Size(const Hash *h); |
159 |
159 |
160 #endif /* QUEUE_H */ |
160 #endif /* QUEUE_H */ |