list.c

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