list.c

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