summaryrefslogtreecommitdiff
path: root/src/lib/eina
diff options
context:
space:
mode:
authorCarsten Haitzler (Rasterman) <raster@rasterman.com>2013-11-28 18:00:25 +0900
committerCarsten Haitzler (Rasterman) <raster@rasterman.com>2013-11-28 18:03:54 +0900
commit523d8607d19eff04c5f820334955c4999ceb250b (patch)
tree21033d059acc762240ddc31ea6246e10a969357e /src/lib/eina
parent403e97ecb08392cb7376cef024f4fff480efcff3 (diff)
fix eina_array_remove to actually realloc down in size to remove bloat
eina_array_remove() didnt ever realloc down unless we went to 0 members. this wasn't very good as you'd expect the array to be reduced in size if enough items were removed. not only that the old code was stupid and ALWAYS malloc()ed a new array of the exact same size and copied items over in the most complex way possible, then freed the old one. this would have added overhead wherever used (evas_render) that should not have been there. this is based on the idea in a patch from Viacheslav Lvov <v.lvov@samsung.com>, but this is a re-do of it entirely, reducing the codebase massively even compared to the patch and making it much simpler to read, maintain, actually reduce memory and cut overhead.
Diffstat (limited to 'src/lib/eina')
-rw-r--r--src/lib/eina/eina_array.c85
1 files changed, 22 insertions, 63 deletions
diff --git a/src/lib/eina/eina_array.c b/src/lib/eina/eina_array.c
index ff727f34eb..ab853a01ea 100644
--- a/src/lib/eina/eina_array.c
+++ b/src/lib/eina/eina_array.c
@@ -330,87 +330,46 @@ eina_array_remove(Eina_Array *array, Eina_Bool (*keep)(void *data,
330 void *gdata), 330 void *gdata),
331 void *gdata) 331 void *gdata)
332{ 332{
333 void **tmp; 333 unsigned int i, j, size, count;
334 /* WARNING: 334 void *data, **tmp;
335 The algorithm does exit before using unitialized data. So compiler is
336 giving you a false positiv here too.
337 */
338 void *data = NULL;
339 unsigned int total = 0;
340 unsigned int limit;
341 unsigned int i;
342 335
343 EINA_SAFETY_ON_NULL_RETURN_VAL(array, EINA_FALSE); 336 EINA_SAFETY_ON_NULL_RETURN_VAL(array, EINA_FALSE);
344 EINA_SAFETY_ON_NULL_RETURN_VAL(keep, EINA_FALSE); 337 EINA_SAFETY_ON_NULL_RETURN_VAL(keep, EINA_FALSE);
345 EINA_MAGIC_CHECK_ARRAY(array); 338 EINA_MAGIC_CHECK_ARRAY(array);
346 339
347 if (array->total == 0) 340 if (array->total == 0) return EINA_TRUE;
348 return EINA_TRUE; 341 // 1. walk through all items and shuffle down any items on top of
349 342 // previously removed item slots
350 for (i = 0; i < array->count; ++i) 343 for (count = array->count, tmp = array->data, j = 0, i = 0; i < count; i++)
351 {
352 data = eina_array_data_get(array, i);
353
354 if (keep(data, gdata) == EINA_FALSE)
355 break;
356 }
357 limit = i;
358 if (i < array->count)
359 ++i;
360
361 for (; i < array->count; ++i)
362 { 344 {
363 data = eina_array_data_get(array, i); 345 data = tmp[i];
364
365 if (keep(data, gdata) == EINA_TRUE) 346 if (keep(data, gdata) == EINA_TRUE)
366 break; 347 {
348 // we keep it - store it (again) (and j will be <= i ALWAYS)
349 tmp[j] = data;
350 j++;
351 }
367 } 352 }
368 /* Special case all objects that need to stay are at the beginning of the array. */ 353 array->count = j;
369 if (i == array->count) 354 // 2. if we reduced size by more than N (block size) then realloc back down
355 if ((array->total - array->count) >= array->step)
370 { 356 {
371 array->count = limit;
372 if (array->count == 0) 357 if (array->count == 0)
373 { 358 {
374 free(array->data); 359 free(array->data);
375 array->total = 0; 360 array->total = 0;
376 array->data = NULL; 361 array->data = NULL;
377 } 362 }
378 363 else
379 return EINA_TRUE;
380 }
381
382 tmp = malloc(sizeof (void *) * array->total);
383 if (!tmp) return EINA_FALSE;
384
385 memcpy(tmp, array->data, limit * sizeof(void *));
386 total = limit;
387
388 if (i < array->count)
389 {
390 tmp[total] = data;
391 total++;
392 ++i;
393 }
394
395 for (; i < array->count; ++i)
396 {
397 data = eina_array_data_get(array, i);
398
399 if (keep(data, gdata))
400 { 364 {
401 tmp[total] = data; 365 // realloc back down - rounding up to the nearest step size
402 total++; 366 size = (array->count + array->step - 1) % array->step;
367 tmp = realloc(array->data, sizeof(void *) * size);
368 if (!tmp) return EINA_FALSE;
369 array->total = size;
370 array->data = tmp;
403 } 371 }
404 } 372 }
405
406 free(array->data);
407
408 /* If we do not keep any object in the array, we should have exited
409 earlier in test (i == array->count). */
410 assert(total != 0);
411
412 array->data = tmp;
413 array->count = total;
414 return EINA_TRUE; 373 return EINA_TRUE;
415} 374}
416 375