list.c

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