author | rubidium |
Thu, 01 Feb 2007 15:49:12 +0000 | |
changeset 5893 | 7e431a4abebb |
parent 5609 | dc6a58930ba4 |
child 6105 | 760134e9dab6 |
permissions | -rw-r--r-- |
2186 | 1 |
/* $Id$ */ |
2 |
||
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
3 |
#include "stdafx.h" |
1891
862800791170
(svn r2397) - CodeChange: rename all "ttd" files to "openttd" files.
Darkvater
parents:
1662
diff
changeset
|
4 |
#include "openttd.h" |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
5 |
#include "queue.h" |
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
6 |
#include "helpers.hpp" |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
7 |
|
1095 | 8 |
static void Stack_Clear(Queue* q, bool free_values) |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
9 |
{ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
10 |
if (free_values) { |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
11 |
uint i; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
12 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
13 |
for (i = 0; i < q->data.stack.size; i++) free(q->data.stack.elements[i]); |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
14 |
} |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
15 |
q->data.stack.size = 0; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
16 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
17 |
|
1095 | 18 |
static void Stack_Free(Queue* q, bool free_values) |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
19 |
{ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
20 |
q->clear(q, free_values); |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
21 |
free(q->data.stack.elements); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
22 |
if (q->freeq) free(q); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
23 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
24 |
|
1095 | 25 |
static bool Stack_Push(Queue* q, void* item, int priority) |
26 |
{ |
|
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
27 |
if (q->data.stack.size == q->data.stack.max_size) return false; |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
28 |
q->data.stack.elements[q->data.stack.size++] = item; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
29 |
return true; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
30 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
31 |
|
1095 | 32 |
static void* Stack_Pop(Queue* q) |
33 |
{ |
|
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
34 |
if (q->data.stack.size == 0) return NULL; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
35 |
return q->data.stack.elements[--q->data.stack.size]; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
36 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
37 |
|
1095 | 38 |
static bool Stack_Delete(Queue* q, void* item, int priority) |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
39 |
{ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
40 |
return false; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
41 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
42 |
|
1095 | 43 |
static Queue* init_stack(Queue* q, uint max_size) |
44 |
{ |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
45 |
q->push = Stack_Push; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
46 |
q->pop = Stack_Pop; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
47 |
q->del = Stack_Delete; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
48 |
q->clear = Stack_Clear; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
49 |
q->free = Stack_Free; |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
50 |
q->data.stack.max_size = max_size; |
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
51 |
q->data.stack.size = 0; |
5609
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
52 |
q->data.stack.elements = MallocT<void*>(max_size); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
53 |
q->freeq = false; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
54 |
return q; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
55 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
56 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
57 |
Queue* new_Stack(uint max_size) |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
58 |
{ |
5609
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
59 |
Queue* q = MallocT<Queue>(1); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
60 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
61 |
init_stack(q, max_size); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
62 |
q->freeq = true; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
63 |
return q; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
64 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
65 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
66 |
/* |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
67 |
* Fifo |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
68 |
*/ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
69 |
|
1095 | 70 |
static void Fifo_Clear(Queue* q, bool free_values) |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
71 |
{ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
72 |
if (free_values) { |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
73 |
uint head = q->data.fifo.head; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
74 |
uint tail = q->data.fifo.tail; /* cache for speed */ |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
75 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
76 |
while (head != tail) { |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
77 |
free(q->data.fifo.elements[tail]); |
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
78 |
tail = (tail + 1) % q->data.fifo.max_size; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
79 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
80 |
} |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
81 |
q->data.fifo.head = 0; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
82 |
q->data.fifo.tail = 0; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
83 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
84 |
|
1095 | 85 |
static void Fifo_Free(Queue* q, bool free_values) |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
86 |
{ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
87 |
q->clear(q, free_values); |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
88 |
free(q->data.fifo.elements); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
89 |
if (q->freeq) free(q); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
90 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
91 |
|
1095 | 92 |
static bool Fifo_Push(Queue* q, void* item, int priority) |
93 |
{ |
|
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
94 |
uint next = (q->data.fifo.head + 1) % q->data.fifo.max_size; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
95 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
96 |
if (next == q->data.fifo.tail) return false; |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
97 |
q->data.fifo.elements[q->data.fifo.head] = item; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
98 |
|
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
99 |
q->data.fifo.head = next; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
100 |
return true; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
101 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
102 |
|
1095 | 103 |
static void* Fifo_Pop(Queue* q) |
104 |
{ |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
105 |
void* result; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
106 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
107 |
if (q->data.fifo.head == q->data.fifo.tail) return NULL; |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
108 |
result = q->data.fifo.elements[q->data.fifo.tail]; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
109 |
|
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
110 |
q->data.fifo.tail = (q->data.fifo.tail + 1) % q->data.fifo.max_size; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
111 |
return result; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
112 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
113 |
|
1095 | 114 |
static bool Fifo_Delete(Queue* q, void* item, int priority) |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
115 |
{ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
116 |
return false; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
117 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
118 |
|
1095 | 119 |
static Queue* init_fifo(Queue* q, uint max_size) |
120 |
{ |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
121 |
q->push = Fifo_Push; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
122 |
q->pop = Fifo_Pop; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
123 |
q->del = Fifo_Delete; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
124 |
q->clear = Fifo_Clear; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
125 |
q->free = Fifo_Free; |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
126 |
q->data.fifo.max_size = max_size; |
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
127 |
q->data.fifo.head = 0; |
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
128 |
q->data.fifo.tail = 0; |
5609
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
129 |
q->data.fifo.elements = MallocT<void*>(max_size); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
130 |
q->freeq = false; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
131 |
return q; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
132 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
133 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
134 |
Queue* new_Fifo(uint max_size) |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
135 |
{ |
5609
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
136 |
Queue* q = MallocT<Queue>(1); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
137 |
init_fifo(q, max_size); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
138 |
q->freeq = true; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
139 |
return q; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
140 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
141 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
142 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
143 |
/* |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
144 |
* Insertion Sorter |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
145 |
*/ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
146 |
|
1095 | 147 |
static void InsSort_Clear(Queue* q, bool free_values) |
148 |
{ |
|
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
149 |
InsSortNode* node = q->data.inssort.first; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
150 |
InsSortNode* prev; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
151 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
152 |
while (node != NULL) { |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
153 |
if (free_values) free(node->item); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
154 |
prev = node; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
155 |
node = node->next; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
156 |
free(prev); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
157 |
} |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
158 |
q->data.inssort.first = NULL; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
159 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
160 |
|
1095 | 161 |
static void InsSort_Free(Queue* q, bool free_values) |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
162 |
{ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
163 |
q->clear(q, free_values); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
164 |
if (q->freeq) free(q); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
165 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
166 |
|
1095 | 167 |
static bool InsSort_Push(Queue* q, void* item, int priority) |
168 |
{ |
|
5609
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
169 |
InsSortNode* newnode = MallocT<InsSortNode>(1); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
170 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
171 |
if (newnode == NULL) return false; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
172 |
newnode->item = item; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
173 |
newnode->priority = priority; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
174 |
if (q->data.inssort.first == NULL || |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
175 |
q->data.inssort.first->priority >= priority) { |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
176 |
newnode->next = q->data.inssort.first; |
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
177 |
q->data.inssort.first = newnode; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
178 |
} else { |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
179 |
InsSortNode* node = q->data.inssort.first; |
2953
4d933ef9a41f
(svn r3512) Yet more whitespace fixes (mostly by Rubidium)
peter1138
parents:
2799
diff
changeset
|
180 |
while (node != NULL) { |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
181 |
if (node->next == NULL || node->next->priority >= priority) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
182 |
newnode->next = node->next; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
183 |
node->next = newnode; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
184 |
break; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
185 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
186 |
node = node->next; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
187 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
188 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
189 |
return true; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
190 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
191 |
|
1095 | 192 |
static void* InsSort_Pop(Queue* q) |
193 |
{ |
|
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
194 |
InsSortNode* node = q->data.inssort.first; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
195 |
void* result; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
196 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
197 |
if (node == NULL) return NULL; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
198 |
result = node->item; |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
199 |
q->data.inssort.first = q->data.inssort.first->next; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
200 |
assert(q->data.inssort.first == NULL || q->data.inssort.first->priority >= node->priority); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
201 |
free(node); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
202 |
return result; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
203 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
204 |
|
1095 | 205 |
static bool InsSort_Delete(Queue* q, void* item, int priority) |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
206 |
{ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
207 |
return false; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
208 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
209 |
|
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
210 |
void init_InsSort(Queue* q) |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
211 |
{ |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
212 |
q->push = InsSort_Push; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
213 |
q->pop = InsSort_Pop; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
214 |
q->del = InsSort_Delete; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
215 |
q->clear = InsSort_Clear; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
216 |
q->free = InsSort_Free; |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
217 |
q->data.inssort.first = NULL; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
218 |
q->freeq = false; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
219 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
220 |
|
1093
4fdc46eaf423
(svn r1594) Convert all undefined parameter lists to (void) and add the appropriate warning flags in the Makefile
tron
parents:
826
diff
changeset
|
221 |
Queue* new_InsSort(void) |
4fdc46eaf423
(svn r1594) Convert all undefined parameter lists to (void) and add the appropriate warning flags in the Makefile
tron
parents:
826
diff
changeset
|
222 |
{ |
5609
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
223 |
Queue* q = MallocT<Queue>(1); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
224 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
225 |
init_InsSort(q); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
226 |
q->freeq = true; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
227 |
return q; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
228 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
229 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
230 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
231 |
/* |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
232 |
* Binary Heap |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
233 |
* For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
234 |
*/ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
235 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
236 |
#define BINARY_HEAP_BLOCKSIZE (1 << BINARY_HEAP_BLOCKSIZE_BITS) |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
237 |
#define BINARY_HEAP_BLOCKSIZE_MASK (BINARY_HEAP_BLOCKSIZE - 1) |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
238 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
239 |
// To make our life easy, we make the next define |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
240 |
// Because Binary Heaps works with array from 1 to n, |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
241 |
// and C with array from 0 to n-1, and we don't like typing |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
242 |
// q->data.binaryheap.elements[i - 1] every time, we use this define. |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
243 |
#define BIN_HEAP_ARR(i) q->data.binaryheap.elements[((i) - 1) >> BINARY_HEAP_BLOCKSIZE_BITS][((i) - 1) & BINARY_HEAP_BLOCKSIZE_MASK] |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
244 |
|
1095 | 245 |
static void BinaryHeap_Clear(Queue* q, bool free_values) |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
246 |
{ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
247 |
/* Free all items if needed and free all but the first blocks of memory */ |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
248 |
uint i; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
249 |
uint j; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
250 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
251 |
for (i = 0; i < q->data.binaryheap.blocks; i++) { |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
252 |
if (q->data.binaryheap.elements[i] == NULL) { |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
253 |
/* No more allocated blocks */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
254 |
break; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
255 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
256 |
/* For every allocated block */ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
257 |
if (free_values) { |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
258 |
for (j = 0; j < (1 << BINARY_HEAP_BLOCKSIZE_BITS); j++) { |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
259 |
/* For every element in the block */ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
260 |
if ((q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS) == i && |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
261 |
(q->data.binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == j) { |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
262 |
break; /* We're past the last element */ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
263 |
} |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
264 |
free(q->data.binaryheap.elements[i][j].item); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
265 |
} |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
266 |
} |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
267 |
if (i != 0) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
268 |
/* Leave the first block of memory alone */ |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
269 |
free(q->data.binaryheap.elements[i]); |
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
270 |
q->data.binaryheap.elements[i] = NULL; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
271 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
272 |
} |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
273 |
q->data.binaryheap.size = 0; |
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
274 |
q->data.binaryheap.blocks = 1; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
275 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
276 |
|
1095 | 277 |
static void BinaryHeap_Free(Queue* q, bool free_values) |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
278 |
{ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
279 |
uint i; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
280 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
281 |
q->clear(q, free_values); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
282 |
for (i = 0; i < q->data.binaryheap.blocks; i++) { |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
283 |
if (q->data.binaryheap.elements[i] == NULL) break; |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
284 |
free(q->data.binaryheap.elements[i]); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
285 |
} |
2799
739481fa6cb9
(svn r3347) Plug a memory leak (Found by Valgrind using Truelight ... or was it the other way round?)
tron
parents:
2752
diff
changeset
|
286 |
free(q->data.binaryheap.elements); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
287 |
if (q->freeq) free(q); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
288 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
289 |
|
1095 | 290 |
static bool BinaryHeap_Push(Queue* q, void* item, int priority) |
291 |
{ |
|
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
292 |
#ifdef QUEUE_DEBUG |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
293 |
printf("[BinaryHeap] Pushing an element. There are %d elements left\n", q->data.binaryheap.size); |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
294 |
#endif |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
295 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
296 |
if (q->data.binaryheap.size == q->data.binaryheap.max_size) return false; |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
297 |
assert(q->data.binaryheap.size < q->data.binaryheap.max_size); |
201
c40d343115f8
(svn r202) -Codechange: I missed some files with trailing spaces.. this should be
truelight
parents:
107
diff
changeset
|
298 |
|
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
299 |
if (q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] == NULL) { |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
300 |
/* The currently allocated blocks are full, allocate a new one */ |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
301 |
assert((q->data.binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == 0); |
5609
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
302 |
q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE); |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
303 |
q->data.binaryheap.blocks++; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
304 |
#ifdef QUEUE_DEBUG |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
305 |
printf("[BinaryHeap] Increasing size of elements to %d nodes\n", q->data.binaryheap.blocks * BINARY_HEAP_BLOCKSIZE); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
306 |
#endif |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
307 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
308 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
309 |
// Add the item at the end of the array |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
310 |
BIN_HEAP_ARR(q->data.binaryheap.size + 1).priority = priority; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
311 |
BIN_HEAP_ARR(q->data.binaryheap.size + 1).item = item; |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
312 |
q->data.binaryheap.size++; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
313 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
314 |
// Now we are going to check where it belongs. As long as the parent is |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
315 |
// bigger, we switch with the parent |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
316 |
{ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
317 |
BinaryHeapNode temp; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
318 |
int i; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
319 |
int j; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
320 |
|
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
321 |
i = q->data.binaryheap.size; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
322 |
while (i > 1) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
323 |
// Get the parent of this object (divide by 2) |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
324 |
j = i / 2; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
325 |
// Is the parent bigger then the current, switch them |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
326 |
if (BIN_HEAP_ARR(i).priority <= BIN_HEAP_ARR(j).priority) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
327 |
temp = BIN_HEAP_ARR(j); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
328 |
BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
329 |
BIN_HEAP_ARR(i) = temp; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
330 |
i = j; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
331 |
} else { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
332 |
// It is not, we're done! |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
333 |
break; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
334 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
335 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
336 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
337 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
338 |
return true; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
339 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
340 |
|
1095 | 341 |
static bool BinaryHeap_Delete(Queue* q, void* item, int priority) |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
342 |
{ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
343 |
uint i = 0; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
344 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
345 |
#ifdef QUEUE_DEBUG |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
346 |
printf("[BinaryHeap] Deleting an element. There are %d elements left\n", q->data.binaryheap.size); |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
347 |
#endif |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
348 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
349 |
// First, we try to find the item.. |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
350 |
do { |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
351 |
if (BIN_HEAP_ARR(i + 1).item == item) break; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
352 |
i++; |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
353 |
} while (i < q->data.binaryheap.size); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
354 |
// We did not find the item, so we return false |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
355 |
if (i == q->data.binaryheap.size) return false; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
356 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
357 |
// Now we put the last item over the current item while decreasing the size of the elements |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
358 |
q->data.binaryheap.size--; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
359 |
BIN_HEAP_ARR(i + 1) = BIN_HEAP_ARR(q->data.binaryheap.size + 1); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
360 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
361 |
// Now the only thing we have to do, is resort it.. |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
362 |
// On place i there is the item to be sorted.. let's start there |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
363 |
{ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
364 |
uint j; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
365 |
BinaryHeapNode temp; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
366 |
/* Because of the fact that Binary Heap uses array from 1 to n, we need to |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
367 |
* increase i by 1 |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
368 |
*/ |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
369 |
i++; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
370 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
371 |
for (;;) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
372 |
j = i; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
373 |
// Check if we have 2 childs |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
374 |
if (2 * j + 1 <= q->data.binaryheap.size) { |
826 | 375 |
// Is this child smaller than the parent? |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
376 |
if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2 * j).priority) i = 2 * j; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
377 |
// Yes, we _need_ to use i here, not j, because we want to have the smallest child |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
378 |
// This way we get that straight away! |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
379 |
if (BIN_HEAP_ARR(i).priority >= BIN_HEAP_ARR(2 * j + 1).priority) i = 2 * j + 1; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
380 |
// Do we have one child? |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
381 |
} else if (2 * j <= q->data.binaryheap.size) { |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
382 |
if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2 * j).priority) i = 2 * j; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
383 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
384 |
|
826 | 385 |
// One of our childs is smaller than we are, switch |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
386 |
if (i != j) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
387 |
temp = BIN_HEAP_ARR(j); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
388 |
BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
389 |
BIN_HEAP_ARR(i) = temp; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
390 |
} else { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
391 |
// None of our childs is smaller, so we stay here.. stop :) |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
392 |
break; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
393 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
394 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
395 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
396 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
397 |
return true; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
398 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
399 |
|
1095 | 400 |
static void* BinaryHeap_Pop(Queue* q) |
401 |
{ |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
402 |
void* result; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
403 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
404 |
#ifdef QUEUE_DEBUG |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
405 |
printf("[BinaryHeap] Popping an element. There are %d elements left\n", q->data.binaryheap.size); |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
406 |
#endif |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
407 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
408 |
if (q->data.binaryheap.size == 0) return NULL; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
409 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
410 |
// The best item is always on top, so give that as result |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
411 |
result = BIN_HEAP_ARR(1).item; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
412 |
// And now we should get rid of this item... |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
413 |
BinaryHeap_Delete(q, BIN_HEAP_ARR(1).item, BIN_HEAP_ARR(1).priority); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
414 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
415 |
return result; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
416 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
417 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
418 |
void init_BinaryHeap(Queue* q, uint max_size) |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
419 |
{ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
420 |
assert(q != NULL); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
421 |
q->push = BinaryHeap_Push; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
422 |
q->pop = BinaryHeap_Pop; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
423 |
q->del = BinaryHeap_Delete; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
424 |
q->clear = BinaryHeap_Clear; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
425 |
q->free = BinaryHeap_Free; |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
426 |
q->data.binaryheap.max_size = max_size; |
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
427 |
q->data.binaryheap.size = 0; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
428 |
// We malloc memory in block of BINARY_HEAP_BLOCKSIZE |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
429 |
// It autosizes when it runs out of memory |
5609
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
430 |
q->data.binaryheap.elements = CallocT<BinaryHeapNode*>((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1); |
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
431 |
q->data.binaryheap.elements[0] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE); |
107
c72381c27546
(svn r108) -Fix: anon-union problems on GCC2 compilers
truelight
parents:
84
diff
changeset
|
432 |
q->data.binaryheap.blocks = 1; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
433 |
q->freeq = false; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
434 |
#ifdef QUEUE_DEBUG |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
435 |
printf("[BinaryHeap] Initial size of elements is %d nodes\n", BINARY_HEAP_BLOCKSIZE); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
436 |
#endif |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
437 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
438 |
|
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
439 |
Queue* new_BinaryHeap(uint max_size) |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
440 |
{ |
5609
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
441 |
Queue* q = MallocT<Queue>(1); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
442 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
443 |
init_BinaryHeap(q, max_size); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
444 |
q->freeq = true; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
445 |
return q; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
446 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
447 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
448 |
// Because we don't want anyone else to bother with our defines |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
449 |
#undef BIN_HEAP_ARR |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
450 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
451 |
/* |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
452 |
* Hash |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
453 |
*/ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
454 |
|
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
455 |
void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets) |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
456 |
{ |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
457 |
/* Allocate space for the Hash, the buckets and the bucket flags */ |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
458 |
uint i; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
459 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
460 |
assert(h != NULL); |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
461 |
#ifdef HASH_DEBUG |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
462 |
debug("Allocated hash: %p", h); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
463 |
#endif |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
464 |
h->hash = hash; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
465 |
h->size = 0; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
466 |
h->num_buckets = num_buckets; |
5587
167d9a91ef02
(svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium
parents:
5584
diff
changeset
|
467 |
h->buckets = (HashNode*)malloc(num_buckets * (sizeof(*h->buckets) + sizeof(*h->buckets_in_use))); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
468 |
#ifdef HASH_DEBUG |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
469 |
debug("Buckets = %p", h->buckets); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
470 |
#endif |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
471 |
h->buckets_in_use = (bool*)(h->buckets + num_buckets); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
472 |
h->freeh = false; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
473 |
for (i = 0; i < num_buckets; i++) h->buckets_in_use[i] = false; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
474 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
475 |
|
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
476 |
Hash* new_Hash(Hash_HashProc* hash, int num_buckets) |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
477 |
{ |
5609
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
478 |
Hash* h = MallocT<Hash>(1); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
479 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
480 |
init_Hash(h, hash, num_buckets); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
481 |
h->freeh = true; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
482 |
return h; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
483 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
484 |
|
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
485 |
void delete_Hash(Hash* h, bool free_values) |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
486 |
{ |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
487 |
uint i; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
488 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
489 |
/* Iterate all buckets */ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
490 |
for (i = 0; i < h->num_buckets; i++) { |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
491 |
if (h->buckets_in_use[i]) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
492 |
HashNode* node; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
493 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
494 |
/* Free the first value */ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
495 |
if (free_values) free(h->buckets[i].value); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
496 |
node = h->buckets[i].next; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
497 |
while (node != NULL) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
498 |
HashNode* prev = node; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
499 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
500 |
node = node->next; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
501 |
/* Free the value */ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
502 |
if (free_values) free(prev->value); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
503 |
/* Free the node */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
504 |
free(prev); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
505 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
506 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
507 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
508 |
free(h->buckets); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
509 |
/* No need to free buckets_in_use, it is always allocated in one |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
510 |
* malloc with buckets */ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
511 |
#ifdef HASH_DEBUG |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
512 |
debug("Freeing Hash: %p", h); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
513 |
#endif |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
514 |
if (h->freeh) free(h); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
515 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
516 |
|
2752 | 517 |
#ifdef HASH_STATS |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
518 |
static void stat_Hash(const Hash* h) |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
519 |
{ |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
520 |
uint used_buckets = 0; |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
521 |
uint max_collision = 0; |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
522 |
uint max_usage = 0; |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
523 |
uint usage[200]; |
1662
beb197794c14
(svn r2166) Fixed two warnings in the last commit.
matthijs
parents:
1661
diff
changeset
|
524 |
uint i; |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
525 |
|
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
526 |
for (i = 0; i < lengthof(usage); i++) usage[i] = 0; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
527 |
for (i = 0; i < h->num_buckets; i++) { |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
528 |
uint collision = 0; |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
529 |
if (h->buckets_in_use[i]) { |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
530 |
const HashNode* node; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
531 |
|
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
532 |
used_buckets++; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
533 |
for (node = &h->buckets[i]; node != NULL; node = node->next) collision++; |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
534 |
if (collision > max_collision) max_collision = collision; |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
535 |
} |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
536 |
if (collision >= lengthof(usage)) collision = lengthof(usage) - 1; |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
537 |
usage[collision]++; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
538 |
if (collision > 0 && usage[collision] >= max_usage) { |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
539 |
max_usage = usage[collision]; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
540 |
} |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
541 |
} |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
542 |
printf( |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
543 |
"---\n" |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
544 |
"Hash size: %d\n" |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
545 |
"Nodes used: %d\n" |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
546 |
"Non empty buckets: %d\n" |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
547 |
"Max collision: %d\n", |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
548 |
h->num_buckets, h->size, used_buckets, max_collision |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
549 |
); |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
550 |
printf("{ "); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
551 |
for (i = 0; i <= max_collision; i++) { |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
552 |
if (usage[i] > 0) { |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
553 |
printf("%d:%d ", i, usage[i]); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
554 |
#if 0 |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
555 |
if (i > 0) { |
1662
beb197794c14
(svn r2166) Fixed two warnings in the last commit.
matthijs
parents:
1661
diff
changeset
|
556 |
uint j; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
557 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
558 |
for (j = 0; j < usage[i] * 160 / 800; j++) putchar('#'); |
1662
beb197794c14
(svn r2166) Fixed two warnings in the last commit.
matthijs
parents:
1661
diff
changeset
|
559 |
} |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
560 |
printf("\n"); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
561 |
#endif |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
562 |
} |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
563 |
} |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
564 |
printf ("}\n"); |
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
565 |
} |
2752 | 566 |
#endif |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
567 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
568 |
void clear_Hash(Hash* h, bool free_values) |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
569 |
{ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
570 |
uint i; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
571 |
|
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
572 |
#ifdef HASH_STATS |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
573 |
if (h->size > 2000) stat_Hash(h); |
1661
f3799f2c84fa
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
matthijs
parents:
1247
diff
changeset
|
574 |
#endif |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
575 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
576 |
/* Iterate all buckets */ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
577 |
for (i = 0; i < h->num_buckets; i++) { |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
578 |
if (h->buckets_in_use[i]) { |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
579 |
HashNode* node; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
580 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
581 |
h->buckets_in_use[i] = false; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
582 |
/* Free the first value */ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
583 |
if (free_values) free(h->buckets[i].value); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
584 |
node = h->buckets[i].next; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
585 |
while (node != NULL) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
586 |
HashNode* prev = node; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
587 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
588 |
node = node->next; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
589 |
if (free_values) free(prev->value); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
590 |
free(prev); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
591 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
592 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
593 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
594 |
h->size = 0; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
595 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
596 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
597 |
/* Finds the node that that saves this key pair. If it is not |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
598 |
* found, returns NULL. If it is found, *prev is set to the |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
599 |
* node before the one found, or if the node found was the first in the bucket |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
600 |
* to NULL. If it is not found, *prev is set to the last HashNode in the |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
601 |
* bucket, or NULL if it is empty. prev can also be NULL, in which case it is |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
602 |
* not used for output. |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
603 |
*/ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
604 |
static HashNode* Hash_FindNode(const Hash* h, uint key1, uint key2, HashNode** prev_out) |
1095 | 605 |
{ |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
606 |
uint hash = h->hash(key1, key2); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
607 |
HashNode* result = NULL; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
608 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
609 |
#ifdef HASH_DEBUG |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
610 |
debug("Looking for %u, %u", key1, key2); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
611 |
#endif |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
612 |
/* Check if the bucket is empty */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
613 |
if (!h->buckets_in_use[hash]) { |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
614 |
if (prev_out != NULL) *prev_out = NULL; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
615 |
result = NULL; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
616 |
/* Check the first node specially */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
617 |
} else if (h->buckets[hash].key1 == key1 && h->buckets[hash].key2 == key2) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
618 |
/* Save the value */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
619 |
result = h->buckets + hash; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
620 |
if (prev_out != NULL) *prev_out = NULL; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
621 |
#ifdef HASH_DEBUG |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
622 |
debug("Found in first node: %p", result); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
623 |
#endif |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
624 |
/* Check all other nodes */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
625 |
} else { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
626 |
HashNode* prev = h->buckets + hash; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
627 |
HashNode* node; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
628 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
629 |
for (node = prev->next; node != NULL; node = node->next) { |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
630 |
if (node->key1 == key1 && node->key2 == key2) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
631 |
/* Found it */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
632 |
result = node; |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
633 |
#ifdef HASH_DEBUG |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
634 |
debug("Found in other node: %p", result); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
635 |
#endif |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
636 |
break; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
637 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
638 |
prev = node; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
639 |
} |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
640 |
if (prev_out != NULL) *prev_out = prev; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
641 |
} |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
642 |
#ifdef HASH_DEBUG |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
643 |
if (result == NULL) debug("Not found"); |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
644 |
#endif |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
645 |
return result; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
646 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
647 |
|
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
648 |
void* Hash_Delete(Hash* h, uint key1, uint key2) |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
649 |
{ |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
650 |
void* result; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
651 |
HashNode* prev; /* Used as output var for below function call */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
652 |
HashNode* node = Hash_FindNode(h, key1, key2, &prev); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
653 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
654 |
if (node == NULL) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
655 |
/* not found */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
656 |
result = NULL; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
657 |
} else if (prev == NULL) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
658 |
/* It is in the first node, we can't free that one, so we free |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
659 |
* the next one instead (if there is any)*/ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
660 |
/* Save the value */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
661 |
result = node->value; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
662 |
if (node->next != NULL) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
663 |
HashNode* next = node->next; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
664 |
/* Copy the second to the first */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
665 |
*node = *next; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
666 |
/* Free the second */ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
667 |
#ifndef NOFREE |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
668 |
free(next); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
669 |
#endif |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
670 |
} else { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
671 |
/* This was the last in this bucket */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
672 |
/* Mark it as empty */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
673 |
uint hash = h->hash(key1, key2); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
674 |
h->buckets_in_use[hash] = false; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
675 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
676 |
} else { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
677 |
/* It is in another node */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
678 |
/* Save the value */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
679 |
result = node->value; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
680 |
/* Link previous and next nodes */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
681 |
prev->next = node->next; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
682 |
/* Free the node */ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
683 |
#ifndef NOFREE |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
684 |
free(node); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
685 |
#endif |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
686 |
} |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
687 |
if (result != NULL) h->size--; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
688 |
return result; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
689 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
690 |
|
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
691 |
|
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
692 |
void* Hash_Set(Hash* h, uint key1, uint key2, void* value) |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
693 |
{ |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
694 |
HashNode* prev; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
695 |
HashNode* node = Hash_FindNode(h, key1, key2, &prev); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
696 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
697 |
if (node != NULL) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
698 |
/* Found it */ |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
699 |
void* result = node->value; |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
700 |
|
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
701 |
node->value = value; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
702 |
return result; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
703 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
704 |
/* It is not yet present, let's add it */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
705 |
if (prev == NULL) { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
706 |
/* The bucket is still empty */ |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
707 |
uint hash = h->hash(key1, key2); |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
708 |
h->buckets_in_use[hash] = true; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
709 |
node = h->buckets + hash; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
710 |
} else { |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
711 |
/* Add it after prev */ |
5609
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
712 |
node = MallocT<HashNode>(1); |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
713 |
prev->next = node; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
714 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
715 |
node->next = NULL; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
716 |
node->key1 = key1; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
717 |
node->key2 = key2; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
718 |
node->value = value; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
719 |
h->size++; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
720 |
return NULL; |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
721 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
722 |
|
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
723 |
void* Hash_Get(const Hash* h, uint key1, uint key2) |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
724 |
{ |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
725 |
HashNode* node = Hash_FindNode(h, key1, key2, NULL); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
726 |
|
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
727 |
#ifdef HASH_DEBUG |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
728 |
debug("Found node: %p", node); |
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
729 |
#endif |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
730 |
return (node != NULL) ? node->value : NULL; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
731 |
} |
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
732 |
|
3012
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
733 |
uint Hash_Size(const Hash* h) |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
734 |
{ |
5e79c183a4bf
(svn r3592) Miscellaneous smaller changes, most notably replacing sizeof(type) by sizeof(*variable)
tron
parents:
3010
diff
changeset
|
735 |
return h->size; |
84
1e0721c29bad
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
truelight
parents:
diff
changeset
|
736 |
} |