[libical] Allocate ical arrays in chunks to keep pointers stable (bug 3514871)
Keith Packard
keithp at keithp.com
Fri Apr 27 13:22:29 PDT 2012
Ical arrays are allocated as a monolithic block of data, which is nice
and space efficient. However, because ical exposes pointers to arrays to
applications, it's important for these pointers to remain stable across
array reallocation, especially for timezone information.
Here's a patch which changes how arrays are managed, allocating a new
block of data for each increment of new objects. This retains the O(1)
behaviour of fetching and storing data, amortizes allocation overhead
for multiple objects and makes inserting objects nominally faster
(copying only the array of pointers to chunks, and not the data itself).
It does introduce a performance regression for sort, when sorting more
objects than can be held in a single chunk.
This keeps evolution from crashing...
----------------------
Description: Allocate icalarray data in chunks
Allocating the icalarray data in chunks makes the pointers
to the data stable across resize.
.
libical (0.48-2) unstable; urgency=low
.
* Change icalarray to chunks
Author: Keith Packard <keithp at keithp.com>
Origin: author
Bug: http://sourceforge.net/tracker/?func=detail&aid=3514871&group_id=16077&atid=116077
---
--- libical-0.48.orig/src/libical/icalarray.c
+++ libical-0.48/src/libical/icalarray.c
@@ -38,7 +38,6 @@
#include "icalarray.h"
#include "icalerror.h"
-
static void icalarray_expand (icalarray *array,
int space_needed);
@@ -61,15 +60,25 @@ icalarray_new (int element_size,
array->increment_size = increment_size;
array->num_elements = 0;
array->space_allocated = 0;
- array->data = NULL;
+ array->chunks = NULL;
return array;
}
+static void *
+icalarray_alloc_chunk(icalarray *array)
+{
+ void *chunk = malloc(array->element_size * array->increment_size);
+ if (!chunk)
+ icalerror_set_errno(ICAL_NEWFAILED_ERROR);
+ return chunk;
+}
icalarray *icalarray_copy (icalarray *originalarray)
{
icalarray *array = icalarray_new(originalarray->element_size, originalarray->increment_size);
+ int chunks = originalarray->space_allocated / originalarray->increment_size;
+ int chunk;
if (!array)
return NULL;
@@ -77,15 +86,18 @@ icalarray *icalarray_copy (icalarray *or
array->num_elements = originalarray->num_elements;
array->space_allocated = originalarray->space_allocated;
- array->data = malloc(array->space_allocated * array->element_size);
-
- if (array->data) {
- memcpy(array->data, originalarray->data,
- array->element_size*array->space_allocated);
+ array->chunks = malloc(chunks * sizeof (void *));
+ if (array->chunks) {
+ for (chunk = 0; chunk < chunks; chunk++) {
+ array->chunks[chunk] = icalarray_alloc_chunk(array);
+ if (array->chunks[chunk])
+ memcpy(array->chunks[chunk], originalarray->chunks[chunk],
+ array->increment_size * array->element_size);
+ }
} else {
icalerror_set_errno(ICAL_ALLOCATION_ERROR);
}
-
+
return array;
}
@@ -96,9 +108,13 @@ icalarray *icalarray_copy (icalarray *or
void
icalarray_free (icalarray *array)
{
- if (array->data) {
- free (array->data);
- array->data = 0;
+ if (array->chunks) {
+ int chunks = array->space_allocated / array->increment_size;
+ int chunk;
+ for (chunk = 0; chunk < chunks; chunk++)
+ free(array->chunks[chunk]);
+ free (array->chunks);
+ array->chunks = 0;
}
free (array);
array = 0;
@@ -109,12 +125,12 @@ void
icalarray_append (icalarray *array,
const void *element)
{
+ int pos;
if (array->num_elements >= array->space_allocated)
icalarray_expand (array, 1);
- memcpy ((char *)(array->data) + ( array->num_elements * array->element_size ), element,
- array->element_size);
- array->num_elements++;
+ pos = array->num_elements++;
+ memcpy (icalarray_element_at(array, pos), element, array->element_size);
}
@@ -122,10 +138,12 @@ void*
icalarray_element_at (icalarray *array,
int position)
{
+ int chunk = position / array->increment_size;
+ int offset = position % array->increment_size;
assert (position >= 0);
assert ((unsigned int)position < array->num_elements);
- return (char *)(array->data) + (position * array->element_size);
+ return (char *)(array->chunks[chunk]) + (offset * array->element_size);
}
@@ -139,13 +157,12 @@ icalarray_remove_element_at (icalarray *
assert (position >= 0);
assert ((unsigned int)position < array->num_elements);
- dest = (char *)array->data + (position * array->element_size);
- elements_to_move = array->num_elements - position - 1;
-
- if (elements_to_move > 0)
- memmove (dest, (char *)dest + array->element_size,
- elements_to_move * array->element_size);
-
+ while (position < array->num_elements - 1) {
+ memmove(icalarray_element_at(array, position),
+ icalarray_element_at(array, position + 1),
+ array->element_size);
+ position++;
+ }
array->num_elements--;
}
@@ -155,7 +172,22 @@ icalarray_sort (icalarray *array,
int (*compare) (const void *,
const void *))
{
- qsort (array->data, array->num_elements, array->element_size, compare);
+ if (array->num_elements <= array->increment_size) {
+ qsort(array->chunks[0], array->num_elements, array->element_size, compare);
+ } else {
+ int pos;
+ void *tmp = malloc (array->num_elements * array->element_size);
+ if (!tmp)
+ return;
+ for (pos = 0; pos < array->num_elements; pos++)
+ memcpy((char *) tmp + array->element_size * pos, icalarray_element_at(array, pos), array->element_size);
+
+ qsort (tmp, array->num_elements, array->element_size, compare);
+
+ for (pos = 0; pos < array->num_elements; pos++)
+ memcpy(icalarray_element_at(array, pos), (char *) tmp + array->element_size * pos, array->element_size);
+ free (tmp);
+ }
}
@@ -163,31 +195,27 @@ static void
icalarray_expand (icalarray *array,
int space_needed)
{
- int new_space_allocated;
- void *new_data;
-
- new_space_allocated = array->space_allocated + array->increment_size;
-
- if ((unsigned int)space_needed > array->increment_size)
- new_space_allocated += space_needed;
-
- /*
- new_data = realloc (array->data,
- new_space_allocated * array->element_size);
- */
- new_data = malloc(new_space_allocated * array->element_size);
-
- if (new_data) {
- memcpy(new_data,array->data,array->element_size*array->space_allocated);
- if (array->data) {
- free(array->data);
- array->data = 0;
- }
- array->data = new_data;
- array->space_allocated = new_space_allocated;
- } else {
+ int num_chunks = array->space_allocated / array->increment_size;
+ int num_new_chunks;
+ int c;
+ void **new_chunks;
+
+ num_new_chunks = (space_needed + array->increment_size - 1) / array->increment_size;
+ if (!num_new_chunks)
+ num_new_chunks = 1;
+
+ new_chunks = malloc ((num_chunks + num_new_chunks) * sizeof (void *));
+
+ if (new_chunks) {
+ memcpy(new_chunks, array->chunks, num_chunks * sizeof (void *));
+ for (c = 0; c < num_new_chunks; c++)
+ new_chunks[c + num_chunks] = icalarray_alloc_chunk(array);
+ if (array->chunks)
+ free (array->chunks);
+ array->chunks = new_chunks;
+ array->space_allocated = array->space_allocated + num_new_chunks * array->increment_size;
+ } else
icalerror_set_errno(ICAL_ALLOCATION_ERROR);
- }
}
--- libical-0.48.orig/src/libical/icalarray.h
+++ libical-0.48/src/libical/icalarray.h
@@ -39,7 +39,7 @@ struct _icalarray {
unsigned int increment_size;
unsigned int num_elements;
unsigned int space_allocated;
- void *data;
+ void **chunks;
};
--
keith.packard at intel.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: not available
URL: <http://lists.infradead.org/pipermail/libical-interest/attachments/20120427/792a253c/attachment.sig>
More information about the libical-interest
mailing list