list.c

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