1 /*======================================================================
2 FILE: icalarray.c
3 CREATOR: Damon Chaplin 07 March 2001
4
5 (C) COPYRIGHT 2001, Ximian, Inc.
6
7 This library is free software; you can redistribute it and/or modify
8 it under the terms of either:
9
10 The LGPL as published by the Free Software Foundation, version
11 2.1, available at: https://www.gnu.org/licenses/lgpl-2.1.html
12
13 Or:
14
15 The Mozilla Public License Version 2.0. You may obtain a copy of
16 the License at https://www.mozilla.org/MPL/
17 ======================================================================*/
18
19 #ifdef HAVE_CONFIG_H
20 #include <config.h>
21 #endif
22
23 #include "icalarray.h"
24 #include "icalerror.h"
25
26 #include <stdlib.h>
27 #include <string.h>
28
29 static void icalarray_expand(icalarray *array, size_t space_needed);
30
icalarray_new(size_t element_size,size_t increment_size)31 icalarray *icalarray_new(size_t element_size, size_t increment_size)
32 {
33 icalarray *array;
34
35 array = (icalarray *) malloc(sizeof(icalarray));
36 if (!array) {
37 icalerror_set_errno(ICAL_NEWFAILED_ERROR);
38 return NULL;
39 }
40
41 array->element_size = element_size;
42 array->increment_size = increment_size;
43 array->num_elements = 0;
44 array->space_allocated = 0;
45 array->chunks = NULL;
46
47 return array;
48 }
49
icalarray_alloc_chunk(icalarray * array)50 static void *icalarray_alloc_chunk(icalarray *array)
51 {
52 void *chunk = malloc(array->element_size * array->increment_size);
53
54 if (!chunk) {
55 icalerror_set_errno(ICAL_NEWFAILED_ERROR);
56 }
57 return chunk;
58 }
59
icalarray_copy(icalarray * originalarray)60 icalarray *icalarray_copy(icalarray *originalarray)
61 {
62 icalarray *array = icalarray_new(originalarray->element_size, originalarray->increment_size);
63 size_t chunks = originalarray->space_allocated / originalarray->increment_size;
64 size_t chunk;
65
66 if (!array) {
67 return NULL;
68 }
69
70 array->num_elements = originalarray->num_elements;
71 array->space_allocated = originalarray->space_allocated;
72
73 array->chunks = malloc(chunks * sizeof(void *));
74 if (array->chunks) {
75 for (chunk = 0; chunk < chunks; chunk++) {
76 array->chunks[chunk] = icalarray_alloc_chunk(array);
77 if (array->chunks[chunk]) {
78 memcpy(array->chunks[chunk], originalarray->chunks[chunk],
79 array->increment_size * array->element_size);
80 }
81 }
82
83 } else {
84 icalerror_set_errno(ICAL_ALLOCATION_ERROR);
85 }
86
87 return array;
88 }
89
icalarray_free(icalarray * array)90 void icalarray_free(icalarray *array)
91 {
92 if (array->chunks) {
93 size_t chunks = array->space_allocated / array->increment_size;
94 size_t chunk;
95
96 for (chunk = 0; chunk < chunks; chunk++) {
97 free(array->chunks[chunk]);
98 }
99 free(array->chunks);
100 array->chunks = 0;
101 }
102 free(array);
103 }
104
icalarray_append(icalarray * array,const void * element)105 void icalarray_append(icalarray *array, const void *element)
106 {
107 size_t pos;
108
109 if (array->num_elements >= array->space_allocated) {
110 icalarray_expand(array, 1);
111 }
112
113 pos = array->num_elements++;
114 memcpy(icalarray_element_at(array, pos), element, array->element_size);
115 }
116
icalarray_element_at(icalarray * array,size_t position)117 void *icalarray_element_at(icalarray *array, size_t position)
118 {
119 size_t chunk = position / array->increment_size;
120 size_t offset = position % array->increment_size;
121
122 return (char *)(array->chunks[chunk]) + (offset * array->element_size);
123 }
124
icalarray_remove_element_at(icalarray * array,size_t position)125 void icalarray_remove_element_at(icalarray *array, size_t position)
126 {
127 while (position < array->num_elements - 1) {
128 memmove(icalarray_element_at(array, position),
129 icalarray_element_at(array, position + 1), array->element_size);
130 position++;
131 }
132
133 array->num_elements--;
134 }
135
icalarray_sort(icalarray * array,int (* compare)(const void *,const void *))136 void icalarray_sort(icalarray *array, int (*compare) (const void *, const void *))
137 {
138 if (array->num_elements == 0) {
139 return;
140 }
141
142 if (array->num_elements <= array->increment_size) {
143 qsort(array->chunks[0], array->num_elements, array->element_size, compare);
144 } else {
145 size_t pos;
146 void *tmp = malloc(array->num_elements * array->element_size);
147
148 if (!tmp) {
149 return;
150 }
151 for (pos = 0; pos < array->num_elements; pos++) {
152 memcpy((char *)tmp + array->element_size * pos,
153 icalarray_element_at(array, pos), array->element_size);
154 }
155
156 qsort(tmp, array->num_elements, array->element_size, compare);
157
158 for (pos = 0; pos < array->num_elements; pos++) {
159 memcpy(icalarray_element_at(array, pos),
160 (char *)tmp + array->element_size * pos, array->element_size);
161 }
162 free(tmp);
163 }
164 }
165
icalarray_expand(icalarray * array,size_t space_needed)166 static void icalarray_expand(icalarray *array, size_t space_needed)
167 {
168 size_t num_chunks = array->space_allocated / array->increment_size;
169 size_t num_new_chunks;
170 size_t c;
171 void **new_chunks;
172
173 num_new_chunks = (space_needed + array->increment_size - 1) / array->increment_size;
174 if (!num_new_chunks) {
175 num_new_chunks = 1;
176 }
177
178 new_chunks = malloc((num_chunks + num_new_chunks) * sizeof(void *));
179
180 if (new_chunks) {
181 if (array->chunks && num_chunks) {
182 memcpy(new_chunks, array->chunks, num_chunks * sizeof(void *));
183 }
184 for (c = 0; c < num_new_chunks; c++) {
185 new_chunks[c + num_chunks] = icalarray_alloc_chunk(array);
186 }
187 if (array->chunks) {
188 free(array->chunks);
189 }
190 array->chunks = new_chunks;
191 array->space_allocated = array->space_allocated + num_new_chunks * array->increment_size;
192 } else {
193 icalerror_set_errno(ICAL_ALLOCATION_ERROR);
194 }
195 }
196