1/* 2 * Copyright (c) 2003 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24#include <unistd.h> 25#include <stdlib.h> 26#include <stdio.h> 27#include <sys/types.h> 28#include <strings.h> 29 30#include "ptrlist.h" 31 32#ifdef TESTING 33#define DEBUG 34 35static __inline__ void 36ptrlist_print(ptrlist_t * list) 37{ 38 printf("ptrlist count %d, size %d\n", list->count, list->size); 39 if (list->count > 0) { 40 int i; 41 for (i = 0; i < list->count; i++) 42 printf("%d. %p\n", i, list->array[i]); 43 } 44 return; 45} 46 47#endif /* TESTING */ 48 49void 50ptrlist_init(ptrlist_t * list) 51{ 52 bzero(list, sizeof(*list)); 53 return; 54} 55 56void 57ptrlist_init_size(ptrlist_t * list, int size) 58{ 59 bzero(list, sizeof(*list)); 60 if (size > 0) { 61 list->size = size; 62 list->array = malloc(sizeof(*list->array) * list->size); 63 if (list->array == NULL) { 64 list->size = 0; 65 } 66 } 67 return; 68} 69 70void 71ptrlist_free(ptrlist_t * list) 72{ 73 if (list->array) 74 free(list->array); 75 ptrlist_init(list); 76 return; 77} 78 79int 80ptrlist_index(ptrlist_t * list, void * element) 81{ 82 int i; 83 for (i = 0; i < ptrlist_count(list); i++) { 84 if (ptrlist_element(list, i) == element) 85 return (i); 86 } 87 return (-1); 88} 89 90int 91ptrlist_count(ptrlist_t * list) 92{ 93 if (list == NULL || list->array == NULL) 94 return (0); 95 96 return (list->count); 97} 98 99void * 100ptrlist_element(ptrlist_t * list, int i) 101{ 102 if (list->array == NULL) 103 return (NULL); 104 if (i < list->count) 105 return (list->array[i]); 106 return (NULL); 107} 108 109boolean_t 110ptrlist_remove(ptrlist_t * list, int i, void * * ret) 111{ 112 int nmove; 113 114 if (list->array == NULL || i >= list->count || i < 0) 115 return (FALSE); 116 if (ret) 117 *ret = list->array[i]; 118 nmove = (list->count - 1) - i; 119 if (nmove > 0) { 120 bcopy(list->array + (i + 1), 121 list->array + i, 122 nmove * sizeof(*list->array)); 123 } 124 list->count--; 125 return (TRUE); 126} 127 128static boolean_t 129ptrlist_grow(ptrlist_t * list) 130{ 131 if (list->array == NULL) { 132 if (list->size == 0) 133 list->size = PTRLIST_NUMBER; 134 list->count = 0; 135 list->array = malloc(sizeof(*list->array) * list->size); 136 } 137 else if (list->size == list->count) { 138#ifdef DEBUG 139 printf("doubling %d to %d\n", list->size, list->size * 2); 140#endif /* DEBUG */ 141 list->size *= 2; 142 list->array = realloc(list->array, 143 sizeof(*list->array) * list->size); 144 } 145 if (list->array == NULL) 146 return (FALSE); 147 return (TRUE); 148} 149 150boolean_t 151ptrlist_add(ptrlist_t * list, void * element) 152{ 153 if (ptrlist_grow(list) == FALSE) 154 return (FALSE); 155 156 list->array[list->count++] = element; 157 return (TRUE); 158} 159 160boolean_t 161ptrlist_insert(ptrlist_t * list, void * element, int where) 162{ 163 if (where < 0) 164 return (FALSE); 165 166 if (where >= list->count) 167 return (ptrlist_add(list, element)); 168 169 if (ptrlist_grow(list) == FALSE) 170 return (FALSE); 171 172 /* open up a space for 1 element */ 173 bcopy(list->array + where, 174 list->array + where + 1, 175 (list->count - where) * sizeof(*list->array)); 176 list->array[where] = element; 177 list->count++; 178 return (TRUE); 179 180} 181 182boolean_t 183ptrlist_dup(ptrlist_t * dest, ptrlist_t * source) 184{ 185 ptrlist_init(dest); 186 dest->size = dest->count = source->count; 187 if (source->count == 0) 188 return (TRUE); 189 dest->array = malloc(sizeof(*dest->array) * dest->size); 190 if (dest->array == NULL) 191 return (FALSE); 192 bcopy(source->array, dest->array, sizeof(*dest->array) * dest->size); 193 return (TRUE); 194} 195 196/* concatenates extra onto list */ 197boolean_t 198ptrlist_concat(ptrlist_t * list, ptrlist_t * extra) 199{ 200 if (extra->count == 0) 201 return (TRUE); 202 203 if ((extra->count + list->count) > list->size) { 204 list->size = extra->count + list->count; 205 if (list->array == NULL) 206 list->array = malloc(sizeof(*list->array) * list->size); 207 else 208 list->array = realloc(list->array, 209 sizeof(*list->array) * list->size); 210 } 211 if (list->array == NULL) 212 return (FALSE); 213 bcopy(extra->array, list->array + list->count, 214 extra->count * sizeof(*list->array)); 215 list->count += extra->count; 216 return (TRUE); 217} 218 219 220#ifdef TEST_PTRLIST 221int 222main(int argc, char * argv[]) 223{ 224 int i; 225 226 ptrlist_t list1, list2, list3; 227 228 ptrlist_init_size(&list1, 1); 229 ptrlist_init(&list2); 230 ptrlist_init(&list3); 231 232 for (i = 0; i < 10; i++) { 233 ptrlist_add(&list1, (void *)i); 234 } 235 printf("list1:\n"); 236 ptrlist_print(&list1); 237 238 for (i = 10; i < 20; i++) { 239 ptrlist_add(&list2, (void *) i); 240 } 241 printf("\nlist2\n"); 242 ptrlist_print(&list2); 243 244 ptrlist_dup(&list1, &list3); 245 printf("\nlist3\n"); 246 ptrlist_print(&list3); 247 248 ptrlist_concat(&list3, &list2); 249 printf("\nlist3\n"); 250 ptrlist_print(&list3); 251 252 { 253 void * val; 254 255 if (ptrlist_remove(&list3, 7, &val)) { 256 printf("Element at index 7 has value %p\n", val); 257 } 258 printf("\nlist3\n"); 259 ptrlist_print(&list3); 260 if (ptrlist_remove(&list3, 0, &val)) { 261 printf("Element at index 0 has value %p\n", val); 262 } 263 printf("\nlist3\n"); 264 ptrlist_print(&list3); 265 if (ptrlist_remove(&list3, ptrlist_count(&list3) - 1, &val)) { 266 printf("Element at index %d has value %p\n", 267 ptrlist_count(&list3), val); 268 } 269 printf("\nlist3\n"); 270 ptrlist_print(&list3); 271 272 } 273 274 for (i = -20; i < -10; i++) { 275 ptrlist_insert(&list2, (void *)i, 0); 276 } 277 printf("\nlist2\n"); 278 ptrlist_print(&list2); 279 280 ptrlist_free(&list1); 281 ptrlist_free(&list2); 282 ptrlist_free(&list3); 283 exit(0); 284 return 0; 285} 286#endif /* TEST_PTRLIST */ 287