Mercurial > hg > openttd

annotate src/queue.cpp @ 8157:019833e42fda draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
(svn r11719) -Codechange: split sound.h in a header with types and one with functions.
author rubidium <rubidium@openttd.org>
date Sat, 29 Dec 2007 09:24:26 +0000
parents 0586823afe39
children d48433370037
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
1 /* $Id$ */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
2
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
3 /** @file queue.cpp */
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
4
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
5 #include "stdafx.h"
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
6 #include "openttd.h"
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
7 #include "queue.h"
8130
0586823afe39 (svn r11691) -Codechange: move+rename helpers.hpp and only include it when it is really needed.
rubidium <rubidium@openttd.org>
parents: 8037
diff changeset
8 #include "core/alloc_func.hpp"
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
9
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
10
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
11 /*
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
12 * Insertion Sorter
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
13 */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
14
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
15 static void InsSort_Clear(Queue* q, bool free_values)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
16 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
17 InsSortNode* node = q->data.inssort.first;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
18 InsSortNode* prev;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
19
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
20 while (node != NULL) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
21 if (free_values) free(node->item);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
22 prev = node;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
23 node = node->next;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
24 free(prev);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
25 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
26 q->data.inssort.first = NULL;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
27 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
28
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
29 static void InsSort_Free(Queue* q, bool free_values)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
30 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
31 q->clear(q, free_values);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
32 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
33
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
34 static bool InsSort_Push(Queue* q, void* item, int priority)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
35 {
5609
358c07fb3212 (svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr <KUDr@openttd.org>
parents: 5587
diff changeset
36 InsSortNode* newnode = MallocT<InsSortNode>(1);
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
37
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
38 if (newnode == NULL) return false;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
39 newnode->item = item;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
40 newnode->priority = priority;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
41 if (q->data.inssort.first == NULL ||
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
42 q->data.inssort.first->priority >= priority) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
43 newnode->next = q->data.inssort.first;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
44 q->data.inssort.first = newnode;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
45 } else {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
46 InsSortNode* node = q->data.inssort.first;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
47 while (node != NULL) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
48 if (node->next == NULL || node->next->priority >= priority) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
49 newnode->next = node->next;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
50 node->next = newnode;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
51 break;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
52 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
53 node = node->next;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
54 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
55 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
56 return true;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
57 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
58
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
59 static void* InsSort_Pop(Queue* q)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
60 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
61 InsSortNode* node = q->data.inssort.first;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
62 void* result;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
63
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
64 if (node == NULL) return NULL;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
65 result = node->item;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
66 q->data.inssort.first = q->data.inssort.first->next;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
67 assert(q->data.inssort.first == NULL || q->data.inssort.first->priority >= node->priority);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
68 free(node);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
69 return result;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
70 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
71
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
72 static bool InsSort_Delete(Queue* q, void* item, int priority)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
73 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
74 return false;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
75 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
76
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
77 void init_InsSort(Queue* q)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
78 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
79 q->push = InsSort_Push;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
80 q->pop = InsSort_Pop;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
81 q->del = InsSort_Delete;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
82 q->clear = InsSort_Clear;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
83 q->free = InsSort_Free;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
84 q->data.inssort.first = NULL;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
85 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
86
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
87
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
88 /*
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
89 * Binary Heap
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
90 * For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
91 */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
92
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
93 #define BINARY_HEAP_BLOCKSIZE (1 << BINARY_HEAP_BLOCKSIZE_BITS)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
94 #define BINARY_HEAP_BLOCKSIZE_MASK (BINARY_HEAP_BLOCKSIZE - 1)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
95
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
96 /* To make our life easy, we make the next define
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
97 * Because Binary Heaps works with array from 1 to n,
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
98 * and C with array from 0 to n-1, and we don't like typing
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
99 * q->data.binaryheap.elements[i - 1] every time, we use this define. */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
100 #define BIN_HEAP_ARR(i) q->data.binaryheap.elements[((i) - 1) >> BINARY_HEAP_BLOCKSIZE_BITS][((i) - 1) & BINARY_HEAP_BLOCKSIZE_MASK]
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
101
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
102 static void BinaryHeap_Clear(Queue* q, bool free_values)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
103 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
104 /* Free all items if needed and free all but the first blocks of memory */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
105 uint i;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
106 uint j;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
107
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
108 for (i = 0; i < q->data.binaryheap.blocks; i++) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
109 if (q->data.binaryheap.elements[i] == NULL) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
110 /* No more allocated blocks */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
111 break;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
112 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
113 /* For every allocated block */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
114 if (free_values) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
115 for (j = 0; j < (1 << BINARY_HEAP_BLOCKSIZE_BITS); j++) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
116 /* For every element in the block */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
117 if ((q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS) == i &&
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
118 (q->data.binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == j) {
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
119 break; // We're past the last element
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
120 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
121 free(q->data.binaryheap.elements[i][j].item);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
122 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
123 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
124 if (i != 0) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
125 /* Leave the first block of memory alone */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
126 free(q->data.binaryheap.elements[i]);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
127 q->data.binaryheap.elements[i] = NULL;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
128 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
129 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
130 q->data.binaryheap.size = 0;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
131 q->data.binaryheap.blocks = 1;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
132 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
133
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
134 static void BinaryHeap_Free(Queue* q, bool free_values)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
135 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
136 uint i;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
137
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
138 q->clear(q, free_values);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
139 for (i = 0; i < q->data.binaryheap.blocks; i++) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
140 if (q->data.binaryheap.elements[i] == NULL) break;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
141 free(q->data.binaryheap.elements[i]);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
142 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
143 free(q->data.binaryheap.elements);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
144 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
145
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
146 static bool BinaryHeap_Push(Queue* q, void* item, int priority)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
147 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
148 #ifdef QUEUE_DEBUG
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
149 printf("[BinaryHeap] Pushing an element. There are %d elements left\n", q->data.binaryheap.size);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
150 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
151
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
152 if (q->data.binaryheap.size == q->data.binaryheap.max_size) return false;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
153 assert(q->data.binaryheap.size < q->data.binaryheap.max_size);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
154
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
155 if (q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] == NULL) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
156 /* The currently allocated blocks are full, allocate a new one */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
157 assert((q->data.binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == 0);
5609
358c07fb3212 (svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr <KUDr@openttd.org>
parents: 5587
diff changeset
158 q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE);
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
159 q->data.binaryheap.blocks++;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
160 #ifdef QUEUE_DEBUG
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
161 printf("[BinaryHeap] Increasing size of elements to %d nodes\n", q->data.binaryheap.blocks * BINARY_HEAP_BLOCKSIZE);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
162 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
163 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
164
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
165 /* Add the item at the end of the array */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
166 BIN_HEAP_ARR(q->data.binaryheap.size + 1).priority = priority;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
167 BIN_HEAP_ARR(q->data.binaryheap.size + 1).item = item;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
168 q->data.binaryheap.size++;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
169
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
170 /* Now we are going to check where it belongs. As long as the parent is
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
171 * bigger, we switch with the parent */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
172 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
173 BinaryHeapNode temp;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
174 int i;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
175 int j;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
176
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
177 i = q->data.binaryheap.size;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
178 while (i > 1) {
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
179 /* Get the parent of this object (divide by 2) */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
180 j = i / 2;
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
181 /* Is the parent bigger then the current, switch them */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
182 if (BIN_HEAP_ARR(i).priority <= BIN_HEAP_ARR(j).priority) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
183 temp = BIN_HEAP_ARR(j);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
184 BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
185 BIN_HEAP_ARR(i) = temp;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
186 i = j;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
187 } else {
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
188 /* It is not, we're done! */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
189 break;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
190 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
191 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
192 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
193
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
194 return true;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
195 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
196
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
197 static bool BinaryHeap_Delete(Queue* q, void* item, int priority)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
198 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
199 uint i = 0;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
200
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
201 #ifdef QUEUE_DEBUG
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
202 printf("[BinaryHeap] Deleting an element. There are %d elements left\n", q->data.binaryheap.size);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
203 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
204
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
205 /* First, we try to find the item.. */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
206 do {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
207 if (BIN_HEAP_ARR(i + 1).item == item) break;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
208 i++;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
209 } while (i < q->data.binaryheap.size);
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
210 /* We did not find the item, so we return false */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
211 if (i == q->data.binaryheap.size) return false;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
212
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
213 /* Now we put the last item over the current item while decreasing the size of the elements */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
214 q->data.binaryheap.size--;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
215 BIN_HEAP_ARR(i + 1) = BIN_HEAP_ARR(q->data.binaryheap.size + 1);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
216
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
217 /* Now the only thing we have to do, is resort it..
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
218 * On place i there is the item to be sorted.. let's start there */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
219 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
220 uint j;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
221 BinaryHeapNode temp;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
222 /* Because of the fact that Binary Heap uses array from 1 to n, we need to
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
223 * increase i by 1
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
224 */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
225 i++;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
226
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
227 for (;;) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
228 j = i;
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
229 /* Check if we have 2 childs */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
230 if (2 * j + 1 <= q->data.binaryheap.size) {
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
231 /* Is this child smaller than the parent? */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
232 if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2 * j).priority) i = 2 * j;
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
233 /* Yes, we _need_ to use i here, not j, because we want to have the smallest child
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
234 * This way we get that straight away! */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
235 if (BIN_HEAP_ARR(i).priority >= BIN_HEAP_ARR(2 * j + 1).priority) i = 2 * j + 1;
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
236 /* Do we have one child? */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
237 } else if (2 * j <= q->data.binaryheap.size) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
238 if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2 * j).priority) i = 2 * j;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
239 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
240
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
241 /* One of our childs is smaller than we are, switch */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
242 if (i != j) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
243 temp = BIN_HEAP_ARR(j);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
244 BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
245 BIN_HEAP_ARR(i) = temp;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
246 } else {
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
247 /* None of our childs is smaller, so we stay here.. stop :) */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
248 break;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
249 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
250 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
251 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
252
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
253 return true;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
254 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
255
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
256 static void* BinaryHeap_Pop(Queue* q)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
257 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
258 void* result;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
259
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
260 #ifdef QUEUE_DEBUG
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
261 printf("[BinaryHeap] Popping an element. There are %d elements left\n", q->data.binaryheap.size);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
262 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
263
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
264 if (q->data.binaryheap.size == 0) return NULL;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
265
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
266 /* The best item is always on top, so give that as result */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
267 result = BIN_HEAP_ARR(1).item;
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
268 /* And now we should get rid of this item... */
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
269 BinaryHeap_Delete(q, BIN_HEAP_ARR(1).item, BIN_HEAP_ARR(1).priority);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
270
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
271 return result;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
272 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
273
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
274 void init_BinaryHeap(Queue* q, uint max_size)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
275 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
276 assert(q != NULL);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
277 q->push = BinaryHeap_Push;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
278 q->pop = BinaryHeap_Pop;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
279 q->del = BinaryHeap_Delete;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
280 q->clear = BinaryHeap_Clear;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
281 q->free = BinaryHeap_Free;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
282 q->data.binaryheap.max_size = max_size;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
283 q->data.binaryheap.size = 0;
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
284 /* We malloc memory in block of BINARY_HEAP_BLOCKSIZE
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
285 * It autosizes when it runs out of memory */
5609
358c07fb3212 (svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr <KUDr@openttd.org>
parents: 5587
diff changeset
286 q->data.binaryheap.elements = CallocT<BinaryHeapNode*>((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1);
358c07fb3212 (svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr <KUDr@openttd.org>
parents: 5587
diff changeset
287 q->data.binaryheap.elements[0] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE);
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
288 q->data.binaryheap.blocks = 1;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
289 #ifdef QUEUE_DEBUG
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
290 printf("[BinaryHeap] Initial size of elements is %d nodes\n", BINARY_HEAP_BLOCKSIZE);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
291 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
292 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
293
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
294 // Because we don't want anyone else to bother with our defines
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
295 #undef BIN_HEAP_ARR
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
296
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
297 /*
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
298 * Hash
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
299 */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
300
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
301 void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
302 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
303 /* Allocate space for the Hash, the buckets and the bucket flags */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
304 uint i;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
305
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
306 assert(h != NULL);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
307 #ifdef HASH_DEBUG
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
308 debug("Allocated hash: %p", h);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
309 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
310 h->hash = hash;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
311 h->size = 0;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
312 h->num_buckets = num_buckets;
8037
02252785b8d6 (svn r11597) -Change: replace all remaining instances of (re|m|c)alloc with (Re|M|C)allocT and add a check for out-of-memory situations to the *allocT functions.
rubidium <rubidium@openttd.org>
parents: 6352
diff changeset
313 h->buckets = (HashNode*)MallocT<byte>(num_buckets * (sizeof(*h->buckets) + sizeof(*h->buckets_in_use)));
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
314 #ifdef HASH_DEBUG
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
315 debug("Buckets = %p", h->buckets);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
316 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
317 h->buckets_in_use = (bool*)(h->buckets + num_buckets);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
318 for (i = 0; i < num_buckets; i++) h->buckets_in_use[i] = false;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
319 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
320
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
321
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
322 void delete_Hash(Hash* h, bool free_values)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
323 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
324 uint i;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
325
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
326 /* Iterate all buckets */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
327 for (i = 0; i < h->num_buckets; i++) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
328 if (h->buckets_in_use[i]) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
329 HashNode* node;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
330
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
331 /* Free the first value */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
332 if (free_values) free(h->buckets[i].value);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
333 node = h->buckets[i].next;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
334 while (node != NULL) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
335 HashNode* prev = node;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
336
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
337 node = node->next;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
338 /* Free the value */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
339 if (free_values) free(prev->value);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
340 /* Free the node */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
341 free(prev);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
342 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
343 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
344 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
345 free(h->buckets);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
346 /* No need to free buckets_in_use, it is always allocated in one
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
347 * malloc with buckets */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
348 #ifdef HASH_DEBUG
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
349 debug("Freeing Hash: %p", h);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
350 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
351 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
352
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
353 #ifdef HASH_STATS
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
354 static void stat_Hash(const Hash* h)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
355 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
356 uint used_buckets = 0;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
357 uint max_collision = 0;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
358 uint max_usage = 0;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
359 uint usage[200];
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
360 uint i;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
361
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
362 for (i = 0; i < lengthof(usage); i++) usage[i] = 0;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
363 for (i = 0; i < h->num_buckets; i++) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
364 uint collision = 0;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
365 if (h->buckets_in_use[i]) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
366 const HashNode* node;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
367
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
368 used_buckets++;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
369 for (node = &h->buckets[i]; node != NULL; node = node->next) collision++;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
370 if (collision > max_collision) max_collision = collision;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
371 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
372 if (collision >= lengthof(usage)) collision = lengthof(usage) - 1;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
373 usage[collision]++;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
374 if (collision > 0 && usage[collision] >= max_usage) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
375 max_usage = usage[collision];
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
376 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
377 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
378 printf(
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
379 "---\n"
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
380 "Hash size: %d\n"
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
381 "Nodes used: %d\n"
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
382 "Non empty buckets: %d\n"
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
383 "Max collision: %d\n",
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
384 h->num_buckets, h->size, used_buckets, max_collision
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
385 );
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
386 printf("{ ");
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
387 for (i = 0; i <= max_collision; i++) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
388 if (usage[i] > 0) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
389 printf("%d:%d ", i, usage[i]);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
390 #if 0
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
391 if (i > 0) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
392 uint j;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
393
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
394 for (j = 0; j < usage[i] * 160 / 800; j++) putchar('#');
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
395 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
396 printf("\n");
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
397 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
398 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
399 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
400 printf ("}\n");
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
401 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
402 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
403
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
404 void clear_Hash(Hash* h, bool free_values)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
405 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
406 uint i;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
407
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
408 #ifdef HASH_STATS
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
409 if (h->size > 2000) stat_Hash(h);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
410 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
411
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
412 /* Iterate all buckets */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
413 for (i = 0; i < h->num_buckets; i++) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
414 if (h->buckets_in_use[i]) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
415 HashNode* node;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
416
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
417 h->buckets_in_use[i] = false;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
418 /* Free the first value */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
419 if (free_values) free(h->buckets[i].value);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
420 node = h->buckets[i].next;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
421 while (node != NULL) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
422 HashNode* prev = node;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
423
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
424 node = node->next;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
425 if (free_values) free(prev->value);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
426 free(prev);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
427 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
428 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
429 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
430 h->size = 0;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
431 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
432
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
433 /** Finds the node that that saves this key pair. If it is not
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
434 * found, returns NULL. If it is found, *prev is set to the
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
435 * node before the one found, or if the node found was the first in the bucket
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
436 * to NULL. If it is not found, *prev is set to the last HashNode in the
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
437 * bucket, or NULL if it is empty. prev can also be NULL, in which case it is
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
438 * not used for output.
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
439 */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
440 static HashNode* Hash_FindNode(const Hash* h, uint key1, uint key2, HashNode** prev_out)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
441 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
442 uint hash = h->hash(key1, key2);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
443 HashNode* result = NULL;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
444
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
445 #ifdef HASH_DEBUG
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
446 debug("Looking for %u, %u", key1, key2);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
447 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
448 /* Check if the bucket is empty */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
449 if (!h->buckets_in_use[hash]) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
450 if (prev_out != NULL) *prev_out = NULL;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
451 result = NULL;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
452 /* Check the first node specially */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
453 } else if (h->buckets[hash].key1 == key1 && h->buckets[hash].key2 == key2) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
454 /* Save the value */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
455 result = h->buckets + hash;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
456 if (prev_out != NULL) *prev_out = NULL;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
457 #ifdef HASH_DEBUG
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
458 debug("Found in first node: %p", result);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
459 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
460 /* Check all other nodes */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
461 } else {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
462 HashNode* prev = h->buckets + hash;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
463 HashNode* node;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
464
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
465 for (node = prev->next; node != NULL; node = node->next) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
466 if (node->key1 == key1 && node->key2 == key2) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
467 /* Found it */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
468 result = node;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
469 #ifdef HASH_DEBUG
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
470 debug("Found in other node: %p", result);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
471 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
472 break;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
473 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
474 prev = node;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
475 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
476 if (prev_out != NULL) *prev_out = prev;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
477 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
478 #ifdef HASH_DEBUG
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
479 if (result == NULL) debug("Not found");
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
480 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
481 return result;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
482 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
483
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
484 void* Hash_Delete(Hash* h, uint key1, uint key2)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
485 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
486 void* result;
6352
d646bb89ca43 (svn r9391) -Documentation : correct Doxygen of comments and @file inclusion. Time for P and Q files
belugas <belugas@openttd.org>
parents: 6105
diff changeset
487 HashNode* prev; // Used as output var for below function call
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
488 HashNode* node = Hash_FindNode(h, key1, key2, &prev);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
489
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
490 if (node == NULL) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
491 /* not found */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
492 result = NULL;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
493 } else if (prev == NULL) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
494 /* It is in the first node, we can't free that one, so we free
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
495 * the next one instead (if there is any)*/
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
496 /* Save the value */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
497 result = node->value;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
498 if (node->next != NULL) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
499 HashNode* next = node->next;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
500 /* Copy the second to the first */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
501 *node = *next;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
502 /* Free the second */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
503 #ifndef NOFREE
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
504 free(next);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
505 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
506 } else {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
507 /* This was the last in this bucket */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
508 /* Mark it as empty */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
509 uint hash = h->hash(key1, key2);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
510 h->buckets_in_use[hash] = false;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
511 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
512 } else {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
513 /* It is in another node */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
514 /* Save the value */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
515 result = node->value;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
516 /* Link previous and next nodes */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
517 prev->next = node->next;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
518 /* Free the node */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
519 #ifndef NOFREE
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
520 free(node);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
521 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
522 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
523 if (result != NULL) h->size--;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
524 return result;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
525 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
526
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
527
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
528 void* Hash_Set(Hash* h, uint key1, uint key2, void* value)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
529 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
530 HashNode* prev;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
531 HashNode* node = Hash_FindNode(h, key1, key2, &prev);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
532
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
533 if (node != NULL) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
534 /* Found it */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
535 void* result = node->value;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
536
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
537 node->value = value;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
538 return result;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
539 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
540 /* It is not yet present, let's add it */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
541 if (prev == NULL) {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
542 /* The bucket is still empty */
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
543 uint hash = h->hash(key1, key2);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
544 h->buckets_in_use[hash] = true;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
545 node = h->buckets + hash;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
546 } else {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
547 /* Add it after prev */
5609
358c07fb3212 (svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr <KUDr@openttd.org>
parents: 5587
diff changeset
548 node = MallocT<HashNode>(1);
5584
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
549 prev->next = node;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
550 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
551 node->next = NULL;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
552 node->key1 = key1;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
553 node->key2 = key2;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
554 node->value = value;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
555 h->size++;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
556 return NULL;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
557 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
558
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
559 void* Hash_Get(const Hash* h, uint key1, uint key2)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
560 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
561 HashNode* node = Hash_FindNode(h, key1, key2, NULL);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
562
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
563 #ifdef HASH_DEBUG
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
564 debug("Found node: %p", node);
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
565 #endif
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
566 return (node != NULL) ? node->value : NULL;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
567 }
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
568
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
569 uint Hash_Size(const Hash* h)
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
570 {
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
571 return h->size;
4b26bd55bd24 (svn r8033) [cpp] - Prepare for merge from branches/cpp (all .c files renamed to .cpp)
KUDr <KUDr@openttd.org>
parents:
diff changeset
572 }