Bug Summary

File:c:\siege\siege/src/siege/util/set.c
Location:line 292, column 5
Description:Use of memory after it is freed

Annotated Source Code

1/*
2 * Copyright (c) 2007 SIEGE Development Team
3 * All rights reserved.
4 *
5 * This file is part of libSIEGE.
6 *
7 * This software is copyrighted work licensed under the terms of the
8 * 2-clause BSD license. Please consult the file "COPYING.txt" for
9 * details.
10 *
11 * If you did not recieve the file with this program, please email
12 * Tim Chas <darkuranium@gmail.com>.
13 */
14
15#define SG_BUILD_LIBRARY
16#include <siege/util/set.h>
17
18#include <stdlib.h>
19#include <string.h>
20
21/// \TODO Non-recursive variant of this function.
22void SG_CALL__cdecl _sgSetDestroyNode(SGSetNode* node)
23{
24 if(!node)
25 return;
26 _sgSetDestroyNode(node->left);
27 _sgSetDestroyNode(node->right);
28 free(node);
29}
30
31SGSetNode* SG_CALL__cdecl _sgSetNodeSkew(SGSetNode* node)
32{
33 SGSetNode* ret;
34 size_t level = node->left ? node->left->level : 0;
35 if(level == node->level && node->level)
36 {
37 ret = node->left;
38 node->left = ret ? ret->right : NULL((void*)0);
39 if(ret)
40 ret->right = node;
41 node = ret;
42 }
43 return node;
44}
45SGSetNode* SG_CALL__cdecl _sgSetNodeSplit(SGSetNode* node)
46{
47 SGSetNode* ret;
48 size_t level = node->right ? (node->right->right ? node->right->right->level : 0) : 0;
49 if(level == node->level && node->level)
50 {
51 ret = node->right;
52 node->right = ret ? ret->left : NULL((void*)0);
53 if(ret)
54 ret->left = node;
55 node = ret;
56 node->level++;
57 }
58 return node;
59}
60
61/**
62 * \TODO: Use a dynamic array for the stack...
63 * Update: Maybe not. At stack size of 256,we have (I think?) up to
64 * 2.31584178475e+77 values... Should be enough since this is *way* more than
65 * the typical amount of memory in a computer, nevermind that a single node is
66 * more than 1 byte.
67 */
68SGSetNode* SG_CALL__cdecl _sgSetNodeInsert(SGSet* set, SGSetNode* root, SGSetNode* node)
69{
70 SGSetNode* curr;
71 SGSetNode* stack[256];
72 ptrdiff_t top;
73 int cmp;
74
75 if(!root)
5
←
Assuming 'root' is non-null
→
6
←
Taking false branch
→
76 root = node;
77 else
78 {
79 curr = root;
80 top = 0;
81 for(;;)
7
←
Loop condition is true. Entering loop body
→
82 {
83 stack[top++] = curr;
84 cmp = set->cmp(curr->item, node->item, set->data);
85
86 if(!cmp)
8
←
Assuming 'cmp' is 0
→
9
←
Taking true branch
→
87 break;
10
←
 Execution continues on line 93
→
88 else if((cmp < 0) ? !curr->right : !curr->left)
89 break;
90 curr = (cmp < 0) ? curr->right : curr->left;
91 }
92
93 if(cmp == 0)
11
←
Taking true branch
→
94 {
95 curr->item = node->item;
96 free(node);
12
←
Memory is released
→
97 return root;
98 }
99
100 if(cmp < 0)
101 curr->right = node;
102 else
103 curr->left = node;
104
105 while(--top >= 0)
106 {
107 if(top)
108 cmp = (stack[top - 1]->right == stack[top]) ? -1 : 1;
109
110 stack[top] = _sgSetNodeSkew(stack[top]);
111 stack[top] = _sgSetNodeSplit(stack[top]);
112
113 if(top)
114 {
115 if(cmp < 0)
116 stack[top - 1]->right = stack[top];
117 else
118 stack[top - 1]->left = stack[top];
119 }
120 else
121 root = stack[top];
122 }
123 }
124 return root;
125}
126SGSetNode* SG_CALL__cdecl _sgSetNodeRemove(SGSet* set, SGSetNode* root, SGSetNode* node)
127{
128 SGSetNode* remove = NULL((void*)0);
129 SGSetNode* curr;
130 SGSetNode* stack[256];
131 ptrdiff_t top;
132 int tcmp;
133 int cmp;
134 SGSetNode* heir;
135 SGSetNode* prev;
136 size_t llevel;
137 size_t rlevel;
138 if(root)
139 {
140 curr = root;
141 top = 0;
142 cmp = 1;
143 while(1)
144 {
145 stack[top++] = curr;
146
147 if(!curr)
148 return root;
149
150 tcmp = set->cmp(curr->item, node->item, set->data);
151 if(!tcmp)
152 break;
153 cmp = tcmp;
154 if(cmp < 0)
155 curr = curr->right;
156 else
157 curr = curr->left;
158 }
159
160 if(!curr->left || !curr->right)
161 {
162 if(--top)
163 {
164 if(cmp < 0)
165 stack[top - 1]->right = curr->left ? curr->left : curr->right;
166 else
167 stack[top - 1]->left = curr->left ? curr->left : curr->right;
168 }
169 else
170 root = curr->right;
171 remove = node;
172 }
173 else
174 {
175 heir = curr->right;
176 prev = curr;
177
178 while(heir->left)
179 {
180 stack[top++] = prev = heir;
181 heir = heir->left;
182 }
183
184 curr->item = heir->item;
185 if(prev == curr)
186 prev->right = heir->right;
187 else
188 prev->left = heir->right;
189 remove = heir;
190 }
191
192 while(--top >= 0)
193 {
194 if(top)
195 cmp = (stack[top - 1]->right == stack[top]) ? -1 : 1;
196
197 llevel = stack[top]->left ? stack[top]->left->level : 0;
198 rlevel = stack[top]->right ? stack[top]->right->level : 0;
199
200 if(llevel < stack[top]->level - 1
201 || rlevel < stack[top]->level - 1)
202 {
203 if(rlevel > --stack[top]->level)
204 stack[top]->right->level = stack[top]->level; // if it's >, then it's definately not 0, thus not NULL
205
206 if(stack[top])
207 {
208 stack[top] = _sgSetNodeSkew(stack[top]);
209 if(stack[top]->right)
210 {
211 stack[top]->right = _sgSetNodeSkew(stack[top]->right);
212 if(stack[top]->right->right)
213 stack[top]->right->right = _sgSetNodeSkew(stack[top]->right->right);
214 }
215 stack[top] = _sgSetNodeSplit(stack[top]);
216 if(stack[top]->right)
217 stack[top]->right = _sgSetNodeSplit(stack[top]->right);
218 }
219 }
220
221 if(top)
222 {
223 if(cmp < 0)
224 stack[top - 1]->right = stack[top];
225 else
226 stack[top - 1]->left = stack[top];
227 }
228 else
229 root = stack[top];
230 }
231 }
232 free(remove);
233 return root;
234}
235
236SGSet* SG_CALL__cdecl sgSetInit(SGSet* set, SGSetCmp* cmp, void* data)
237{
238 if(!set) return NULL((void*)0);
239
240 set->root = NULL((void*)0);
241 set->cmp = cmp;
242 set->data = data;
243 return set;
244}
245void SG_CALL__cdecl sgSetDeinit(SGSet* set)
246{
247 if(!set) return;
248
249 _sgSetDestroyNode(set->root);
250}
251
252SGSet* SG_CALL__cdecl sgSetCreate(SGSetCmp* cmp, void* data)
253{
254 return sgSetInit(malloc(sizeof(SGSet)), cmp, data);
255}
256void SG_CALL__cdecl sgSetDestroy(SGSet* set)
257{
258 sgSetDeinit(set);
259 free(set);
260}
261
262//size_t SG_CALL sgSetNumNodes(SGSet* set);
263
264SGSetNode* SG_CALL__cdecl sgSetSearch(SGSet* set, const void* item)
265{
266 SGSetNode* node = set->root;
267 int cmp;
268 while(node)
269 {
270 cmp = set->cmp(node->item, item, set->data);
271 if(!cmp)
272 break;
273 if(cmp < 0)
274 node = node->right;
275 else
276 node = node->left;
277 }
278 return node;
279}
280
281SGSetNode* SG_CALL__cdecl sgSetInsert(SGSet* set, void* item)
282{
283 SGSetNode* node = malloc(sizeof(SGSetNode));
1
Memory is allocated
→
284 if(!node) return NULL((void*)0);
2
←
Assuming 'node' is non-null
→
3
←
Taking false branch
→
285 //node->parent = NULL;
286 node->left = NULL((void*)0);
287 node->right = NULL((void*)0);
288 node->level = 1;
289 node->item = item;
290 set->root = _sgSetNodeInsert(set, set->root, node);
4
←
Calling '_sgSetNodeInsert'
→
13
←
Returning; memory was released via 3rd parameter
→
291 if(!set->root) return NULL((void*)0);
14
←
Taking false branch
→
292 return node;
15
←
Use of memory after it is freed
293}
294
295void SG_CALL__cdecl sgSetRemoveNode(SGSet* set, SGSetNode* node)
296{
297 set->root = _sgSetNodeRemove(set, set->root, node);
298}
299void SG_CALL__cdecl sgSetRemoveItem(SGSet* set, void* item)
300{
301 SGSetNode* node = sgSetSearch(set, item);
302 if(!node)
303 return;
304 sgSetRemoveNode(set, node);
305}
306
307SGSetNode* SG_CALL__cdecl sgSetGetRoot(SGSet* set)
308{
309 return set->root;
310}
311SGSetNode* SG_CALL__cdecl sgSetGetFirst(SGSet* set)
312{
313 SGSetNode* curr = set->root;
314 if(curr)
315 while(curr->left)
316 curr = curr->left;
317 return curr;
318}
319SGSetNode* SG_CALL__cdecl sgSetGetLast(SGSet* set)
320{
321 SGSetNode* curr = set->root;
322 if(curr)
323 while(curr->right)
324 curr = curr->right;
325 return curr;
326}
327
328void* SG_CALL__cdecl sgSetPopRoot(SGSet* set)
329{
330 SGSetNode* node = sgSetGetRoot(set);
331 if(!node)
332 return NULL((void*)0);
333 void* item = node->item;
334 sgSetRemoveNode(set, node);
335 return item;
336}
337void* SG_CALL__cdecl sgSetPopFirst(SGSet* set)
338{
339 SGSetNode* node = sgSetGetFirst(set);
340 if(!node)
341 return NULL((void*)0);
342 void* item = node->item;
343 sgSetRemoveNode(set, node);
344 return item;
345}
346void* SG_CALL__cdecl sgSetPopLast(SGSet* set)
347{
348 SGSetNode* node = sgSetGetLast(set);
349 if(!node)
350 return NULL((void*)0);
351 void* item = node->item;
352 sgSetRemoveNode(set, node);
353 return item;
354}