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