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