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 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 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 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 152 cc_uint64 cci_array_count (cci_array_t in_array) 153 { 154 return in_array ? in_array->count : 0; 155 } 156 157 /* ------------------------------------------------------------------------ */ 158 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 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 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 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 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