list.c

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