blob: 2c5febb01047499b6930b7ba318a1bbe529e7306 [file] [log] [blame]
bigbiff bigbiff9c754052013-01-09 09:09:08 -05001/* listhash/libtar_list.c. Generated from list.c.in by configure. */
2
3/*
4** Copyright 1998-2002 University of Illinois Board of Trustees
5** Copyright 1998-2002 Mark D. Roth
6** All rights reserved.
7**
8** libtar_list.c - linked list routines
9**
10** Mark D. Roth <roth@uiuc.edu>
11** Campus Information Technologies and Educational Services
12** University of Illinois at Urbana-Champaign
13*/
14
15#include <config.h>
16#include <compat.h>
17
18#include <libtar_listhash.h>
19
20#include <stdio.h>
21#include <errno.h>
22#include <sys/param.h>
23
24#ifdef STDC_HEADERS
25# include <string.h>
26# include <stdlib.h>
27#endif
28
29
30/*
31** libtar_listptr_reset() - reset a list pointer
32*/
33void
34libtar_listptr_reset(libtar_listptr_t *lp)
35{
36 *lp = NULL;
37}
38
39
40/*
41** libtar_listptr_data() - retrieve the data pointed to by lp
42*/
43void *
44libtar_listptr_data(libtar_listptr_t *lp)
45{
46 return (*lp)->data;
47}
48
49
50/*
51** libtar_list_new() - create a new, empty list
52*/
53libtar_list_t *
54libtar_list_new(int flags, libtar_cmpfunc_t cmpfunc)
55{
56 libtar_list_t *newlist;
57
58#ifdef DS_DEBUG
59 printf("in libtar_list_new(%d, 0x%lx)\n", flags, cmpfunc);
60#endif
61
62 if (flags != LIST_USERFUNC
63 && flags != LIST_STACK
64 && flags != LIST_QUEUE)
65 {
66 errno = EINVAL;
67 return NULL;
68 }
69
70 newlist = (libtar_list_t *)calloc(1, sizeof(libtar_list_t));
71 if (cmpfunc != NULL)
72 newlist->cmpfunc = cmpfunc;
73 else
74 newlist->cmpfunc = (libtar_cmpfunc_t)strcmp;
75 newlist->flags = flags;
76
77 return newlist;
78}
79
80
81/*
82** libtar_list_iterate() - call a function for every element
83** in a list
84*/
85int
86libtar_list_iterate(libtar_list_t *l,
87 libtar_iterate_func_t plugin,
88 void *state)
89{
90 libtar_listptr_t n;
91
92 if (l == NULL)
93 return -1;
94
95 for (n = l->first; n != NULL; n = n->next)
96 {
97 if ((*plugin)(n->data, state) == -1)
98 return -1;
99 }
100
101 return 0;
102}
103
104
105/*
106** libtar_list_empty() - empty the list
107*/
108void
109libtar_list_empty(libtar_list_t *l, libtar_freefunc_t freefunc)
110{
111 libtar_listptr_t n;
112
113 for (n = l->first; n != NULL; n = l->first)
114 {
115 l->first = n->next;
116 if (freefunc != NULL)
117 (*freefunc)(n->data);
118 free(n);
119 }
120
121 l->nents = 0;
122}
123
124
125/*
126** libtar_list_free() - remove and free() the whole list
127*/
128void
129libtar_list_free(libtar_list_t *l, libtar_freefunc_t freefunc)
130{
131 libtar_list_empty(l, freefunc);
132 free(l);
133}
134
135
136/*
137** libtar_list_nents() - return number of elements in the list
138*/
139unsigned int
140libtar_list_nents(libtar_list_t *l)
141{
142 return l->nents;
143}
144
145
146/*
147** libtar_list_add() - adds an element to the list
148** returns:
149** 0 success
150** -1 (and sets errno) failure
151*/
152int
153libtar_list_add(libtar_list_t *l, void *data)
154{
155 libtar_listptr_t n, m;
156
157#ifdef DS_DEBUG
158 printf("==> libtar_list_add(\"%s\")\n", (char *)data);
159#endif
160
161 n = (libtar_listptr_t)malloc(sizeof(struct libtar_node));
162 if (n == NULL)
163 return -1;
164 n->data = data;
165 l->nents++;
166
167#ifdef DS_DEBUG
168 printf(" libtar_list_add(): allocated data\n");
169#endif
170
171 /* if the list is empty */
172 if (l->first == NULL)
173 {
174 l->last = l->first = n;
175 n->next = n->prev = NULL;
176#ifdef DS_DEBUG
177 printf("<== libtar_list_add(): list was empty; "
178 "added first element and returning 0\n");
179#endif
180 return 0;
181 }
182
183#ifdef DS_DEBUG
184 printf(" libtar_list_add(): list not empty\n");
185#endif
186
187 if (l->flags == LIST_STACK)
188 {
189 n->prev = NULL;
190 n->next = l->first;
191 if (l->first != NULL)
192 l->first->prev = n;
193 l->first = n;
194#ifdef DS_DEBUG
195 printf("<== libtar_list_add(): LIST_STACK set; "
196 "added in front\n");
197#endif
198 return 0;
199 }
200
201 if (l->flags == LIST_QUEUE)
202 {
203 n->prev = l->last;
204 n->next = NULL;
205 if (l->last != NULL)
206 l->last->next = n;
207 l->last = n;
208#ifdef DS_DEBUG
209 printf("<== libtar_list_add(): LIST_QUEUE set; "
210 "added at end\n");
211#endif
212 return 0;
213 }
214
215 for (m = l->first; m != NULL; m = m->next)
216 if ((*(l->cmpfunc))(data, m->data) < 0)
217 {
218 /*
219 ** if we find one that's bigger,
220 ** insert data before it
221 */
222#ifdef DS_DEBUG
223 printf(" libtar_list_add(): gotcha..."
224 "inserting data\n");
225#endif
226 if (m == l->first)
227 {
228 l->first = n;
229 n->prev = NULL;
230 m->prev = n;
231 n->next = m;
232#ifdef DS_DEBUG
233 printf("<== libtar_list_add(): "
234 "added first, returning 0\n");
235#endif
236 return 0;
237 }
238 m->prev->next = n;
239 n->prev = m->prev;
240 m->prev = n;
241 n->next = m;
242#ifdef DS_DEBUG
243 printf("<== libtar_list_add(): added middle,"
244 " returning 0\n");
245#endif
246 return 0;
247 }
248
249#ifdef DS_DEBUG
250 printf(" libtar_list_add(): new data larger than current "
251 "list elements\n");
252#endif
253
254 /* if we get here, data is bigger than everything in the list */
255 l->last->next = n;
256 n->prev = l->last;
257 l->last = n;
258 n->next = NULL;
259#ifdef DS_DEBUG
260 printf("<== libtar_list_add(): added end, returning 0\n");
261#endif
262 return 0;
263}
264
265
266/*
267** libtar_list_del() - remove the element pointed to by n
268** from the list l
269*/
270void
271libtar_list_del(libtar_list_t *l, libtar_listptr_t *n)
272{
273 libtar_listptr_t m;
274
275#ifdef DS_DEBUG
276 printf("==> libtar_list_del()\n");
277#endif
278
279 l->nents--;
280
281 m = (*n)->next;
282
283 if ((*n)->prev)
284 (*n)->prev->next = (*n)->next;
285 else
286 l->first = (*n)->next;
287 if ((*n)->next)
288 (*n)->next->prev = (*n)->prev;
289 else
290 l->last = (*n)->prev;
291
292 free(*n);
293 *n = m;
294}
295
296
297/*
298** libtar_list_next() - get the next element in the list
299** returns:
300** 1 success
301** 0 end of list
302*/
303int
304libtar_list_next(libtar_list_t *l,
305 libtar_listptr_t *n)
306{
307 if (*n == NULL)
308 *n = l->first;
309 else
310 *n = (*n)->next;
311
312 return (*n != NULL ? 1 : 0);
313}
314
315
316/*
317** libtar_list_prev() - get the previous element in the list
318** returns:
319** 1 success
320** 0 end of list
321*/
322int
323libtar_list_prev(libtar_list_t *l,
324 libtar_listptr_t *n)
325{
326 if (*n == NULL)
327 *n = l->last;
328 else
329 *n = (*n)->prev;
330
331 return (*n != NULL ? 1 : 0);
332}
333
334
335/*
336** libtar_str_match() - string matching function
337** returns:
338** 1 match
339** 0 no match
340*/
341int
342libtar_str_match(char *check, char *data)
343{
344 return !strcmp(check, data);
345}
346
347
348/*
349** libtar_list_add_str() - splits string str into delim-delimited
350** elements and adds them to list l
351** returns:
352** 0 success
353** -1 (and sets errno) failure
354*/
355int
356libtar_list_add_str(libtar_list_t *l,
357 char *str, char *delim)
358{
359 char tmp[10240];
360 char *tokp, *nextp = tmp;
361
362 strlcpy(tmp, str, sizeof(tmp));
363 while ((tokp = strsep(&nextp, delim)) != NULL)
364 {
365 if (*tokp == '\0')
366 continue;
367 if (libtar_list_add(l, strdup(tokp)))
368 return -1;
369 }
370
371 return 0;
372}
373
374
375/*
376** libtar_list_search() - find an entry in a list
377** returns:
378** 1 match found
379** 0 no match
380*/
381int
382libtar_list_search(libtar_list_t *l,
383 libtar_listptr_t *n, void *data,
384 libtar_matchfunc_t matchfunc)
385{
386#ifdef DS_DEBUG
387 printf("==> libtar_list_search(l=0x%lx, n=0x%lx, \"%s\")\n",
388 l, n, (char *)data);
389#endif
390
391 if (matchfunc == NULL)
392 matchfunc = (libtar_matchfunc_t)libtar_str_match;
393
394 if (*n == NULL)
395 *n = l->first;
396 else
397 *n = (*n)->next;
398
399 for (; *n != NULL; *n = (*n)->next)
400 {
401#ifdef DS_DEBUG
402 printf("checking against \"%s\"\n", (char *)(*n)->data);
403#endif
404 if ((*(matchfunc))(data, (*n)->data) != 0)
405 return 1;
406 }
407
408#ifdef DS_DEBUG
409 printf("no matches found\n");
410#endif
411 return 0;
412}
413
414
415/*
416** libtar_list_dup() - copy an existing list
417*/
418libtar_list_t *
419libtar_list_dup(libtar_list_t *l)
420{
421 libtar_list_t *newlist;
422 libtar_listptr_t n;
423
424 newlist = libtar_list_new(l->flags, l->cmpfunc);
425 for (n = l->first; n != NULL; n = n->next)
426 libtar_list_add(newlist, n->data);
427
428#ifdef DS_DEBUG
429 printf("returning from libtar_list_dup()\n");
430#endif
431 return newlist;
432}
433
434
435/*
436** libtar_list_merge() - merge two lists into a new list
437*/
438libtar_list_t *
439libtar_list_merge(libtar_cmpfunc_t cmpfunc, int flags,
440 libtar_list_t *list1,
441 libtar_list_t *list2)
442{
443 libtar_list_t *newlist;
444 libtar_listptr_t n;
445
446 newlist = libtar_list_new(flags, cmpfunc);
447
448 n = NULL;
449 while (libtar_list_next(list1, &n) != 0)
450 libtar_list_add(newlist, n->data);
451 n = NULL;
452 while (libtar_list_next(list2, &n) != 0)
453 libtar_list_add(newlist, n->data);
454
455 return newlist;
456}
457
458