1 // SONIC ROBO BLAST 2
2 //-----------------------------------------------------------------------------
3 // Copyright (C) 1993-1996 by id Software, Inc.
4 // Copyright (C) 1998-2000 by DooM Legacy Team.
5 // Copyright (C) 1999-2020 by Sonic Team Junior.
6 //
7 // This program is free software distributed under the
8 // terms of the GNU General Public License, version 2.
9 // See the 'LICENSE' file for more details.
10 //-----------------------------------------------------------------------------
11 /// \file m_aatree.h
12 /// \brief AA trees code
13
14 #include "m_aatree.h"
15 #include "z_zone.h"
16
17 // A partial implementation of AA trees,
18 // according to the algorithms given on Wikipedia.
19 // http://en.wikipedia.org/wiki/AA_tree
20
21 typedef struct aatree_node_s
22 {
23 INT32 level;
24 INT32 key;
25 void* value;
26
27 struct aatree_node_s *left, *right;
28 } aatree_node_t;
29
30 struct aatree_s
31 {
32 aatree_node_t *root;
33 UINT32 flags;
34 };
35
M_AATreeAlloc(UINT32 flags)36 aatree_t *M_AATreeAlloc(UINT32 flags)
37 {
38 aatree_t *aatree = Z_Malloc(sizeof (aatree_t), PU_STATIC, NULL);
39 aatree->root = NULL;
40 aatree->flags = flags;
41 return aatree;
42 }
43
M_AATreeFree_Node(aatree_node_t * node)44 static void M_AATreeFree_Node(aatree_node_t *node)
45 {
46 if (node->left) M_AATreeFree_Node(node->left);
47 if (node->right) M_AATreeFree_Node(node->right);
48 Z_Free(node);
49 }
50
M_AATreeFree(aatree_t * aatree)51 void M_AATreeFree(aatree_t *aatree)
52 {
53 if (aatree->root)
54 M_AATreeFree_Node(aatree->root);
55
56 Z_Free(aatree);
57 }
58
M_AATreeSkew(aatree_node_t * node)59 static aatree_node_t *M_AATreeSkew(aatree_node_t *node)
60 {
61 if (node && node->left && node->left->level == node->level)
62 {
63 // Not allowed: horizontal left-link. Reverse the
64 // horizontal link and hook the orphan back in.
65 aatree_node_t *oldleft = node->left;
66 node->left = oldleft->right;
67 oldleft->right = node;
68
69 return oldleft;
70 }
71
72 // No change needed.
73 return node;
74 }
75
M_AATreeSplit(aatree_node_t * node)76 static aatree_node_t *M_AATreeSplit(aatree_node_t *node)
77 {
78 if (node && node->right && node->right->right && node->level == node->right->right->level)
79 {
80 // Not allowed: two consecutive horizontal right-links.
81 // The middle one becomes the new root at this point,
82 // with suitable adjustments below.
83
84 aatree_node_t *oldright = node->right;
85 node->right = oldright->left;
86 oldright->left = node;
87 oldright->level++;
88
89 return oldright;
90 }
91
92 // No change needed.
93 return node;
94 }
95
M_AATreeSet_Node(aatree_node_t * node,UINT32 flags,INT32 key,void * value)96 static aatree_node_t *M_AATreeSet_Node(aatree_node_t *node, UINT32 flags, INT32 key, void* value)
97 {
98 if (!node)
99 {
100 // Nothing here, so just add where we are
101
102 node = Z_Malloc(sizeof (aatree_node_t), PU_STATIC, NULL);
103 node->level = 1;
104 node->key = key;
105 if (value && (flags & AATREE_ZUSER)) Z_SetUser(value, &node->value);
106 else node->value = value;
107 node->left = node->right = NULL;
108 }
109 else
110 {
111 if (key < node->key)
112 node->left = M_AATreeSet_Node(node->left, flags, key, value);
113 else if (key > node->key)
114 node->right = M_AATreeSet_Node(node->right, flags, key, value);
115 else
116 {
117 if (value && (flags & AATREE_ZUSER)) Z_SetUser(value, &node->value);
118 else node->value = value;
119 }
120
121 node = M_AATreeSkew(node);
122 node = M_AATreeSplit(node);
123 }
124
125 return node;
126 }
127
M_AATreeSet(aatree_t * aatree,INT32 key,void * value)128 void M_AATreeSet(aatree_t *aatree, INT32 key, void* value)
129 {
130 aatree->root = M_AATreeSet_Node(aatree->root, aatree->flags, key, value);
131 }
132
133 // Caveat: we don't distinguish between nodes that don't exists
134 // and nodes with value == NULL.
M_AATreeGet_Node(aatree_node_t * node,INT32 key)135 static void *M_AATreeGet_Node(aatree_node_t *node, INT32 key)
136 {
137 if (node)
138 {
139 if (node->key == key)
140 return node->value;
141 else if(node->key < key)
142 return M_AATreeGet_Node(node->right, key);
143 else
144 return M_AATreeGet_Node(node->left, key);
145 }
146
147 return NULL;
148 }
149
M_AATreeGet(aatree_t * aatree,INT32 key)150 void *M_AATreeGet(aatree_t *aatree, INT32 key)
151 {
152 return M_AATreeGet_Node(aatree->root, key);
153 }
154
155
M_AATreeIterate_Node(aatree_node_t * node,aatree_iter_t callback)156 static void M_AATreeIterate_Node(aatree_node_t *node, aatree_iter_t callback)
157 {
158 if (node->left) M_AATreeIterate_Node(node->left, callback);
159 callback(node->key, node->value);
160 if (node->right) M_AATreeIterate_Node(node->right, callback);
161 }
162
M_AATreeIterate(aatree_t * aatree,aatree_iter_t callback)163 void M_AATreeIterate(aatree_t *aatree, aatree_iter_t callback)
164 {
165 if (aatree->root)
166 M_AATreeIterate_Node(aatree->root, callback);
167 }
168