1 /* ccapi/common/cci_array_internal.c */
2 /*
3 * Copyright 2006, 2007 Massachusetts Institute of Technology.
4 * All Rights Reserved.
5 *
6 * Export of this software from the United States of America may
7 * require a specific license from the United States Government.
8 * It is the responsibility of any person or organization contemplating
9 * export to obtain such a license before exporting.
10 *
11 * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
12 * distribute this software and its documentation for any purpose and
13 * without fee is hereby granted, provided that the above copyright
14 * notice appear in all copies and that both that copyright notice and
15 * this permission notice appear in supporting documentation, and that
16 * the name of M.I.T. not be used in advertising or publicity pertaining
17 * to distribution of the software without specific, written prior
18 * permission. Furthermore if you modify this software you must label
19 * your software as modified software and not distribute it in such a
20 * fashion that it might be confused with the original M.I.T. software.
21 * M.I.T. makes no representations about the suitability of
22 * this software for any purpose. It is provided "as is" without express
23 * or implied warranty.
24 */
25
26 #include "cci_common.h"
27 #include "cci_array_internal.h"
28
29 #ifdef WIN32
30 #include "k5-platform.h"
31 #endif
32
33 /* ------------------------------------------------------------------------ */
34
35 struct cci_array_d {
36 cci_array_object_t *objects;
37 cc_uint64 count;
38 cc_uint64 max_count;
39
40 cci_array_object_release_t object_release;
41 };
42
43 struct cci_array_d cci_array_initializer = { NULL, 0, 0, NULL };
44
45 #define CCI_ARRAY_COUNT_INCREMENT 16
46
47 /* ------------------------------------------------------------------------ */
48
cci_array_resize(cci_array_t io_array,cc_uint64 in_new_count)49 static cc_int32 cci_array_resize (cci_array_t io_array,
50 cc_uint64 in_new_count)
51 {
52 cc_int32 err = ccNoError;
53 cc_uint64 new_max_count = 0;
54
55 if (!io_array) { err = cci_check_error (ccErrBadParam); }
56
57 if (!err) {
58 cc_uint64 old_max_count = io_array->max_count;
59 new_max_count = io_array->max_count;
60
61 if (in_new_count > old_max_count) {
62 /* Expand the array */
63 while (in_new_count > new_max_count) {
64 new_max_count += CCI_ARRAY_COUNT_INCREMENT;
65 }
66
67 } else if ((in_new_count + CCI_ARRAY_COUNT_INCREMENT) < old_max_count) {
68 /* Shrink the array, but never drop below CC_ARRAY_COUNT_INCREMENT */
69 while ((in_new_count + CCI_ARRAY_COUNT_INCREMENT) < new_max_count &&
70 (new_max_count > CCI_ARRAY_COUNT_INCREMENT)) {
71 new_max_count -= CCI_ARRAY_COUNT_INCREMENT;
72 }
73 }
74 }
75
76 if (!err && io_array->max_count != new_max_count) {
77 cci_array_object_t *objects = io_array->objects;
78
79 if (!objects) {
80 objects = malloc (new_max_count * sizeof (*objects));
81 } else {
82 objects = realloc (objects, new_max_count * sizeof (*objects));
83 }
84 if (!objects) { err = cci_check_error (ccErrNoMem); }
85
86 if (!err) {
87 io_array->objects = objects;
88 io_array->max_count = new_max_count;
89 }
90 }
91
92 return cci_check_error (err);
93 }
94
95 #ifdef TARGET_OS_MAC
96 #pragma mark -
97 #endif
98
99 /* ------------------------------------------------------------------------ */
100
cci_array_new(cci_array_t * out_array,cci_array_object_release_t in_array_object_release)101 cc_int32 cci_array_new (cci_array_t *out_array,
102 cci_array_object_release_t in_array_object_release)
103 {
104 cc_int32 err = ccNoError;
105 cci_array_t array = NULL;
106
107 if (!out_array) { err = cci_check_error (ccErrBadParam); }
108
109 if (!err) {
110 array = malloc (sizeof (*array));
111 if (array) {
112 *array = cci_array_initializer;
113 array->object_release = in_array_object_release;
114 } else {
115 err = cci_check_error (ccErrNoMem);
116 }
117 }
118
119 if (!err) {
120 *out_array = array;
121 array = NULL;
122 }
123
124 cci_array_release (array);
125
126 return cci_check_error (err);
127 }
128
129 /* ------------------------------------------------------------------------ */
130
cci_array_release(cci_array_t io_array)131 cc_int32 cci_array_release (cci_array_t io_array)
132 {
133 cc_int32 err = ccNoError;
134
135 if (!err && io_array) {
136 cc_uint64 i;
137
138 if (io_array->object_release) {
139 for (i = 0; i < io_array->count; i++) {
140 io_array->object_release (io_array->objects[i]);
141 }
142 }
143 free (io_array->objects);
144 free (io_array);
145 }
146
147 return err;
148 }
149
150 /* ------------------------------------------------------------------------ */
151
cci_array_count(cci_array_t in_array)152 cc_uint64 cci_array_count (cci_array_t in_array)
153 {
154 return in_array ? in_array->count : 0;
155 }
156
157 /* ------------------------------------------------------------------------ */
158
cci_array_object_at_index(cci_array_t io_array,cc_uint64 in_position)159 cci_array_object_t cci_array_object_at_index (cci_array_t io_array,
160 cc_uint64 in_position)
161 {
162 if (io_array && in_position < io_array->count) {
163 return io_array->objects[in_position];
164 } else {
165 if (!io_array) {
166 cci_debug_printf ("%s() got NULL array", __FUNCTION__);
167 } else {
168 cci_debug_printf ("%s() got bad index %lld (count = %lld)", __FUNCTION__,
169 in_position, io_array->count);
170 }
171 return NULL;
172 }
173 }
174
175 #ifdef TARGET_OS_MAC
176 #pragma mark -
177 #endif
178
179 /* ------------------------------------------------------------------------ */
180
cci_array_insert(cci_array_t io_array,cci_array_object_t in_object,cc_uint64 in_position)181 cc_int32 cci_array_insert (cci_array_t io_array,
182 cci_array_object_t in_object,
183 cc_uint64 in_position)
184 {
185 cc_int32 err = ccNoError;
186
187 if (!io_array ) { err = cci_check_error (ccErrBadParam); }
188 if (!in_object) { err = cci_check_error (ccErrBadParam); }
189
190 if (!err) {
191 /* Don't try to insert past the end and don't overflow the array */
192 if (in_position > io_array->count || io_array->count == UINT64_MAX) {
193 err = cci_check_error (ccErrBadParam);
194 }
195 }
196
197 if (!err) {
198 err = cci_array_resize (io_array, io_array->count + 1);
199 }
200
201 if (!err) {
202 cc_uint64 move_count = io_array->count - in_position;
203
204 if (move_count > 0) {
205 memmove (&io_array->objects[in_position + 1], &io_array->objects[in_position],
206 move_count * sizeof (*io_array->objects));
207 }
208
209 io_array->objects[in_position] = in_object;
210 io_array->count++;
211 }
212
213 return cci_check_error (err);
214 }
215
216 /* ------------------------------------------------------------------------ */
217
cci_array_remove(cci_array_t io_array,cc_uint64 in_position)218 cc_int32 cci_array_remove (cci_array_t io_array,
219 cc_uint64 in_position)
220 {
221 cc_int32 err = ccNoError;
222
223 if (!io_array) { err = cci_check_error (ccErrBadParam); }
224
225 if (!err && in_position >= io_array->count) {
226 err = cci_check_error (ccErrBadParam);
227 }
228
229 if (!err) {
230 cc_uint64 move_count = io_array->count - in_position - 1;
231 cci_array_object_t object = io_array->objects[in_position];
232
233 if (move_count > 0) {
234 memmove (&io_array->objects[in_position], &io_array->objects[in_position + 1],
235 move_count * sizeof (*io_array->objects));
236 }
237 io_array->count--;
238
239 if (io_array->object_release) { io_array->object_release (object); }
240
241 cci_array_resize (io_array, io_array->count);
242 }
243
244 return cci_check_error (err);
245 }
246
247 /* ------------------------------------------------------------------------ */
248
cci_array_move(cci_array_t io_array,cc_uint64 in_position,cc_uint64 in_new_position,cc_uint64 * out_real_new_position)249 cc_int32 cci_array_move (cci_array_t io_array,
250 cc_uint64 in_position,
251 cc_uint64 in_new_position,
252 cc_uint64 *out_real_new_position)
253 {
254 cc_int32 err = ccNoError;
255
256 if (!io_array ) { err = cci_check_error (ccErrBadParam); }
257 if (!out_real_new_position) { err = cci_check_error (ccErrBadParam); }
258
259 if (!err && in_position >= io_array->count) {
260 err = cci_check_error (ccErrBadParam);
261 }
262
263 if (!err && in_new_position > io_array->count) {
264 err = cci_check_error (ccErrBadParam);
265 }
266 if (!err) {
267 cc_uint64 move_from = 0;
268 cc_uint64 move_to = 0;
269 cc_uint64 move_count = 0;
270 cc_uint64 real_new_position = 0;
271
272 if (in_position < in_new_position) {
273 /* shift right, making an empty space so the
274 * actual new position is one less in_new_position */
275 move_from = in_position + 1;
276 move_to = in_position;
277 move_count = in_new_position - in_position - 1;
278 real_new_position = in_new_position - 1;
279
280 } else if (in_position > in_new_position) {
281 /* shift left */
282 move_from = in_new_position;
283 move_to = in_new_position + 1;
284 move_count = in_position - in_new_position;
285 real_new_position = in_new_position;
286
287 } else {
288 real_new_position = in_new_position;
289 }
290
291 if (move_count > 0) {
292 cci_array_object_t object = io_array->objects[in_position];
293
294 memmove (&io_array->objects[move_to], &io_array->objects[move_from],
295 move_count * sizeof (*io_array->objects));
296 io_array->objects[real_new_position] = object;
297 }
298
299 *out_real_new_position = real_new_position;
300 }
301
302 return cci_check_error (err);
303 }
304
305 /* ------------------------------------------------------------------------ */
306
cci_array_push_front(cci_array_t io_array,cc_uint64 in_position)307 cc_int32 cci_array_push_front (cci_array_t io_array,
308 cc_uint64 in_position)
309 {
310 cc_uint64 real_new_position = 0;
311 return cci_array_move (io_array, in_position, 0, &real_new_position);
312 }
313