59 */ |
59 */ |
60 Queue_FreeProc* free; |
60 Queue_FreeProc* free; |
61 |
61 |
62 union { |
62 union { |
63 struct { |
63 struct { |
64 uint max_size; |
|
65 uint size; |
|
66 void** elements; |
|
67 } stack; |
|
68 struct { |
|
69 uint max_size; |
|
70 uint head; /* The index where the last element should be inserted */ |
|
71 uint tail; /* The index where the next element should be read */ |
|
72 void** elements; |
|
73 } fifo; |
|
74 struct { |
|
75 InsSortNode* first; |
64 InsSortNode* first; |
76 } inssort; |
65 } inssort; |
77 struct { |
66 struct { |
78 uint max_size; |
67 uint max_size; |
79 uint size; |
68 uint size; |
80 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 */ |
81 BinaryHeapNode** elements; |
70 BinaryHeapNode** elements; |
82 } binaryheap; |
71 } binaryheap; |
83 } data; |
72 } data; |
84 |
|
85 /* If true, this struct will be free'd when the |
|
86 * Queue is deleted. */ |
|
87 bool freeq; |
|
88 }; |
73 }; |
89 |
74 |
90 /* Initializes a stack and allocates internal memory. */ |
|
91 void init_Stack(Queue* q, uint max_size); |
|
92 |
|
93 /* Allocate a new stack with a maximum of max_size elements. */ |
|
94 Queue* new_Stack(uint max_size); |
|
95 |
|
96 /* |
|
97 * Fifo |
|
98 */ |
|
99 |
|
100 /* Initializes a fifo and allocates internal memory for maximum of max_size |
|
101 * elements */ |
|
102 void init_Fifo(Queue* q, uint max_size); |
|
103 |
|
104 /* Allocate a new fifo and initializes it with a maximum of max_size elements. */ |
|
105 Queue* new_Fifo(uint max_size); |
|
106 |
|
107 Queue* new_Fifo_in_buffer(uint max_size, void* buffer); |
|
108 |
|
109 int build_Fifo(void* buffer, uint size); |
|
110 |
75 |
111 /* |
76 /* |
112 * Insertion Sorter |
77 * Insertion Sorter |
113 */ |
78 */ |
114 |
79 |
115 /* Initializes a inssort and allocates internal memory. There is no maximum |
80 /* Initializes a inssort and allocates internal memory. There is no maximum |
116 * size */ |
81 * size */ |
117 void init_InsSort(Queue* q); |
82 void init_InsSort(Queue* q); |
118 |
83 |
119 /* Allocate a new fifo and initializes it. There is no maximum size */ |
|
120 Queue* new_InsSort(void); |
|
121 |
84 |
122 /* |
85 /* |
123 * Binary Heap |
86 * Binary Heap |
124 * For information, see: |
87 * For information, see: |
125 * http://www.policyalmanac.org/games/binaryHeaps.htm |
88 * http://www.policyalmanac.org/games/binaryHeaps.htm |
130 |
93 |
131 /* Initializes a binary heap and allocates internal memory for maximum of |
94 /* Initializes a binary heap and allocates internal memory for maximum of |
132 * max_size elements */ |
95 * max_size elements */ |
133 void init_BinaryHeap(Queue* q, uint max_size); |
96 void init_BinaryHeap(Queue* q, uint max_size); |
134 |
97 |
135 /* Allocate a new binary heap and initializes it with a maximum of max_size |
|
136 * elements. */ |
|
137 Queue* new_BinaryHeap(uint max_size); |
|
138 |
98 |
139 /* |
99 /* |
140 * Hash |
100 * Hash |
141 */ |
101 */ |
142 typedef struct HashNode HashNode; |
102 typedef struct HashNode HashNode; |
161 /* A pointer to an array of num_buckets buckets. */ |
121 /* A pointer to an array of num_buckets buckets. */ |
162 HashNode* buckets; |
122 HashNode* buckets; |
163 /* A pointer to an array of numbuckets booleans, which will be true if |
123 /* A pointer to an array of numbuckets booleans, which will be true if |
164 * there are any Nodes in the bucket */ |
124 * there are any Nodes in the bucket */ |
165 bool* buckets_in_use; |
125 bool* buckets_in_use; |
166 /* If true, buckets will be freed in delete_hash */ |
|
167 bool freeb; |
|
168 /* If true, the pointer to this struct will be freed in delete_hash */ |
|
169 bool freeh; |
|
170 } Hash; |
126 } Hash; |
171 |
127 |
172 /* Call these function to manipulate a hash */ |
128 /* Call these function to manipulate a hash */ |
173 |
129 |
174 /* Deletes the value with the specified key pair from the hash and returns |
130 /* Deletes the value with the specified key pair from the hash and returns |
182 * present. */ |
138 * present. */ |
183 void* Hash_Get(const Hash* h, uint key1, uint key2); |
139 void* Hash_Get(const Hash* h, uint key1, uint key2); |
184 |
140 |
185 /* Call these function to create/destroy a hash */ |
141 /* Call these function to create/destroy a hash */ |
186 |
142 |
187 /* Builds a new hash, with num_buckets buckets. Make sure that hash() always |
|
188 * returns a hash less than num_buckets! Call delete_hash after use */ |
|
189 Hash* new_Hash(Hash_HashProc* hash, int num_buckets); |
|
190 /* Builds a new hash in an existing struct. Make sure that hash() always |
143 /* Builds a new hash in an existing struct. Make sure that hash() always |
191 * returns a hash less than num_buckets! Call delete_hash after use */ |
144 * returns a hash less than num_buckets! Call delete_hash after use */ |
192 void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets); |
145 void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets); |
193 /* |
146 /* |
194 * Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash |
147 * Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash |