Bug Summary

File:src/air/heap.c
Location:line 152, column 3
Description:Null pointer argument in call to memory copy function

Annotated Source Code

1/*
2 Teem: Tools to process and visualize scientific data and images .
3 Copyright (C) 2010 Thomas Schultz
4
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public License
7 (LGPL) as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9 The terms of redistributing and/or modifying this software also
10 include exceptions to the LGPL that facilitate static linking.
11
12 This library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Lesser General Public License for more details.
16
17 You should have received a copy of the GNU Lesser General Public License
18 along with this library; if not, write to Free Software Foundation, Inc.,
19 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20*/
21
22#include "air.h"
23#include <string.h>
24
25/* internal helper routines */
26/* restore heap property by pulling a single node up the tree */
27static void upheap(airHeap *h, unsigned int i) {
28 while (i) {
29 unsigned int parent = (i-1)/2;
30 if (h->key[h->idx[parent]] > h->key[h->idx[i]]) { /* swap */
31 unsigned int tmp = h->idx[parent];
32 h->idx[parent] = h->idx[i];
33 h->idx[i] = tmp;
34 h->invidx[h->idx[i]] = i;
35 h->invidx[h->idx[parent]] = parent;
36 i = parent;
37 } else
38 i = 0; /* break loop */
39 }
40}
41
42/* restore heap property by pushing a single node down the tree */
43static void downheap (airHeap *h, unsigned int i) {
44 unsigned int len = h->key_a->len;
45 while (1) {
46 unsigned int left = 2*i+1;
47 unsigned int right = 2*i+2;
48 unsigned int minidx = 0;
49 double minval = 0;
50 if (left>=len)
51 return;
52 if ((right>=len) ||
53 (h->key[h->idx[left]] < h->key[h->idx[right]])) {
54 minidx = left;
55 minval = h->key[h->idx[left]];
56 } else {
57 minidx = right;
58 minval = h->key[h->idx[right]];
59 }
60 if (h->key[h->idx[i]] > minval) { /* swap */
61 unsigned int tmp = h->idx[i];
62 h->idx[i] = h->idx[minidx];
63 h->idx[minidx] = tmp;
64 h->invidx[h->idx[i]] = i;
65 h->invidx[h->idx[minidx]] = minidx;
66 i = minidx;
67 } else
68 return;
69 }
70}
71
72/* Restore heap property "from scratch" (without any prior assumptions).
73 * Works in a bottom-up manner, which is more efficient than top-down */
74static void heapify (airHeap *h) {
75 unsigned int len = h->key_a->len;
76 int maxi = len/2-1, i; /* above maxi, downheap has no effect */
77 for (i=maxi; i>=0; i--) {
78 downheap(h, i);
79 }
80}
81
82/* Tries to increase or decrease the length of h. returns 0 upon success. */
83static int heapLenIncr (airHeap *h, int delta) {
84 unsigned int oldlen=h->key_a->len;
85 unsigned int newlen=oldlen+delta;
86 if (delta==0)
12
←
Assuming 'delta' is not equal to 0
→
13
←
Taking false branch
→
87 return 0;
88 airArrayLenIncr(h->key_a, delta);
89 if (h->data_a!=NULL((void*)0)) airArrayLenIncr(h->data_a, delta);
14
←
Taking false branch
→
90 airArrayLenIncr(h->idx_a, delta);
91 airArrayLenIncr(h->invidx_a, delta);
92 if (h->key_a->len<newlen || (h->data_a!=NULL((void*)0) && h->data_a->len<newlen) ||
15
←
Taking false branch
→
93 h->idx_a->len<newlen || h->invidx_a->len<newlen) {
94 /* Error. Try to undo changes and return error code. */
95 if (h->key_a->len>oldlen) airArrayLenSet(h->key_a, oldlen);
96 if (h->data_a!=NULL((void*)0) && h->data_a->len>oldlen)
97 airArrayLenSet(h->data_a, oldlen);
98 if (h->idx_a->len>oldlen) airArrayLenSet(h->idx_a, oldlen);
99 if (h->invidx_a->len>oldlen) airArrayLenSet(h->invidx_a, oldlen);
100 return 1;
101 }
102 return 0;
103}
104
105/* Creates a new heap, returning NULL upon error. If additional data
106 * is to be stored with each node, dataUnit needs to be set to the
107 * number of data bytes needed per element. incr is used for dynamic
108 * memory allocation (an additional number of incr elements are
109 * allocated each time the heap grows past its current capacity).
110 */
111airHeap *airHeapNew(size_t dataUnit, unsigned int incr) {
112 airHeap *h;
113 airPtrPtrUnion appu;
114 h = AIR_CALLOC(1, airHeap)(airHeap*)(calloc((1), sizeof(airHeap)));
5
←
Within the expansion of the macro 'AIR_CALLOC':
→
a
Null pointer value stored to field 'key'
115 if (h==NULL((void*)0)) {
6
←
Assuming 'h' is not equal to null
→
7
←
Taking false branch
→
116 return NULL((void*)0);
117 }
118
119 appu.d = &h->key;
120 h->key_a = airArrayNew(appu.v, NULL((void*)0), sizeof(double), incr);
121 if (dataUnit>0) { /* data is optional */
8
←
Taking false branch
→
122 h->data_a = airArrayNew(&h->data, NULL((void*)0), dataUnit, incr);
123 }
124 appu.ui = &h->idx;
125 h->idx_a = airArrayNew(appu.v, NULL((void*)0), sizeof(unsigned int), incr);
126 appu.ui = &h->invidx;
127 h->invidx_a = airArrayNew(appu.v, NULL((void*)0), sizeof(unsigned int), incr);
128
129 if (h->key_a==NULL((void*)0) || (dataUnit>0 && h->data_a==NULL((void*)0)) || h->idx_a==NULL((void*)0) ||
9
←
Taking false branch
→
130 h->invidx_a==NULL((void*)0)) { /* allocation failed (partly) */
131 airHeapNix(h);
132 return NULL((void*)0);
133 }
134 return h;
135}
136
137/* Same as airHeapNew, but initializes the new heap with the keys from key
138 * and the optional data from data. If data is non-NULL, it needs to
139 * have the same length as key, or this function will fail. The incr
140 * field of the heap is copied from key (rather than data).
141 */
142airHeap *airHeapFromArray(const airArray *key, const airArray *data) {
143 airHeap *h;
144 unsigned int i;
145 if (key==NULL((void*)0) || (data!=NULL((void*)0) && data->len!=key->len))
1
Assuming 'key' is not equal to null
→
2
←
Assuming 'data' is equal to null
→
146 return NULL((void*)0); /* unusable input */
147 h = airHeapNew((data==NULL((void*)0))?0:data->unit, key->incr);
3
←
'?' condition is true
→
4
←
Calling 'airHeapNew'
→
10
←
Returning from 'airHeapNew'
→
148 if (heapLenIncr (h, key->len)) { /* could not allocate memory */
11
←
Calling 'heapLenIncr'
→
16
←
Returning from 'heapLenIncr'
→
17
←
Taking false branch
→
149 airHeapNix(h);
150 return NULL((void*)0);
151 }
152 memcpy(h->key, key->data, key->len*sizeof(double))__builtin___memcpy_chk (h->key, key->data, key->len*
sizeof(double), __builtin_object_size (h->key, 0));
18
←
Within the expansion of the macro 'memcpy':
a
Null pointer argument in call to memory copy function
153 if (h->data_a!=NULL((void*)0)) memcpy(h->data, data->data, data->len*data->unit)__builtin___memcpy_chk (h->data, data->data, data->len
*data->unit, __builtin_object_size (h->data, 0));
154 for (i=0; i<key->len; i++) { /* initialize indices to identity */
155 h->idx[i]=i;
156 h->invidx[i]=i;
157 }
158 heapify(h);
159 return h;
160}
161
162/* Frees all memory associated with the heap and its data */
163airHeap *airHeapNix(airHeap *h) {
164 if (h!=NULL((void*)0)) {
165 airArrayNuke(h->key_a);
166 if (h->data_a!=NULL((void*)0)) airArrayNuke(h->data_a);
167 airArrayNuke(h->idx_a);
168 airArrayNuke(h->invidx_a);
169 free(h);
170 }
171 return NULL((void*)0);
172}
173
174/* Returns the number of elements that are currently in heap h
175 * (or 0 if h==NULL) */
176unsigned int airHeapLength(const airHeap *h) {
177 if (h!=NULL((void*)0)) {
178 return h->key_a->len;
179 } else
180 return 0;
181}
182
183/* Inserts a key into the heap. data is copied over (deep copy) when the
184 * heap was initialized to hold additional data. Otherwise, it is ignored.
185 *
186 * Returns the new number of elements in h.
187 * Upon error, this can be the same as the old length. */
188unsigned int airHeapInsert(airHeap *h, double key, const void *data) {
189 unsigned int oldlen;
190 if (h==NULL((void*)0)) return 0;
191 oldlen = h->key_a->len;
192 /* make space for the new element */
193 if (heapLenIncr(h, 1))
194 return oldlen;
195 h->key[oldlen]=key;
196 if (h->data_a!=NULL((void*)0) && data!=NULL((void*)0)) {
197 memcpy((char*)h->data_a->data+oldlen*h->data_a->unit, data,__builtin___memcpy_chk ((char*)h->data_a->data+oldlen*h
->data_a->unit, data, h->data_a->unit, __builtin_object_size
((char*)h->data_a->data+oldlen*h->data_a->unit, 0
))
198 h->data_a->unit)__builtin___memcpy_chk ((char*)h->data_a->data+oldlen*h
->data_a->unit, data, h->data_a->unit, __builtin_object_size
((char*)h->data_a->data+oldlen*h->data_a->unit, 0
));
199 }
200 h->idx[oldlen]=oldlen;
201 h->invidx[oldlen]=oldlen;
202 upheap(h,oldlen); /* restore the heap property */
203 return oldlen+1;
204}
205
206/* Merges the second heap into the first. Returns the new length of first,
207 * or zero upon error. */
208unsigned int airHeapMerge(airHeap *first, const airHeap *second) {
209 unsigned int first_len, second_len, i;
210 if (first==NULL((void*)0) || second==NULL((void*)0))
211 return 0;
212 if ((first->data_a==NULL((void*)0)) ^ (second->data_a==NULL((void*)0)))
213 return 0; /* incompatible data */
214 if (first->data_a!=NULL((void*)0) &&
215 (first->data_a->unit!=second->data_a->unit))
216 return 0; /* incompatible data */
217 /* make sufficient space in first */
218 first_len = first->key_a->len;
219 second_len = second->key_a->len;
220 if (heapLenIncr(first, second_len))
221 return 0;
222 /* concatenate and heapify */
223 memcpy(first->key+first_len, second->key, second_len*sizeof(double))__builtin___memcpy_chk (first->key+first_len, second->key
, second_len*sizeof(double), __builtin_object_size (first->
key+first_len, 0));
224 if (first->data_a!=NULL((void*)0))
225 memcpy((char*)first->data_a->data+first_len*first->data_a->unit,__builtin___memcpy_chk ((char*)first->data_a->data+first_len
*first->data_a->unit, second->data_a->data, second_len
*second->data_a->unit, __builtin_object_size ((char*)first
->data_a->data+first_len*first->data_a->unit, 0))
226 second->data_a->data,second_len*second->data_a->unit)__builtin___memcpy_chk ((char*)first->data_a->data+first_len
*first->data_a->unit, second->data_a->data, second_len
*second->data_a->unit, __builtin_object_size ((char*)first
->data_a->data+first_len*first->data_a->unit, 0));
227 for (i=0; i<second_len; i++) {
228 first->idx[first_len+i] = first_len+second->idx[i];
229 first->invidx[first->idx[first_len+i]]=first_len+i;
230 }
231 heapify(first);
232 return first_len+second_len;
233}
234
235/* Returns the key of the front element in the heap and optionally copies the
236 * associated data to *data. Does not modify the heap. */
237double airHeapFrontPeek(const airHeap *h, void *data) {
238 if (h==NULL((void*)0) || h->key_a->len==0)
239 return 0.0;
240 if (data!=NULL((void*)0) && h->data_a!=NULL((void*)0))
241 memcpy(data, (char*)h->data_a->data+h->idx[0]*h->data_a->unit,__builtin___memcpy_chk (data, (char*)h->data_a->data+h->
idx[0]*h->data_a->unit, h->data_a->unit, __builtin_object_size
(data, 0))
242 h->data_a->unit)__builtin___memcpy_chk (data, (char*)h->data_a->data+h->
idx[0]*h->data_a->unit, h->data_a->unit, __builtin_object_size
(data, 0));
243 return h->key[h->idx[0]];
244}
245
246/* Same as airHeapFrontPeek, but additionally removes the front element. */
247double airHeapFrontPop(airHeap *h, void *data) {
248 double retval = airHeapFrontPeek(h, data);
249 if (h!=NULL((void*)0) && h->key_a->len>0) {
250 airHeapRemove(h, h->idx[0]);
251 }
252 return retval;
253}
254
255/* Assigns a new key (and optionally, new data) to the front element and
256 * re-sorts the heap if necessary. */
257int airHeapFrontUpdate(airHeap *h, double newKey, const void *newData) {
258 if (h==NULL((void*)0) || h->key_a->len==0)
259 return 1;
260 if (newData!=NULL((void*)0) && h->data_a!=NULL((void*)0))
261 memcpy((char*)h->data_a->data+h->idx[0]*h->data_a->unit, newData,__builtin___memcpy_chk ((char*)h->data_a->data+h->idx
[0]*h->data_a->unit, newData, h->data_a->unit, __builtin_object_size
((char*)h->data_a->data+h->idx[0]*h->data_a->
unit, 0))
262 h->data_a->unit)__builtin___memcpy_chk ((char*)h->data_a->data+h->idx
[0]*h->data_a->unit, newData, h->data_a->unit, __builtin_object_size
((char*)h->data_a->data+h->idx[0]*h->data_a->
unit, 0));
263 h->key[h->idx[0]]=newKey;
264 downheap(h, 0);
265 return 0;
266}
267
268/* The following functions provide advanced functionality and should
269 * not be required in most applications. */
270
271/* airHeapFind returns 0 if an element is found whose data is bitwise
272 * equal to the given data, and sets *ai to the index of this
273 * element. If more than one element matches the data, an arbitrary
274 * one of them is returned. The index can be used with airHeapRemove
275 * or airHeapUpdate, but will become invalid as soon as any element is
276 * removed from the heap. */
277int airHeapFind(const airHeap *h, unsigned int *ai, const void *data) {
278 unsigned int i;
279 if (h==NULL((void*)0) || ai==NULL((void*)0) || data==NULL((void*)0) || h->data_a==NULL((void*)0))
280 return 1;
281 for (i=0; i<h->key_a->len; i++) {
282 if (!memcmp((char*)h->data_a->data+i*h->data_a->unit, data,
283 h->data_a->unit)) {
284 *ai = i;
285 return 0;
286 }
287 }
288 return 1;
289}
290
291/* Removes element ai from the heap, returns 0 upon success. */
292int airHeapRemove(airHeap *h, unsigned int ai) {
293 unsigned int old_invidx_ai;
294 if (h==NULL((void*)0) || h->key_a->len<=ai)
295 return 1;
296 /* in the tree, replace ai with last element */
297 old_invidx_ai=h->invidx[ai];
298 h->idx[h->invidx[ai]]=h->idx[h->key_a->len-1];
299 h->invidx[h->idx[h->key_a->len-1]]=h->invidx[ai];
300 /* remove ai - copy last element over, then drop it */
301 if (ai!=h->key_a->len-1) {
302 h->key[ai]=h->key[h->key_a->len-1];
303 if (h->data_a!=NULL((void*)0)) {
304 memcpy((char*)h->data_a->data+ai*h->data_a->unit,__builtin___memcpy_chk ((char*)h->data_a->data+ai*h->
data_a->unit, (char*)h->data_a->data+(h->key_a->
len-1)*h->data_a->unit, h->data_a->unit, __builtin_object_size
((char*)h->data_a->data+ai*h->data_a->unit, 0))
305 (char*)h->data_a->data+(h->key_a->len-1)*h->data_a->unit,__builtin___memcpy_chk ((char*)h->data_a->data+ai*h->
data_a->unit, (char*)h->data_a->data+(h->key_a->
len-1)*h->data_a->unit, h->data_a->unit, __builtin_object_size
((char*)h->data_a->data+ai*h->data_a->unit, 0))
306 h->data_a->unit)__builtin___memcpy_chk ((char*)h->data_a->data+ai*h->
data_a->unit, (char*)h->data_a->data+(h->key_a->
len-1)*h->data_a->unit, h->data_a->unit, __builtin_object_size
((char*)h->data_a->data+ai*h->data_a->unit, 0));
307 }
308 h->idx[h->invidx[h->key_a->len-1]]=ai;
309 h->invidx[ai]=h->invidx[h->key_a->len-1];
310 }
311 heapLenIncr(h, -1);
312 /* push moved element downheap */
313 if (old_invidx_ai<h->key_a->len)
314 downheap(h, old_invidx_ai);
315 return 0;
316}
317
318/* Changes the key (and optional data) of the element ai, re-sorting
319 * the heap if necessary. Returns 0 upon success. */
320int airHeapUpdate(airHeap *h, unsigned int ai, double newKey,
321 const void *newData) {
322 double oldkey;
323 if (h==NULL((void*)0) || h->key_a->len<=ai)
324 return 1;
325 oldkey = h->key[ai];
326 /* replace key and data */
327 h->key[ai] = newKey;
328 if (h->data_a!=NULL((void*)0) && newData!=NULL((void*)0)) {
329 memcpy((char*)h->data_a->data+ai*h->data_a->unit,__builtin___memcpy_chk ((char*)h->data_a->data+ai*h->
data_a->unit, newData, h->data_a->unit, __builtin_object_size
((char*)h->data_a->data+ai*h->data_a->unit, 0))
330 newData, h->data_a->unit)__builtin___memcpy_chk ((char*)h->data_a->data+ai*h->
data_a->unit, newData, h->data_a->unit, __builtin_object_size
((char*)h->data_a->data+ai*h->data_a->unit, 0));
331 }
332 if (oldkey<newKey) downheap(h, h->invidx[ai]);
333 else upheap(h, h->invidx[ai]);
334 return 0;
335}