list.c

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