bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 1 | /* 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 | */ |
| 33 | void |
| 34 | libtar_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 | */ |
| 43 | void * |
| 44 | libtar_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 | */ |
| 53 | libtar_list_t * |
| 54 | libtar_list_new(int flags, libtar_cmpfunc_t cmpfunc) |
| 55 | { |
| 56 | libtar_list_t *newlist; |
| 57 | |
| 58 | #ifdef DS_DEBUG |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 59 | LOG("in libtar_list_new(%d, 0x%lx)\n", flags, cmpfunc); |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 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 | */ |
| 85 | int |
| 86 | libtar_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 | */ |
| 108 | void |
| 109 | libtar_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 | */ |
| 128 | void |
| 129 | libtar_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 | */ |
| 139 | unsigned int |
| 140 | libtar_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 | */ |
| 152 | int |
| 153 | libtar_list_add(libtar_list_t *l, void *data) |
| 154 | { |
| 155 | libtar_listptr_t n, m; |
| 156 | |
| 157 | #ifdef DS_DEBUG |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 158 | LOG("==> libtar_list_add(\"%s\")\n", (char *)data); |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 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 |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 168 | LOG(" libtar_list_add(): allocated data\n"); |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 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 |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 177 | LOG("<== libtar_list_add(): list was empty; " |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 178 | "added first element and returning 0\n"); |
| 179 | #endif |
| 180 | return 0; |
| 181 | } |
| 182 | |
| 183 | #ifdef DS_DEBUG |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 184 | LOG(" libtar_list_add(): list not empty\n"); |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 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 |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 195 | LOG("<== libtar_list_add(): LIST_STACK set; " |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 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 |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 209 | LOG("<== libtar_list_add(): LIST_QUEUE set; " |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 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 |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 223 | LOG(" libtar_list_add(): gotcha..." |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 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 |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 233 | LOG("<== libtar_list_add(): " |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 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 |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 243 | LOG("<== libtar_list_add(): added middle," |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 244 | " returning 0\n"); |
| 245 | #endif |
| 246 | return 0; |
| 247 | } |
| 248 | |
| 249 | #ifdef DS_DEBUG |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 250 | LOG(" libtar_list_add(): new data larger than current " |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 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 |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 260 | LOG("<== libtar_list_add(): added end, returning 0\n"); |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 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 | */ |
| 270 | void |
| 271 | libtar_list_del(libtar_list_t *l, libtar_listptr_t *n) |
| 272 | { |
| 273 | libtar_listptr_t m; |
| 274 | |
| 275 | #ifdef DS_DEBUG |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 276 | LOG("==> libtar_list_del()\n"); |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 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 | */ |
| 303 | int |
| 304 | libtar_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 | */ |
| 322 | int |
| 323 | libtar_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 | */ |
| 341 | int |
| 342 | libtar_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 | */ |
| 355 | int |
| 356 | libtar_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 | */ |
| 381 | int |
| 382 | libtar_list_search(libtar_list_t *l, |
| 383 | libtar_listptr_t *n, void *data, |
| 384 | libtar_matchfunc_t matchfunc) |
| 385 | { |
| 386 | #ifdef DS_DEBUG |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 387 | LOG("==> libtar_list_search(l=0x%lx, n=0x%lx, \"%s\")\n", |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 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 |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 402 | LOG("checking against \"%s\"\n", (char *)(*n)->data); |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 403 | #endif |
| 404 | if ((*(matchfunc))(data, (*n)->data) != 0) |
| 405 | return 1; |
| 406 | } |
| 407 | |
| 408 | #ifdef DS_DEBUG |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 409 | LOG("no matches found\n"); |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 410 | #endif |
| 411 | return 0; |
| 412 | } |
| 413 | |
| 414 | |
| 415 | /* |
| 416 | ** libtar_list_dup() - copy an existing list |
| 417 | */ |
| 418 | libtar_list_t * |
| 419 | libtar_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 |
Mohd Faraz | 1524764 | 2023-01-16 16:16:21 +0100 | [diff] [blame] | 429 | LOG("returning from libtar_list_dup()\n"); |
bigbiff bigbiff | 9c75405 | 2013-01-09 09:09:08 -0500 | [diff] [blame] | 430 | #endif |
| 431 | return newlist; |
| 432 | } |
| 433 | |
| 434 | |
| 435 | /* |
| 436 | ** libtar_list_merge() - merge two lists into a new list |
| 437 | */ |
| 438 | libtar_list_t * |
| 439 | libtar_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 | |