src/list.c

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