Bug Summary

File:c:\siege\siege/src/siege/util/set.c
Location:line 293, 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 cmp = 1;
82 while(1)
7
←
Loop condition is true. Entering loop body
→
83 {
84 stack[top++] = curr;
85 cmp = set->cmp(curr->item, node->item, set->data);
86
87 if(!cmp)
8
←
Assuming 'cmp' is 0
→
9
←
Taking true branch
→
88 break;
10
←
 Execution continues on line 94
→
89 else if((cmp < 0) ? !curr->right : !curr->left)
90 break;
91 curr = (cmp < 0) ? curr->right : curr->left;
92 }
93
94 if(cmp == 0)
11
←
Taking true branch
→
95 {
96 curr->item = node->item;
97 free(node);
12
←
Memory is released
→
98 return root;
99 }
100
101 if(cmp < 0)
102 curr->right = node;
103 else
104 curr->left = node;
105
106 while(--top >= 0)
107 {
108 if(top)
109 cmp = (stack[top - 1]->right == stack[top]) ? -1 : 1;
110
111 stack[top] = _sgSetNodeSkew(stack[top]);
112 stack[top] = _sgSetNodeSplit(stack[top]);
113
114 if(top)
115 {
116 if(cmp < 0)
117 stack[top - 1]->right = stack[top];
118 else
119 stack[top - 1]->left = stack[top];
120 }
121 else
122 root = stack[top];
123 }
124 }
125 return root;
126}
127SGSetNode* SG_CALL__cdecl _sgSetNodeRemove(SGSet* set, SGSetNode* root, SGSetNode* node)
128{
129 SGSetNode* remove = NULL((void*)0);
130 SGSetNode* curr;
131 SGSetNode* stack[256];
132 ptrdiff_t top;
133 int tcmp;
134 int cmp;
135 SGSetNode* heir;
136 SGSetNode* prev;
137 size_t llevel;
138 size_t rlevel;
139 if(root)
140 {
141 curr = root;
142 top = 0;
143 cmp = 1;
144 while(1)
145 {
146 stack[top++] = curr;
147
148 if(!curr)
149 return root;
150
151 tcmp = set->cmp(curr->item, node->item, set->data);
152 if(!tcmp)
153 break;
154 cmp = tcmp;
155 if(cmp < 0)
156 curr = curr->right;
157 else
158 curr = curr->left;
159 }
160
161 if(!curr->left || !curr->right)
162 {
163 if(--top)
164 {
165 if(cmp < 0)
166 stack[top - 1]->right = curr->left ? curr->left : curr->right;
167 else
168 stack[top - 1]->left = curr->left ? curr->left : curr->right;
169 }
170 else
171 root = curr->right;
172 remove = node;
173 }
174 else
175 {
176 heir = curr->right;
177 prev = curr;
178
179 while(heir->left)
180 {
181 stack[top++] = prev = heir;
182 heir = heir->left;
183 }
184
185 curr->item = heir->item;
186 if(prev == curr)
187 prev->right = heir->right;
188 else
189 prev->left = heir->right;
190 remove = heir;
191 }
192
193 while(--top >= 0)
194 {
195 if(top)
196 cmp = (stack[top - 1]->right == stack[top]) ? -1 : 1;
197
198 llevel = stack[top]->left ? stack[top]->left->level : 0;
199 rlevel = stack[top]->right ? stack[top]->right->level : 0;
200
201 if(llevel < stack[top]->level - 1
202 || rlevel < stack[top]->level - 1)
203 {
204 if(rlevel > --stack[top]->level)
205 stack[top]->right->level = stack[top]->level; // if it's >, then it's definately not 0, thus not NULL
206
207 if(stack[top])
208 {
209 stack[top] = _sgSetNodeSkew(stack[top]);
210 if(stack[top]->right)
211 {
212 stack[top]->right = _sgSetNodeSkew(stack[top]->right);
213 if(stack[top]->right->right)
214 stack[top]->right->right = _sgSetNodeSkew(stack[top]->right->right);
215 }
216 stack[top] = _sgSetNodeSplit(stack[top]);
217 if(stack[top]->right)
218 stack[top]->right = _sgSetNodeSplit(stack[top]->right);
219 }
220 }
221
222 if(top)
223 {
224 if(cmp < 0)
225 stack[top - 1]->right = stack[top];
226 else
227 stack[top - 1]->left = stack[top];
228 }
229 else
230 root = stack[top];
231 }
232 }
233 free(remove);
234 return root;
235}
236
237SGSet* SG_CALL__cdecl sgSetInit(SGSet* set, SGSetCmp* cmp, void* data)
238{
239 if(!set) return NULL((void*)0);
240
241 set->root = NULL((void*)0);
242 set->cmp = cmp;
243 set->data = data;
244 return set;
245}
246void SG_CALL__cdecl sgSetDeinit(SGSet* set)
247{
248 if(!set) return;
249
250 _sgSetDestroyNode(set->root);
251}
252
253SGSet* SG_CALL__cdecl sgSetCreate(SGSetCmp* cmp, void* data)
254{
255 return sgSetInit(malloc(sizeof(SGSet)), cmp, data);
256}
257void SG_CALL__cdecl sgSetDestroy(SGSet* set)
258{
259 sgSetDeinit(set);
260 free(set);
261}
262
263//size_t SG_CALL sgSetNumNodes(SGSet* set);
264
265SGSetNode* SG_CALL__cdecl sgSetSearch(SGSet* set, const void* item)
266{
267 SGSetNode* node = set->root;
268 int cmp;
269 while(node)
270 {
271 cmp = set->cmp(node->item, item, set->data);
272 if(!cmp)
273 break;
274 if(cmp < 0)
275 node = node->right;
276 else
277 node = node->left;
278 }
279 return node;
280}
281
282SGSetNode* SG_CALL__cdecl sgSetInsert(SGSet* set, void* item)
283{
284 SGSetNode* node = malloc(sizeof(SGSetNode));
1
Memory is allocated
→
285 if(!node)
2
←
Assuming 'node' is non-null
→
3
←
Taking false branch
→
286 return NULL((void*)0);
287 //node->parent = NULL;
288 node->left = NULL((void*)0);
289 node->right = NULL((void*)0);
290 node->level = 1;
291 node->item = item;
292 set->root = _sgSetNodeInsert(set, set->root, node);
4
←
Calling '_sgSetNodeInsert'
→
13
←
Returning; memory was released via 3rd parameter
→
293 return node;
14
←
Use of memory after it is freed
294}
295
296void SG_CALL__cdecl sgSetRemoveNode(SGSet* set, SGSetNode* node)
297{
298 set->root = _sgSetNodeRemove(set, set->root, node);
299}
300void SG_CALL__cdecl sgSetRemoveItem(SGSet* set, void* item)
301{
302 SGSetNode* node = sgSetSearch(set, item);
303 if(!node)
304 return;
305 sgSetRemoveNode(set, node);
306}
307
308SGSetNode* SG_CALL__cdecl sgSetGetRoot(SGSet* set)
309{
310 return set->root;
311}
312SGSetNode* SG_CALL__cdecl sgSetGetFirst(SGSet* set)
313{
314 SGSetNode* curr = set->root;
315 if(curr)
316 while(curr->left)
317 curr = curr->left;
318 return curr;
319}
320SGSetNode* SG_CALL__cdecl sgSetGetLast(SGSet* set)
321{
322 SGSetNode* curr = set->root;
323 if(curr)
324 while(curr->right)
325 curr = curr->right;
326 return curr;
327}
328
329void* SG_CALL__cdecl sgSetPopRoot(SGSet* set)
330{
331 SGSetNode* node = sgSetGetRoot(set);
332 if(!node)
333 return NULL((void*)0);
334 void* item = node->item;
335 sgSetRemoveNode(set, node);
336 return item;
337}
338void* SG_CALL__cdecl sgSetPopFirst(SGSet* set)
339{
340 SGSetNode* node = sgSetGetFirst(set);
341 if(!node)
342 return NULL((void*)0);
343 void* item = node->item;
344 sgSetRemoveNode(set, node);
345 return item;
346}
347void* SG_CALL__cdecl sgSetPopLast(SGSet* set)
348{
349 SGSetNode* node = sgSetGetLast(set);
350 if(!node)
351 return NULL((void*)0);
352 void* item = node->item;
353 sgSetRemoveNode(set, node);
354 return item;
355}