[libical] Allocate ical arrays in chunks to keep pointers stable (bug 3514871)

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 454-5900

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 <ke...@ke...>
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;
 };
 
-- 
kei...@in...
