2 |
2 |
3 #include "stdafx.h" |
3 #include "stdafx.h" |
4 #include "openttd.h" |
4 #include "openttd.h" |
5 #include "queue.h" |
5 #include "queue.h" |
6 #include "helpers.hpp" |
6 #include "helpers.hpp" |
7 |
|
8 static void Stack_Clear(Queue* q, bool free_values) |
|
9 { |
|
10 if (free_values) { |
|
11 uint i; |
|
12 |
|
13 for (i = 0; i < q->data.stack.size; i++) free(q->data.stack.elements[i]); |
|
14 } |
|
15 q->data.stack.size = 0; |
|
16 } |
|
17 |
|
18 static void Stack_Free(Queue* q, bool free_values) |
|
19 { |
|
20 q->clear(q, free_values); |
|
21 free(q->data.stack.elements); |
|
22 if (q->freeq) free(q); |
|
23 } |
|
24 |
|
25 static bool Stack_Push(Queue* q, void* item, int priority) |
|
26 { |
|
27 if (q->data.stack.size == q->data.stack.max_size) return false; |
|
28 q->data.stack.elements[q->data.stack.size++] = item; |
|
29 return true; |
|
30 } |
|
31 |
|
32 static void* Stack_Pop(Queue* q) |
|
33 { |
|
34 if (q->data.stack.size == 0) return NULL; |
|
35 return q->data.stack.elements[--q->data.stack.size]; |
|
36 } |
|
37 |
|
38 static bool Stack_Delete(Queue* q, void* item, int priority) |
|
39 { |
|
40 return false; |
|
41 } |
|
42 |
|
43 static Queue* init_stack(Queue* q, uint max_size) |
|
44 { |
|
45 q->push = Stack_Push; |
|
46 q->pop = Stack_Pop; |
|
47 q->del = Stack_Delete; |
|
48 q->clear = Stack_Clear; |
|
49 q->free = Stack_Free; |
|
50 q->data.stack.max_size = max_size; |
|
51 q->data.stack.size = 0; |
|
52 q->data.stack.elements = MallocT<void*>(max_size); |
|
53 q->freeq = false; |
|
54 return q; |
|
55 } |
|
56 |
|
57 Queue* new_Stack(uint max_size) |
|
58 { |
|
59 Queue* q = MallocT<Queue>(1); |
|
60 |
|
61 init_stack(q, max_size); |
|
62 q->freeq = true; |
|
63 return q; |
|
64 } |
|
65 |
|
66 /* |
|
67 * Fifo |
|
68 */ |
|
69 |
|
70 static void Fifo_Clear(Queue* q, bool free_values) |
|
71 { |
|
72 if (free_values) { |
|
73 uint head = q->data.fifo.head; |
|
74 uint tail = q->data.fifo.tail; /* cache for speed */ |
|
75 |
|
76 while (head != tail) { |
|
77 free(q->data.fifo.elements[tail]); |
|
78 tail = (tail + 1) % q->data.fifo.max_size; |
|
79 } |
|
80 } |
|
81 q->data.fifo.head = 0; |
|
82 q->data.fifo.tail = 0; |
|
83 } |
|
84 |
|
85 static void Fifo_Free(Queue* q, bool free_values) |
|
86 { |
|
87 q->clear(q, free_values); |
|
88 free(q->data.fifo.elements); |
|
89 if (q->freeq) free(q); |
|
90 } |
|
91 |
|
92 static bool Fifo_Push(Queue* q, void* item, int priority) |
|
93 { |
|
94 uint next = (q->data.fifo.head + 1) % q->data.fifo.max_size; |
|
95 |
|
96 if (next == q->data.fifo.tail) return false; |
|
97 q->data.fifo.elements[q->data.fifo.head] = item; |
|
98 |
|
99 q->data.fifo.head = next; |
|
100 return true; |
|
101 } |
|
102 |
|
103 static void* Fifo_Pop(Queue* q) |
|
104 { |
|
105 void* result; |
|
106 |
|
107 if (q->data.fifo.head == q->data.fifo.tail) return NULL; |
|
108 result = q->data.fifo.elements[q->data.fifo.tail]; |
|
109 |
|
110 q->data.fifo.tail = (q->data.fifo.tail + 1) % q->data.fifo.max_size; |
|
111 return result; |
|
112 } |
|
113 |
|
114 static bool Fifo_Delete(Queue* q, void* item, int priority) |
|
115 { |
|
116 return false; |
|
117 } |
|
118 |
|
119 static Queue* init_fifo(Queue* q, uint max_size) |
|
120 { |
|
121 q->push = Fifo_Push; |
|
122 q->pop = Fifo_Pop; |
|
123 q->del = Fifo_Delete; |
|
124 q->clear = Fifo_Clear; |
|
125 q->free = Fifo_Free; |
|
126 q->data.fifo.max_size = max_size; |
|
127 q->data.fifo.head = 0; |
|
128 q->data.fifo.tail = 0; |
|
129 q->data.fifo.elements = MallocT<void*>(max_size); |
|
130 q->freeq = false; |
|
131 return q; |
|
132 } |
|
133 |
|
134 Queue* new_Fifo(uint max_size) |
|
135 { |
|
136 Queue* q = MallocT<Queue>(1); |
|
137 init_fifo(q, max_size); |
|
138 q->freeq = true; |
|
139 return q; |
|
140 } |
|
141 |
7 |
142 |
8 |
143 /* |
9 /* |
144 * Insertion Sorter |
10 * Insertion Sorter |
145 */ |
11 */ |
282 for (i = 0; i < q->data.binaryheap.blocks; i++) { |
137 for (i = 0; i < q->data.binaryheap.blocks; i++) { |
283 if (q->data.binaryheap.elements[i] == NULL) break; |
138 if (q->data.binaryheap.elements[i] == NULL) break; |
284 free(q->data.binaryheap.elements[i]); |
139 free(q->data.binaryheap.elements[i]); |
285 } |
140 } |
286 free(q->data.binaryheap.elements); |
141 free(q->data.binaryheap.elements); |
287 if (q->freeq) free(q); |
|
288 } |
142 } |
289 |
143 |
290 static bool BinaryHeap_Push(Queue* q, void* item, int priority) |
144 static bool BinaryHeap_Push(Queue* q, void* item, int priority) |
291 { |
145 { |
292 #ifdef QUEUE_DEBUG |
146 #ifdef QUEUE_DEBUG |
428 // We malloc memory in block of BINARY_HEAP_BLOCKSIZE |
282 // We malloc memory in block of BINARY_HEAP_BLOCKSIZE |
429 // It autosizes when it runs out of memory |
283 // It autosizes when it runs out of memory |
430 q->data.binaryheap.elements = CallocT<BinaryHeapNode*>((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1); |
284 q->data.binaryheap.elements = CallocT<BinaryHeapNode*>((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1); |
431 q->data.binaryheap.elements[0] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE); |
285 q->data.binaryheap.elements[0] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE); |
432 q->data.binaryheap.blocks = 1; |
286 q->data.binaryheap.blocks = 1; |
433 q->freeq = false; |
|
434 #ifdef QUEUE_DEBUG |
287 #ifdef QUEUE_DEBUG |
435 printf("[BinaryHeap] Initial size of elements is %d nodes\n", BINARY_HEAP_BLOCKSIZE); |
288 printf("[BinaryHeap] Initial size of elements is %d nodes\n", BINARY_HEAP_BLOCKSIZE); |
436 #endif |
289 #endif |
437 } |
|
438 |
|
439 Queue* new_BinaryHeap(uint max_size) |
|
440 { |
|
441 Queue* q = MallocT<Queue>(1); |
|
442 |
|
443 init_BinaryHeap(q, max_size); |
|
444 q->freeq = true; |
|
445 return q; |
|
446 } |
290 } |
447 |
291 |
448 // Because we don't want anyone else to bother with our defines |
292 // Because we don't want anyone else to bother with our defines |
449 #undef BIN_HEAP_ARR |
293 #undef BIN_HEAP_ARR |
450 |
294 |
467 h->buckets = (HashNode*)malloc(num_buckets * (sizeof(*h->buckets) + sizeof(*h->buckets_in_use))); |
311 h->buckets = (HashNode*)malloc(num_buckets * (sizeof(*h->buckets) + sizeof(*h->buckets_in_use))); |
468 #ifdef HASH_DEBUG |
312 #ifdef HASH_DEBUG |
469 debug("Buckets = %p", h->buckets); |
313 debug("Buckets = %p", h->buckets); |
470 #endif |
314 #endif |
471 h->buckets_in_use = (bool*)(h->buckets + num_buckets); |
315 h->buckets_in_use = (bool*)(h->buckets + num_buckets); |
472 h->freeh = false; |
|
473 for (i = 0; i < num_buckets; i++) h->buckets_in_use[i] = false; |
316 for (i = 0; i < num_buckets; i++) h->buckets_in_use[i] = false; |
474 } |
317 } |
475 |
318 |
476 Hash* new_Hash(Hash_HashProc* hash, int num_buckets) |
|
477 { |
|
478 Hash* h = MallocT<Hash>(1); |
|
479 |
|
480 init_Hash(h, hash, num_buckets); |
|
481 h->freeh = true; |
|
482 return h; |
|
483 } |
|
484 |
319 |
485 void delete_Hash(Hash* h, bool free_values) |
320 void delete_Hash(Hash* h, bool free_values) |
486 { |
321 { |
487 uint i; |
322 uint i; |
488 |
323 |