list.c

   1 const char list_rcs[] = "$Id: list.c,v 1.9 2001/09/16 13:20:29 jongfoster Exp $";
   2 /*********************************************************************
   3  *
   4  * File        :  $Source: /cvsroot/ijbswa/current/list.c,v $
   5  *
   6  * Purpose     :  Declares functions to handle lists.
   7  *                Functions declared include:
   8  *                   `destroy_list', `enlist' and `list_to_text'
   9  *
  10  * Copyright   :  Written by and Copyright (C) 2001 the SourceForge
  11  *                IJBSWA team.  http://ijbswa.sourceforge.net
  12  *
  13  *                Based on the Internet Junkbuster originally written
  14  *                by and Copyright (C) 1997 Anonymous Coders and
  15  *                Junkbusters Corporation.  http://www.junkbusters.com
  16  *
  17  *                This program is free software; you can redistribute it
  18  *                and/or modify it under the terms of the GNU General
  19  *                Public License as published by the Free Software
  20  *                Foundation; either version 2 of the License, or (at
  21  *                your option) any later version.
  22  *
  23  *                This program is distributed in the hope that it will
  24  *                be useful, but WITHOUT ANY WARRANTY; without even the
  25  *                implied warranty of MERCHANTABILITY or FITNESS FOR A
  26  *                PARTICULAR PURPOSE.  See the GNU General Public
  27  *                License for more details.
  28  *
  29  *                The GNU General Public License should be included with
  30  *                this file.  If not, you can view it at
  31  *                http://www.gnu.org/copyleft/gpl.html
  32  *                or write to the Free Software Foundation, Inc., 59
  33  *                Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  34  *
  35  * Revisions   :
  36  *    $Log: list.c,v $
  37  *    Revision 1.9  2001/09/16 13:20:29  jongfoster
  38  *    Rewrite of list library.  Now has seperate header and list_entry
  39  *    structures.  Also added a large sprinking of assert()s to the list
  40  *    code.
  41  *
  42  *    Revision 1.8  2001/08/07 14:00:20  oes
  43  *    Fixed comment
  44  *
  45  *    Revision 1.7  2001/08/05 16:06:20  jongfoster
  46  *    Modifiying "struct map" so that there are now separate header and
  47  *    "map_entry" structures.  This means that functions which modify a
  48  *    map no longer need to return a pointer to the modified map.
  49  *    Also, it no longer reverses the order of the entries (which may be
  50  *    important with some advanced template substitutions).
  51  *
  52  *    Revision 1.6  2001/07/31 14:44:51  oes
  53  *    list_to_text() now appends empty line at end
  54  *
  55  *    Revision 1.5  2001/06/29 21:45:41  oes
  56  *    Indentation, CRLF->LF, Tab-> Space
  57  *
  58  *    Revision 1.4  2001/06/29 13:30:22  oes
  59  *    - Added Convenience function enlist_unique_header(),
  60  *      which takes the Header name and value as separate
  61  *      arguments and thus saves the pain of sprintf()ing
  62  *      and determining the Header name length to enlist_unique
  63  *    - Improved comments
  64  *    - Removed logentry from cancelled commit
  65  *
  66  *    Revision 1.3  2001/06/03 19:12:24  oes
  67  *    functions for new struct map, extended enlist_unique
  68  *
  69  *    Revision 1.2  2001/06/01 18:49:17  jongfoster
  70  *    Replaced "list_share" with "list" - the tiny memory gain was not
  71  *    worth the extra complexity.
  72  *
  73  *    Revision 1.1  2001/05/31 21:11:53  jongfoster
  74  *    - Moved linked list support to new "list.c" file.
  75  *      Structure definitions are still in project.h,
  76  *      function prototypes are now in "list.h".
  77  *    - Added support for "struct list_share", which is identical
  78  *      to "struct list" except it saves memory by not duplicating
  79  *      the strings.  Obviously, this only works if there is some
  80  *      other way of managing the memory used by the strings.
  81  *      (These list_share lists are used for lists which last
  82  *      for only 1 request, and where all the list entries are
  83  *      just coming directly from entries in the actionsfile.)
  84  *      Note that you still need to destroy list_share lists
  85  *      properly to free the nodes - it's only the strings
  86  *      which are shared.
  87  *
  88  *
  89  *********************************************************************/
  90 \f
  91
  92 #include "config.h"
  93
  94 #ifndef _WIN32
  95 /* FIXME: The following headers are not needed for Win32.  Are they
  96  * needed on other platforms?
  97  */
  98 #include <stdio.h>
  99 #include <sys/types.h>
 100 #include <stdlib.h>
 101 #include <ctype.h>
 102 #endif
 103 #include <string.h>
 104
 105 #ifndef _WIN32
 106 #include <unistd.h>
 107 #endif
 108
 109 #include <assert.h>
 110
 111 #include "project.h"
 112 #include "list.h"
 113 #include "miscutil.h"
 114
 115 const char list_h_rcs[] = LIST_H_VERSION;
 116
 117
 118 static int list_is_valid (const struct list *the_list);
 119
 120
 121 /*********************************************************************
 122  *
 123  * Function    :  list_init
 124  *
 125  * Description :  Create a new, empty list in user-allocated memory.
 126  *                Caller should allocate a "struct list" variable,
 127  *                then pass it to this function.
 128  *                (Implementation note:  Rather than calling this
 129  *                function, you can also just memset the memory to
 130  *                zero, e.g. if you have a larger structure you
 131  *                want to initialize quickly.  However, that isn't
 132  *                really good design.)
 133  *
 134  * Parameters  :
 135  *          1  :  the_list = pointer to list
 136  *
 137  * Returns     :  N/A
 138  *
 139  *********************************************************************/
 140 void init_list(struct list *the_list)
 141 {
 142    memset(the_list, '\0', sizeof(*the_list));
 143 }
 144
 145
 146 /*********************************************************************
 147  *
 148  * Function    :  destroy_list
 149  *
 150  * Description :  Destroy a string list (opposite of list_init).
 151  *                On return, the memory used by the list entries has
 152  *                been freed, but not the memory used by the_list
 153  *                itself.  You should not re-use the_list without
 154  *                calling list_init().
 155  *
 156  *                (Implementation note:  You *can* reuse the_list
 157  *                without calling list_init(), but please don't.
 158  *                If you want to remove all entries from a list
 159  *                and still have a usable list, then use
 160  *                list_remove_all().)
 161  *
 162  * Parameters  :
 163  *          1  :  the_list = pointer to list
 164  *
 165  * Returns     :  N/A
 166  *
 167  *********************************************************************/
 168 void destroy_list (struct list *the_list)
 169 {
 170    struct list_entry *cur_entry, *next_entry;
 171
 172    assert(the_list);
 173
 174    for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
 175    {
 176       next_entry = cur_entry->next;
 177       freez((char *)cur_entry->str);
 178       free(cur_entry);
 179    }
 180
 181    the_list->first = NULL;
 182    the_list->last = NULL;
 183 }
 184
 185
 186 /*********************************************************************
 187  *
 188  * Function    :  list_is_valid
 189  *
 190  * Description :  Check that a string list is valid.  The intended
 191  *                usage is "assert(list_is_valid(the_list))".
 192  *                Currently this checks that "the_list->last"
 193  *                is correct, and that the list dosn't contain
 194  *                circular references.  It is likely to crash if
 195  *                it's passed complete garbage.
 196  *
 197  * Parameters  :
 198  *          1  :  the_list = pointer to list.  Must be non-null.
 199  *
 200  * Returns     :  1 if list is valid, 0 otherwise.
 201  *
 202  *********************************************************************/
 203 static int list_is_valid (const struct list *the_list)
 204 {
 205    /*
 206     * If you don't want this check, just change the line below
 207     * from "#if 1" to "#if 0".
 208     */
 209 #if 1
 210    const struct list_entry *cur_entry;
 211    const struct list_entry *last_entry = NULL;
 212    int length = 0;
 213
 214    assert(the_list);
 215
 216    for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
 217    {
 218       last_entry = cur_entry;
 219
 220       if (cur_entry->str)
 221       {
 222          /*
 223           * Just check that this string can be accessed - i.e. it's a valid
 224           * pointer.
 225           */
 226          strlen(cur_entry->str);
 227       }
 228
 229       /*
 230        * Check for looping back to first
 231        */
 232       if ((length != 0) && (cur_entry == the_list->first))
 233       {
 234          return 0;
 235       }
 236
 237       /*
 238        * Arbitrarily limit length to prevent infinite loops.
 239        */
 240       if (++length > 1000)
 241       {
 242          return 0;
 243       }
 244
 245       /*
 246        * Check this isn't marked as the last entry, unless of course it's
 247        * *really* the last entry.
 248        */
 249       if ((the_list->last == cur_entry) && (cur_entry->next != NULL))
 250       {
 251          /* This is the last entry, but there's data after it !!?? */
 252          return 0;
 253       }
 254    }
 255
 256    return (the_list->last == last_entry);
 257 #else
 258    return 1;
 259 #endif
 260 }
 261
 262 /*********************************************************************
 263  *
 264  * Function    :  enlist
 265  *
 266  * Description :  Append a string into a specified string list.
 267  *
 268  * Parameters  :
 269  *          1  :  the_list = pointer to list
 270  *          2  :  str = string to add to the list (maybe NULL)
 271  *
 272  * Returns     :  0 on success, nonzero on out-of-memory error.  On
 273  *                error, the_list will be unchanged.
 274  *
 275  *********************************************************************/
 276 int enlist(struct list *the_list, const char *str)
 277 {
 278    struct list_entry *cur;
 279
 280    assert(the_list);
 281    assert(list_is_valid(the_list));
 282
 283    if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
 284    {
 285       return 1;
 286    }
 287
 288    if (str)
 289    {
 290       if (NULL == (cur->str = strdup(str)))
 291       {
 292          free(cur);
 293          return 1;
 294       }
 295    }
 296    /* else { cur->str = NULL; }  - implied by zalloc */
 297
 298    /* cur->next = NULL;  - implied by zalloc */
 299
 300    if (the_list->last)
 301    {
 302       the_list->last->next = cur;
 303       the_list->last = cur;
 304    }
 305    else
 306    {
 307       the_list->first = cur;
 308       the_list->last = cur;
 309    }
 310
 311    assert(list_is_valid(the_list));
 312    return 0;
 313 }
 314
 315
 316 /*********************************************************************
 317  *
 318  * Function    :  enlist_first
 319  *
 320  * Description :  Append a string as first element into a specified
 321  *                string list.
 322  *
 323  * Parameters  :
 324  *          1  :  the_list = pointer to list
 325  *          2  :  str = string to add to the list (maybe NULL)
 326  *
 327  * Returns     :  0 on success, nonzero on out-of-memory error.  On
 328  *                error, the_list will be unchanged.
 329  *
 330  *********************************************************************/
 331 int enlist_first(struct list *the_list, const char *str)
 332 {
 333    struct list_entry *cur;
 334
 335    assert(the_list);
 336    assert(list_is_valid(the_list));
 337
 338    if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
 339    {
 340       return 1;
 341    }
 342
 343    if (str)
 344    {
 345       if (NULL == (cur->str = strdup(str)))
 346       {
 347          free(cur);
 348          return 1;
 349       }
 350    }
 351    /* else { cur->str = NULL; }  - implied by zalloc */
 352
 353    cur->next = the_list->first;
 354
 355    the_list->first = cur;
 356    if (the_list->last == NULL)
 357    {
 358       the_list->last = cur;
 359    }
 360
 361    assert(list_is_valid(the_list));
 362    return 0;
 363 }
 364
 365
 366 /*********************************************************************
 367  *
 368  * Function    :  enlist_unique
 369  *
 370  * Description :  Append a string into a specified string list,
 371  *                if & only if it's not there already.
 372  *                If the num_significant_chars argument is nonzero,
 373  *                only compare up to the nth character.
 374  *
 375  * Parameters  :
 376  *          1  :  the_list = pointer to list
 377  *          2  :  str = string to add to the list
 378  *          3  :  num_significant_chars = number of chars to use
 379  *                for uniqueness test, or 0 to require an exact match.
 380  *
 381  * Returns     :  0 on success, nonzero on out-of-memory error.  On
 382  *                error, the_list will be unchanged.  "Success"
 383  *                does not indicate whether or not the item was
 384  *                already in the list.
 385  *
 386  *********************************************************************/
 387 int enlist_unique(struct list *the_list, const char *str,
 388                   int num_significant_chars)
 389 {
 390    struct list_entry *cur_entry;
 391
 392    assert(the_list);
 393    assert(list_is_valid(the_list));
 394    assert(str);
 395    assert(num_significant_chars >= 0);
 396    assert((size_t)num_significant_chars <= strlen(str));
 397
 398    if (num_significant_chars > 0)
 399    {
 400       for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
 401       {
 402          if ( (cur_entry->str != NULL)
 403            && (0 == strncmp(str, cur_entry->str, num_significant_chars)))
 404          {
 405             /* Already there */
 406             return 0;
 407          }
 408       }
 409    }
 410    else
 411    {
 412       /* Test whole string */
 413       for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
 414       {
 415          if ( (cur_entry->str != NULL) && (0 == strcmp(str, cur_entry->str)))
 416          {
 417             /* Already there */
 418             return 0;
 419          }
 420       }
 421    }
 422
 423    return enlist(the_list, str);
 424 }
 425
 426
 427 /*********************************************************************
 428  *
 429  * Function    :  enlist_unique_header
 430  *
 431  * Description :  Make a HTTP header from the two strings name and value,
 432  *                and append the result into a specified string list,
 433  *                if & only if there isn't already a header with that name.
 434  *
 435  * Parameters  :
 436  *          1  :  the_list = pointer to list
 437  *          2  :  name = HTTP header name (e.g. "Content-type")
 438  *          3  :  value = HTTP header value (e.g. "text/html")
 439  *
 440  * Returns     :  0 on success, nonzero on out-of-memory error.  On
 441  *                error, the_list will be unchanged.  "Success"
 442  *                does not indicate whether or not the header was
 443  *                already in the list.
 444  *
 445  *********************************************************************/
 446 int enlist_unique_header(struct list *the_list, const char *name, const char *value)
 447 {
 448    int length;
 449    int result;
 450    char *str;
 451
 452    assert(the_list);
 453    assert(list_is_valid(the_list));
 454    assert(name);
 455    assert(value);
 456
 457    length = strlen(name) + 2;
 458    if (NULL == (str = (char *)malloc(length + strlen(value) + 1)))
 459    {
 460       return 1;
 461    }
 462    strcpy(str, name);
 463    str[length - 2] = ':';
 464    str[length - 1] = ' ';
 465    strcpy(str + length, value);
 466
 467    result = enlist_unique(the_list, str, length);
 468
 469    free(str);
 470
 471    assert(list_is_valid(the_list));
 472
 473    return result;
 474 }
 475
 476
 477 /*********************************************************************
 478  *
 479  * Function    :  list_remove_all
 480  *
 481  * Description :  Remove all entries from a list.  On return, the_list
 482  *                is a valid, empty list.  Note that this is similar
 483  *                to destroy_list(), but the difference is that this
 484  *                function guarantees that the list structure is still
 485  *                valid after the call.
 486  *
 487  * Parameters  :
 488  *          1  :  the_list = pointer to list
 489  *
 490  * Returns     :  N/A
 491  *
 492  *********************************************************************/
 493 void list_remove_all(struct list *the_list)
 494 {
 495    struct list_entry *cur_entry;
 496    struct list_entry *next_entry;
 497
 498    assert(the_list);
 499    assert(list_is_valid(the_list));
 500
 501    for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
 502    {
 503       next_entry = cur_entry->next;
 504       freez((char *)cur_entry->str);
 505       free(cur_entry);
 506    }
 507
 508    the_list->first = the_list->last = NULL;
 509
 510    assert(list_is_valid(the_list));
 511 }
 512
 513
 514 /*********************************************************************
 515  *
 516  * Function    :  list_to_text
 517  *
 518  * Description :  "Flatten" a string list into 1 long \r\n delimited string,
 519  *                adding an empty line at the end.  NULL entries are ignored.
 520  *                This function does not change the_list.
 521  *
 522  * Parameters  :
 523  *          1  :  the_list = pointer to list
 524  *
 525  * Returns     :  NULL on malloc error, else new long string.
 526  *                Caller must free() it.
 527  *
 528  *********************************************************************/
 529 char *list_to_text(const struct list *the_list)
 530 {
 531    struct list_entry *cur_entry;
 532    char *ret = NULL;
 533    char *s;
 534    int size = 2;
 535
 536    assert(the_list);
 537    assert(list_is_valid(the_list));
 538
 539    for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
 540    {
 541       if (cur_entry->str)
 542       {
 543          size += strlen(cur_entry->str) + 2;
 544       }
 545    }
 546
 547    if ((ret = (char *)malloc(size + 1)) == NULL)
 548    {
 549       return(NULL);
 550    }
 551
 552    ret[size] = '\0';
 553
 554    s = ret;
 555
 556    for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
 557    {
 558       if (cur_entry->str)
 559       {
 560          strcpy(s, cur_entry->str);
 561          s += strlen(s);
 562          *s++ = '\r'; *s++ = '\n';
 563       }
 564    }
 565    *s++ = '\r'; *s++ = '\n';
 566
 567    return(ret);
 568 }
 569
 570
 571 /*********************************************************************
 572  *
 573  * Function    :  list_remove_item
 574  *
 575  * Description :  Remove a string from a specified string list.
 576  *
 577  * Parameters  :
 578  *          1  :  the_list = pointer to list
 579  *          2  :  str = string to remove from the list - non-NULL
 580  *
 581  * Returns     :  Number of times it was removed.
 582  *
 583  *********************************************************************/
 584 int list_remove_item(struct list *the_list, const char *str)
 585 {
 586    struct list_entry *prev = NULL;
 587    struct list_entry *cur;
 588    struct list_entry *next;
 589    int count = 0;
 590
 591    assert(the_list);
 592    assert(list_is_valid(the_list));
 593    assert(str);
 594
 595    cur = the_list->first;
 596
 597    while (cur != NULL)
 598    {
 599       next = cur->next;
 600
 601       if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
 602       {
 603          count++;
 604
 605          if (prev != NULL)
 606          {
 607             prev->next = next;
 608          }
 609          else
 610          {
 611             the_list->first = next;
 612          }
 613          free((char *)cur->str);
 614          free(cur);
 615       }
 616       else
 617       {
 618          prev = cur;
 619       }
 620       cur = next;
 621    }
 622
 623    the_list->last = prev;
 624
 625    assert(list_is_valid(the_list));
 626
 627    return count;
 628 }
 629
 630
 631 /*********************************************************************
 632  *
 633  * Function    :  list_remove_list
 634  *
 635  * Description :  Remove all strings in one list from another list.
 636  *                This is currently a brute-force algorithm
 637  *                (it compares every pair of strings).
 638  *
 639  * Parameters  :
 640  *          1  :  dest = list to change
 641  *          2  :  src = list of strings to remove
 642  *
 643  * Returns     :  Total number of strings removed.
 644  *
 645  *********************************************************************/
 646 int list_remove_list(struct list *dest, const struct list *src)
 647 {
 648    struct list_entry *cur;
 649    int count = 0;
 650
 651    assert(src);
 652    assert(dest);
 653    assert(list_is_valid(src));
 654    assert(list_is_valid(dest));
 655
 656    for (cur = src->first; cur != NULL; cur = cur->next)
 657    {
 658       if (cur->str != NULL)
 659       {
 660          count += list_remove_item(dest, cur->str);
 661       }
 662    }
 663
 664    assert(list_is_valid(src));
 665    assert(list_is_valid(dest));
 666
 667    return count;
 668 }
 669
 670
 671 /*********************************************************************
 672  *
 673  * Function    :  list_duplicate
 674  *
 675  * Description :  Copy a string list
 676  *
 677  * Parameters  :
 678  *          1  :  dest = Destination list.  Must be a valid list.
 679  *                       All existing entries will be removed.
 680  *          1  :  src = pointer to source list for copy.
 681  *
 682  * Returns     :  0 on success, nonzero on error.  On error, dest
 683  *                will be empty.
 684  *
 685  *********************************************************************/
 686 int list_duplicate(struct list *dest, const struct list *src)
 687 {
 688    struct list_entry * cur_src;
 689    struct list_entry * cur_dest;
 690
 691    assert(src);
 692    assert(dest);
 693    assert(list_is_valid(src));
 694    assert(list_is_valid(dest));
 695
 696    list_remove_all(dest);
 697
 698    /* Need to process first entry specially so we can set dest->first */
 699    cur_src = src->first;
 700    if (cur_src)
 701    {
 702       cur_dest = dest->first = (struct list_entry *)zalloc(sizeof(*cur_dest));
 703       if (cur_dest == NULL)
 704       {
 705          destroy_list(dest);
 706
 707          assert(list_is_valid(src));
 708          assert(list_is_valid(dest));
 709
 710          return 1;
 711       }
 712
 713       if (cur_src->str)
 714       {
 715          cur_dest->str = strdup(cur_src->str);
 716          if (cur_dest->str == NULL)
 717          {
 718             destroy_list(dest);
 719
 720             assert(list_is_valid(src));
 721             assert(list_is_valid(dest));
 722
 723             return 1;
 724          }
 725       }
 726       /* else { cur_dest->str = NULL; }  - implied by zalloc */
 727
 728       /* Now process the rest */
 729       for (cur_src = cur_src->next; cur_src; cur_src = cur_src->next)
 730       {
 731          cur_dest = cur_dest->next = (struct list_entry *)zalloc(sizeof(*cur_dest));
 732          if (cur_dest == NULL)
 733          {
 734             destroy_list(dest);
 735
 736             assert(list_is_valid(src));
 737             assert(list_is_valid(dest));
 738
 739             return 1;
 740          }
 741          if (cur_src->str)
 742          {
 743             cur_dest->str = strdup(cur_src->str);
 744             if (cur_dest->str == NULL)
 745             {
 746                destroy_list(dest);
 747
 748                assert(list_is_valid(src));
 749                assert(list_is_valid(dest));
 750
 751                return 1;
 752             }
 753          }
 754          /* else { cur_dest->str = NULL; }  - implied by zalloc */
 755       }
 756
 757       dest->last = cur_dest;
 758    }
 759
 760    assert(list_is_valid(src));
 761    assert(list_is_valid(dest));
 762
 763    return 0;
 764 }
 765
 766
 767 /*********************************************************************
 768  *
 769  * Function    :  list_append_list_unique
 770  *
 771  * Description :  Append a string list to another list.
 772  *                Duplicate items are not added.
 773  *
 774  * Parameters  :
 775  *          1  :  dest = pointer to destination list for merge.
 776  *          2  :  src = pointer to source for merge.
 777  *
 778  * Returns     :  0 on success, nonzero on out-of-memory error.
 779  *                On error, some (but not all) of src might have
 780  *                been copied into dest.
 781  *
 782  *********************************************************************/
 783 int list_append_list_unique(struct list *dest, const struct list *src)
 784 {
 785    struct list_entry * cur;
 786
 787    assert(src);
 788    assert(dest);
 789    assert(list_is_valid(src));
 790    assert(list_is_valid(dest));
 791
 792    for (cur = src->first; cur; cur = cur->next)
 793    {
 794       if (cur->str)
 795       {
 796          if (enlist_unique(dest, cur->str, 0))
 797          {
 798             assert(list_is_valid(src));
 799             assert(list_is_valid(dest));
 800
 801             return 1;
 802          }
 803       }
 804    }
 805
 806    assert(list_is_valid(src));
 807    assert(list_is_valid(dest));
 808
 809    return 0;
 810 }
 811
 812
 813 /*********************************************************************
 814  *
 815  * Function    :  list_is_empty
 816  *
 817  * Description :  Test whether a list is empty.  Does not change the list.
 818  *
 819  * Parameters  :
 820  *          1  :  the_list = pointer to list to test.
 821  *
 822  * Returns     :  Nonzero iff the list contains no entries.
 823  *
 824  *********************************************************************/
 825 int list_is_empty(const struct list *the_list)
 826 {
 827    assert(the_list);
 828    assert(list_is_valid(the_list));
 829
 830    return (the_list->first == NULL);
 831 }
 832
 833
 834 /*********************************************************************
 835  *
 836  * Function    :  new_map
 837  *
 838  * Description :  Create a new, empty map.
 839  *
 840  * Parameters  :  N/A
 841  *
 842  * Returns     :  A new, empty map, or NULL if out of memory.
 843  *
 844  *********************************************************************/
 845 struct map *new_map(void)
 846 {
 847    return (struct map *) zalloc(sizeof(struct map));
 848 }
 849
 850
 851 /*********************************************************************
 852  *
 853  * Function    :  free_map
 854  *
 855  * Description :  Free the memory occupied by a map and its
 856  *                depandant strings
 857  *
 858  * Parameters  :
 859  *          1  :  the_map = map to be freed.  May be NULL.
 860  *
 861  * Returns     :  N/A
 862  *
 863  *********************************************************************/
 864 void free_map(struct map *the_map)
 865 {
 866    struct map_entry *cur_entry;
 867    struct map_entry *next_entry;
 868
 869    if (the_map == NULL)
 870    {
 871       return;
 872    }
 873
 874    for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = next_entry)
 875    {
 876       freez((char *)cur_entry->name);
 877       freez((char *)cur_entry->value);
 878
 879       next_entry = cur_entry->next;
 880       free(cur_entry);
 881    }
 882
 883    the_map->first = the_map->last = NULL;
 884
 885    free(the_map);
 886 }
 887
 888
 889 /*********************************************************************
 890  *
 891  * Function    :  map
 892  *
 893  * Description :  Add a mapping from given name to given value to a
 894  *                given map.
 895  *
 896  *                Note: Since all strings will be free()d in free_map()
 897  *                      later, set the copy flags for constants or
 898  *                      strings that will be independantly free()d.
 899  *
 900  * Parameters  :
 901  *          1  :  the_map = map to add to
 902  *          2  :  name = name to add
 903  *          3  :  name_needs_copying = flag set if a copy of name should be used
 904  *          4  :  value = value to add
 905  *          5  :  value_needs_copying = flag set if a copy of value should be used
 906  *
 907  * Returns     :  0 on success, nonzero on out-of-memory error.
 908  *
 909  *********************************************************************/
 910 int map(struct map *the_map,
 911         const char *name, int name_needs_copying,
 912         const char *value, int value_needs_copying)
 913 {
 914    struct map_entry *new_entry;
 915
 916    assert(the_map);
 917    assert(name);
 918    assert(value);
 919
 920    if (NULL == (new_entry = zalloc(sizeof(*new_entry))))
 921    {
 922       return 1;
 923    }
 924
 925    if (name_needs_copying)
 926    {
 927       if (NULL == (name = strdup(name)))
 928       {
 929          free(new_entry);
 930          return 1;
 931       }
 932    }
 933
 934    if (value_needs_copying)
 935    {
 936       if (NULL == (value = strdup(value)))
 937       {
 938          if (name_needs_copying)
 939          {
 940              free((char *)name);
 941          }
 942          free(new_entry);
 943          return 1;
 944       }
 945    }
 946
 947    new_entry->name = name;
 948    new_entry->value = value;
 949    /* new_entry->next = NULL;  - implied by zalloc */
 950
 951    if (the_map->last)
 952    {
 953       the_map->last->next = new_entry;
 954       the_map->last = new_entry;
 955    }
 956    else
 957    {
 958       the_map->first = new_entry;
 959       the_map->last = new_entry;
 960    }
 961
 962    return 0;
 963 }
 964
 965
 966 /*********************************************************************
 967  *
 968  * Function    :  lookup
 969  *
 970  * Description :  Look up an item with a given name in a map, and
 971  *                return its value
 972  *
 973  * Parameters  :
 974  *          1  :  the_map = map to look in
 975  *          2  :  name = name parameter to look for
 976  *
 977  * Returns     :  the value if found, else the empty string.
 978  *                Return value is alloced as part of the map, so
 979  *                it is freed when the map is destroyed.  Caller
 980  *                must not free or modify it.
 981  *
 982  *********************************************************************/
 983 const char *lookup(const struct map *the_map, const char *name)
 984 {
 985    const struct map_entry *cur_entry;
 986
 987    assert(the_map);
 988    assert(name);
 989
 990    for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
 991    {
 992       if (!strcmp(name, cur_entry->name))
 993       {
 994          return cur_entry->value;
 995       }
 996    }
 997    return "";
 998 }
 999
1000
1001 /*
1002   Local Variables:
1003   tab-width: 3
1004   end:
1005 */