listhash/list.c.in

   1 /* @configure_input@ */
   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 **  @LISTHASH_PREFIX@_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 <@LISTHASH_PREFIX@_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 ** @LISTHASH_PREFIX@_listptr_reset() - reset a list pointer
  32 */
  33 void
  34 @LISTHASH_PREFIX@_listptr_reset(@LISTHASH_PREFIX@_listptr_t *lp)
  35 {
  36         *lp = NULL;
  37 }
  38
  39
  40 /*
  41 ** @LISTHASH_PREFIX@_listptr_data() - retrieve the data pointed to by lp
  42 */
  43 void *
  44 @LISTHASH_PREFIX@_listptr_data(@LISTHASH_PREFIX@_listptr_t *lp)
  45 {
  46         return (*lp)->data;
  47 }
  48
  49
  50 /*
  51 ** @LISTHASH_PREFIX@_list_new() - create a new, empty list
  52 */
  53 @LISTHASH_PREFIX@_list_t *
  54 @LISTHASH_PREFIX@_list_new(int flags, @LISTHASH_PREFIX@_cmpfunc_t cmpfunc)
  55 {
  56         @LISTHASH_PREFIX@_list_t *newlist;
  57
  58 #ifdef DS_DEBUG
  59         printf("in @LISTHASH_PREFIX@_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 = (@LISTHASH_PREFIX@_list_t *)calloc(1, sizeof(@LISTHASH_PREFIX@_list_t));
  71         if (cmpfunc != NULL)
  72                 newlist->cmpfunc = cmpfunc;
  73         else
  74                 newlist->cmpfunc = (@LISTHASH_PREFIX@_cmpfunc_t)strcmp;
  75         newlist->flags = flags;
  76
  77         return newlist;
  78 }
  79
  80
  81 /*
  82 ** @LISTHASH_PREFIX@_list_iterate() - call a function for every element
  83 **                                    in a list
  84 */
  85 int
  86 @LISTHASH_PREFIX@_list_iterate(@LISTHASH_PREFIX@_list_t *l,
  87                                @LISTHASH_PREFIX@_iterate_func_t plugin,
  88                                void *state)
  89 {
  90         @LISTHASH_PREFIX@_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 ** @LISTHASH_PREFIX@_list_empty() - empty the list
 107 */
 108 void
 109 @LISTHASH_PREFIX@_list_empty(@LISTHASH_PREFIX@_list_t *l, @LISTHASH_PREFIX@_freefunc_t freefunc)
 110 {
 111         @LISTHASH_PREFIX@_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 ** @LISTHASH_PREFIX@_list_free() - remove and free() the whole list
 127 */
 128 void
 129 @LISTHASH_PREFIX@_list_free(@LISTHASH_PREFIX@_list_t *l, @LISTHASH_PREFIX@_freefunc_t freefunc)
 130 {
 131         @LISTHASH_PREFIX@_list_empty(l, freefunc);
 132         free(l);
 133 }
 134
 135
 136 /*
 137 ** @LISTHASH_PREFIX@_list_nents() - return number of elements in the list
 138 */
 139 unsigned int
 140 @LISTHASH_PREFIX@_list_nents(@LISTHASH_PREFIX@_list_t *l)
 141 {
 142         return l->nents;
 143 }
 144
 145
 146 /*
 147 ** @LISTHASH_PREFIX@_list_add() - adds an element to the list
 148 ** returns:
 149 **      0                       success
 150 **      -1 (and sets errno)     failure
 151 */
 152 int
 153 @LISTHASH_PREFIX@_list_add(@LISTHASH_PREFIX@_list_t *l, void *data)
 154 {
 155         @LISTHASH_PREFIX@_listptr_t n, m;
 156
 157 #ifdef DS_DEBUG
 158         printf("==> @LISTHASH_PREFIX@_list_add(\"%s\")\n", (char *)data);
 159 #endif
 160
 161         n = (@LISTHASH_PREFIX@_listptr_t)malloc(sizeof(struct @LISTHASH_PREFIX@_node));
 162         if (n == NULL)
 163                 return -1;
 164         n->data = data;
 165         l->nents++;
 166
 167 #ifdef DS_DEBUG
 168         printf("    @LISTHASH_PREFIX@_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("<== @LISTHASH_PREFIX@_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("    @LISTHASH_PREFIX@_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("<== @LISTHASH_PREFIX@_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("<== @LISTHASH_PREFIX@_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("    @LISTHASH_PREFIX@_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("<== @LISTHASH_PREFIX@_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("<== @LISTHASH_PREFIX@_list_add(): added middle,"
 244                                " returning 0\n");
 245 #endif
 246                         return 0;
 247                 }
 248
 249 #ifdef DS_DEBUG
 250         printf("    @LISTHASH_PREFIX@_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("<== @LISTHASH_PREFIX@_list_add(): added end, returning 0\n");
 261 #endif
 262         return 0;
 263 }
 264
 265
 266 /*
 267 ** @LISTHASH_PREFIX@_list_del() - remove the element pointed to by n
 268 **                                from the list l
 269 */
 270 void
 271 @LISTHASH_PREFIX@_list_del(@LISTHASH_PREFIX@_list_t *l, @LISTHASH_PREFIX@_listptr_t *n)
 272 {
 273         @LISTHASH_PREFIX@_listptr_t m;
 274
 275 #ifdef DS_DEBUG
 276         printf("==> @LISTHASH_PREFIX@_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 ** @LISTHASH_PREFIX@_list_next() - get the next element in the list
 299 ** returns:
 300 **      1                       success
 301 **      0                       end of list
 302 */
 303 int
 304 @LISTHASH_PREFIX@_list_next(@LISTHASH_PREFIX@_list_t *l,
 305                             @LISTHASH_PREFIX@_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 ** @LISTHASH_PREFIX@_list_prev() - get the previous element in the list
 318 ** returns:
 319 **      1                       success
 320 **      0                       end of list
 321 */
 322 int
 323 @LISTHASH_PREFIX@_list_prev(@LISTHASH_PREFIX@_list_t *l,
 324                             @LISTHASH_PREFIX@_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 ** @LISTHASH_PREFIX@_str_match() - string matching function
 337 ** returns:
 338 **      1                       match
 339 **      0                       no match
 340 */
 341 int
 342 @LISTHASH_PREFIX@_str_match(char *check, char *data)
 343 {
 344         return !strcmp(check, data);
 345 }
 346
 347
 348 /*
 349 ** @LISTHASH_PREFIX@_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 @LISTHASH_PREFIX@_list_add_str(@LISTHASH_PREFIX@_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 (@LISTHASH_PREFIX@_list_add(l, strdup(tokp)))
 368                         return -1;
 369         }
 370
 371         return 0;
 372 }
 373
 374
 375 /*
 376 ** @LISTHASH_PREFIX@_list_search() - find an entry in a list
 377 ** returns:
 378 **      1                       match found
 379 **      0                       no match
 380 */
 381 int
 382 @LISTHASH_PREFIX@_list_search(@LISTHASH_PREFIX@_list_t *l,
 383                               @LISTHASH_PREFIX@_listptr_t *n, void *data,
 384                               @LISTHASH_PREFIX@_matchfunc_t matchfunc)
 385 {
 386 #ifdef DS_DEBUG
 387         printf("==> @LISTHASH_PREFIX@_list_search(l=0x%lx, n=0x%lx, \"%s\")\n",
 388                l, n, (char *)data);
 389 #endif
 390
 391         if (matchfunc == NULL)
 392                 matchfunc = (@LISTHASH_PREFIX@_matchfunc_t)@LISTHASH_PREFIX@_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 ** @LISTHASH_PREFIX@_list_dup() - copy an existing list
 417 */
 418 @LISTHASH_PREFIX@_list_t *
 419 @LISTHASH_PREFIX@_list_dup(@LISTHASH_PREFIX@_list_t *l)
 420 {
 421         @LISTHASH_PREFIX@_list_t *newlist;
 422         @LISTHASH_PREFIX@_listptr_t n;
 423
 424         newlist = @LISTHASH_PREFIX@_list_new(l->flags, l->cmpfunc);
 425         for (n = l->first; n != NULL; n = n->next)
 426                 @LISTHASH_PREFIX@_list_add(newlist, n->data);
 427
 428 #ifdef DS_DEBUG
 429         printf("returning from @LISTHASH_PREFIX@_list_dup()\n");
 430 #endif
 431         return newlist;
 432 }
 433
 434
 435 /*
 436 ** @LISTHASH_PREFIX@_list_merge() - merge two lists into a new list
 437 */
 438 @LISTHASH_PREFIX@_list_t *
 439 @LISTHASH_PREFIX@_list_merge(@LISTHASH_PREFIX@_cmpfunc_t cmpfunc, int flags,
 440                              @LISTHASH_PREFIX@_list_t *list1,
 441                              @LISTHASH_PREFIX@_list_t *list2)
 442 {
 443         @LISTHASH_PREFIX@_list_t *newlist;
 444         @LISTHASH_PREFIX@_listptr_t n;
 445
 446         newlist = @LISTHASH_PREFIX@_list_new(flags, cmpfunc);
 447
 448         n = NULL;
 449         while (@LISTHASH_PREFIX@_list_next(list1, &n) != 0)
 450                 @LISTHASH_PREFIX@_list_add(newlist, n->data);
 451         n = NULL;
 452         while (@LISTHASH_PREFIX@_list_next(list2, &n) != 0)
 453                 @LISTHASH_PREFIX@_list_add(newlist, n->data);
 454
 455         return newlist;
 456 }
 457
 458