list.c

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