102 Dalmatians: Puppies to the Rescue
Decompilation Source Reference | GitLab repository
Loading...
Searching...
No Matches
tree.c
Go to the documentation of this file.
1/* Recovered game implementation; original addresses identify provenance. */
7
8// Original pcdogs.exe: 0x43fa80
9// Clears the hidden map-node header and inserts the payload into the map. A null payload is ignored.
10void Tree_InitializeMapNode(struct Tree_Map *tree, void *node_payload)
11{
12 if (!node_payload)
13 return;
14
15 struct Tree_MapNode *node = (struct Tree_MapNode *)node_payload - 1;
16
17 node->child = NULL;
18 node->parent = NULL;
19 node->rank = 0;
20 node->marked = 0;
21 Tree_InsertMapNode(tree, node);
22}
23
24// Original pcdogs.exe: 0x43fab0
25// Inserts a node into the circular root ring. A nonnull parent is cleared without comparing priorities; otherwise the payload comparator updates the minimum root.
26void Tree_InsertMapNode(struct Tree_Map *tree, struct Tree_MapNode *node)
27{
28 struct Tree_MapNode *min_root = tree->min_root;
29
30 if (!min_root)
31 {
32 node->prev = node;
33 node->next = node;
34 tree->min_root = node;
35
36 return;
37 }
38
39 node->prev = min_root->prev;
40
41 node->next = min_root;
42 min_root->prev = node;
43 node->prev->next = node;
44
45 if (node->parent)
46 {
47 node->parent = NULL;
48
49 return;
50 }
51
52 if (tree->compare(&node[1], &tree->min_root[1]) < 0)
53 tree->min_root = node;
54}
55
56// Original pcdogs.exe: 0x43fb10
57// Splices a circular node ring into the map's root ring. A null ring is ignored.
58void Tree_SpliceRingIntoRootList(struct Tree_Map *tree, struct Tree_MapNode *node)
59{
60 if (!node)
61 return;
62
63 struct Tree_MapNode *incoming_tail = node->prev;
64 struct Tree_MapNode *min_root = tree->min_root;
65 struct Tree_MapNode *root_tail = min_root->prev;
66
67 min_root->prev = incoming_tail;
68 incoming_tail->next = min_root;
69 node->prev = root_tail;
70 root_tail->next = node;
71}
72
73// Original pcdogs.exe: 0x43fb40
74// Detaches a payload's node and consolidates the remaining roots without freeing the payload allocation.
75void Tree_RemoveMapNode(struct Tree_Map *tree, void *node_payload)
76{
77 if (!node_payload)
78 return;
79
80 struct Tree_MapNode *node = (struct Tree_MapNode *)node_payload - 1;
81
84 node->next->prev = NULL;
85
86 struct Tree_MapNode *prev = node->prev;
87
88 tree->min_root = prev;
89
90 if (prev)
92}
93
94// Original pcdogs.exe: 0x43fb90
95// Merges roots of equal rank through 33 scratch buckets and rebuilds the circular root ring and minimum pointer. Input roots must form the temporary null-terminated backward chain expected by removal.
96void Tree_RebalanceMap(struct Tree_Map *tree)
97{
98 struct Tree_MapNode *root_cursor = tree->min_root;
99
100 do
101 {
102 struct Tree_MapNode *merged_root = root_cursor;
103
104 root_cursor = root_cursor->prev;
105
106 for (struct Tree_MapNode *same_rank_root = g_treeMapBuckets[merged_root->rank]; same_rank_root;
107 same_rank_root = g_treeMapBuckets[merged_root->rank])
108 {
109 g_treeMapBuckets[merged_root->rank] = NULL;
110
111 if (tree->compare(&same_rank_root[1], &merged_root[1]) < 0)
112 {
113 struct Tree_MapNode *previous_merged_root = merged_root;
114
115 merged_root = same_rank_root;
116 same_rank_root = previous_merged_root;
117 }
118
119 same_rank_root->parent = merged_root;
120 same_rank_root->marked = 0;
121
122 struct Tree_MapNode *child = merged_root->child;
123
124 if (child)
125 {
126 same_rank_root->next = child;
127 same_rank_root->prev = merged_root->child->prev;
128 merged_root->child->prev = same_rank_root;
129 same_rank_root->prev->next = same_rank_root;
130 }
131 else
132 {
133 same_rank_root->prev = same_rank_root;
134 same_rank_root->next = same_rank_root;
135 merged_root->child = same_rank_root;
136 }
137
138 merged_root->rank += 1;
139 }
140
141 g_treeMapBuckets[merged_root->rank] = merged_root;
142 } while (root_cursor);
143
144 tree->min_root = NULL;
145 for (int32_t rank = 0; rank < TREE_RANK_BUCKET_COUNT; ++rank)
146 {
147 struct Tree_MapNode *node = g_treeMapBuckets[rank];
148
149 if (node)
150 {
151 g_treeMapBuckets[rank] = NULL;
152 node->marked = 0;
153 node->parent = NULL;
154 Tree_InsertMapNode(tree, node);
155 }
156 }
157}
158
159// Original pcdogs.exe: 0x43fc70
160// Cuts a nonroot node, updates its parent's rank and loss mark, and cascades cuts after repeated child loss. This routine performs no key comparison.
161void Tree_RotateAndDetachMapNode(struct Tree_Map *tree, struct Tree_MapNode *node)
162{
163 struct Tree_MapNode *detached_node = node;
164 struct Tree_MapNode *parent = detached_node->parent;
165
166 if (!parent)
167 return;
168
169 detached_node->marked = 0;
170
171 do
172 {
173 parent->rank -= 1;
174
175 if (parent->rank)
176 {
177 parent->child = detached_node->prev;
178 detached_node->next->prev = detached_node->prev;
179 detached_node->prev->next = detached_node->next;
180 }
181 else
182 parent->child = NULL;
183
184 Tree_InsertMapNode(tree, detached_node);
185 detached_node = parent;
187
188 if (!parent)
189 break;
190
191 detached_node->marked ^= TREE_NODE_MARKED;
192 } while (!detached_node->marked);
193}
194
195// Original pcdogs.exe: 0x43fce0
196// Removes and returns the minimum payload, consolidating the remaining roots. An empty map returns null, and the removed allocation remains owned by the caller.
198{
199 if (!tree)
200 return tree;
201
202 struct Tree_MapNode *min_root = tree->min_root;
203
204 if (min_root)
205 {
206 min_root = &min_root[1];
207 Tree_RemoveMapNode(tree, min_root);
208 }
209
210 return min_root;
211}
212
213// Original pcdogs.exe: 0x43fd00
214// Repairs parent and minimum ordering after a payload priority decreases, cutting the node when needed. A null payload returns minus one; other paths return zero.
215int32_t Tree_FixupMapAfterInsert(struct Tree_Map *tree, void *node_payload)
216{
217 if (!node_payload)
218 return -1;
219
220 struct Tree_MapNode *node = ((struct Tree_MapNode *)node_payload - 1);
221 struct Tree_MapNode *previous = node->parent;
222
223 if (!previous)
224 {
225 if (node == tree->min_root)
226 return 0;
227 }
228 else
229 {
230 if (tree->compare(node_payload, &previous[1]) >= 0)
231 return 0;
232
233 Tree_RotateAndDetachMapNode(tree, node);
234 }
235
236 if (tree->compare(node_payload, &tree->min_root[1]) < 0)
237 tree->min_root = node;
238
239 return 0;
240}
241
242// Original pcdogs.exe: 0x43fd70
243// Allocates a node-sized block and returns the payload after its hidden header. It neither initializes the header nor inserts the node, and allocation failure returns null.
245{
246 void *allocation = Pkg_AllocateResourceMemory(tree->node_alloc_size);
247
248 if (!allocation)
249 return 0;
250
251 return (struct Tree_MapNode *)allocation + 1;
252}
253
254// Original pcdogs.exe: 0x43fd90
255// Frees the allocation containing a payload's hidden header. A null payload is accepted, but a linked node must be removed separately before freeing.
256void Tree_FreeMapNode(void *node_payload)
257{
258 if (node_payload)
259 Pkg_FreeResourceMemory((struct Tree_MapNode *)node_payload - 1);
260}
261
262// Original pcdogs.exe: 0x43fdb0
263// Allocates an empty map header with a payload comparator and node allocation size that includes the hidden header.
264struct Tree_Map *Tree_CreateMap(int32_t payload_size, int32_t (*compare_func)(void *, void *))
265{
266 struct Tree_Map *result = Pkg_AllocateResourceMemory(sizeof(*result));
267
268 if (result)
269 {
270 result->min_root = NULL;
271 result->node_alloc_size = payload_size + sizeof(struct Tree_MapNode);
272 result->compare = compare_func;
273 }
274
275 return result;
276}
277
278// Original pcdogs.exe: 0x43fde0
279// Frees every root and descendant allocation, then frees the map header.
280void Tree_DestroyMap(struct Tree_Map *tree)
281{
282 if (!tree)
283 return;
284
285 struct Tree_MapNode *root_cursor = tree->min_root;
286
287 if (root_cursor)
288 {
289 do
290 {
291 tree->min_root = root_cursor;
292 Tree_SpliceRingIntoRootList(tree, root_cursor->child);
293 root_cursor->next->prev = root_cursor->prev;
294 root_cursor->prev->next = root_cursor->next;
295 root_cursor = root_cursor->prev;
297 } while (root_cursor != tree->min_root);
298 }
299
301}
#define TREE_NODE_MARKED
Definition constants.h:7
#define TREE_RANK_BUCKET_COUNT
Definition constants.h:6
#define g_treeMapBuckets
Definition globals.h:9
void Pkg_FreeResourceMemory(void *user_ptr)
Definition resources.c:342
void * Pkg_AllocateResourceMemory(uint32_t size)
Definition resources.c:317
struct Tree_MapNode * child
Definition types.h:25
uint16_t marked
Definition types.h:27
struct Tree_MapNode * parent
Definition types.h:24
int16_t rank
Definition types.h:26
struct Tree_MapNode * prev
Definition types.h:23
struct Tree_MapNode * next
Definition types.h:22
struct Tree_MapNode * min_root
Definition types.h:10
int32_t node_alloc_size
Definition types.h:11
int32_t(* compare)(void *lhs, void *rhs)
Definition types.h:12
struct Tree_Map * Tree_CreateMap(int32_t payload_size, int32_t(*compare_func)(void *, void *))
Definition tree.c:264
void * Tree_AllocateMapNode(struct Tree_Map *tree)
Definition tree.c:244
void Tree_SpliceRingIntoRootList(struct Tree_Map *tree, struct Tree_MapNode *node)
Definition tree.c:58
void Tree_RemoveMapNode(struct Tree_Map *tree, void *node_payload)
Definition tree.c:75
void * Tree_GetFirstMapNode(struct Tree_Map *tree)
Definition tree.c:197
void Tree_InsertMapNode(struct Tree_Map *tree, struct Tree_MapNode *node)
Definition tree.c:26
int32_t Tree_FixupMapAfterInsert(struct Tree_Map *tree, void *node_payload)
Definition tree.c:215
void Tree_DestroyMap(struct Tree_Map *tree)
Definition tree.c:280
void Tree_RotateAndDetachMapNode(struct Tree_Map *tree, struct Tree_MapNode *node)
Definition tree.c:161
void Tree_RebalanceMap(struct Tree_Map *tree)
Definition tree.c:96
void Tree_InitializeMapNode(struct Tree_Map *tree, void *node_payload)
Definition tree.c:10
void Tree_FreeMapNode(void *node_payload)
Definition tree.c:256