list.c

   1 const char list_rcs[] = "$Id: list.c,v 1.6 2001/07/31 14:44:51 oes Exp $";
   2 /*********************************************************************
   3  *
   4  * File        :  $Source: /cvsroot/ijbswa/current/list.c,v $
   5  *
   6  * Purpose     :  Declares functions to handle lists.
   7  *                Functions declared include:
   8  *                   `destroy_list', `enlist' and `list_to_text'
   9  *
  10  * Copyright   :  Written by and Copyright (C) 2001 the SourceForge
  11  *                IJBSWA team.  http://ijbswa.sourceforge.net
  12  *
  13  *                Based on the Internet Junkbuster originally written
  14  *                by and Copyright (C) 1997 Anonymous Coders and
  15  *                Junkbusters Corporation.  http://www.junkbusters.com
  16  *
  17  *                This program is free software; you can redistribute it
  18  *                and/or modify it under the terms of the GNU General
  19  *                Public License as published by the Free Software
  20  *                Foundation; either version 2 of the License, or (at
  21  *                your option) any later version.
  22  *
  23  *                This program is distributed in the hope that it will
  24  *                be useful, but WITHOUT ANY WARRANTY; without even the
  25  *                implied warranty of MERCHANTABILITY or FITNESS FOR A
  26  *                PARTICULAR PURPOSE.  See the GNU General Public
  27  *                License for more details.
  28  *
  29  *                The GNU General Public License should be included with
  30  *                this file.  If not, you can view it at
  31  *                http://www.gnu.org/copyleft/gpl.html
  32  *                or write to the Free Software Foundation, Inc., 59
  33  *                Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  34  *
  35  * Revisions   :
  36  *    $Log: list.c,v $
  37  *    Revision 1.6  2001/07/31 14:44:51  oes
  38  *    list_to_text() now appends empty line at end
  39  *
  40  *    Revision 1.5  2001/06/29 21:45:41  oes
  41  *    Indentation, CRLF->LF, Tab-> Space
  42  *
  43  *    Revision 1.4  2001/06/29 13:30:22  oes
  44  *    - Added Convenience function enlist_unique_header(),
  45  *      which takes the Header name and value as separate
  46  *      arguments and thus saves the pain of sprintf()ing
  47  *      and determining the Header name length to enlist_unique
  48  *    - Improved comments
  49  *    - Removed logentry from cancelled commit
  50  *
  51  *    Revision 1.3  2001/06/03 19:12:24  oes
  52  *    functions for new struct map, extended enlist_unique
  53  *
  54  *    Revision 1.2  2001/06/01 18:49:17  jongfoster
  55  *    Replaced "list_share" with "list" - the tiny memory gain was not
  56  *    worth the extra complexity.
  57  *
  58  *    Revision 1.1  2001/05/31 21:11:53  jongfoster
  59  *    - Moved linked list support to new "list.c" file.
  60  *      Structure definitions are still in project.h,
  61  *      function prototypes are now in "list.h".
  62  *    - Added support for "struct list_share", which is identical
  63  *      to "struct list" except it saves memory by not duplicating
  64  *      the strings.  Obviously, this only works if there is some
  65  *      other way of managing the memory used by the strings.
  66  *      (These list_share lists are used for lists which last
  67  *      for only 1 request, and where all the list entries are
  68  *      just coming directly from entries in the actionsfile.)
  69  *      Note that you still need to destroy list_share lists
  70  *      properly to free the nodes - it's only the strings
  71  *      which are shared.
  72  *
  73  *
  74  *********************************************************************/
  75 \f
  76
  77 #include "config.h"
  78
  79 #include <stdio.h>
  80 #include <sys/types.h>
  81 #include <stdlib.h>
  82 #include <ctype.h>
  83 #include <string.h>
  84
  85 #include <assert.h>
  86
  87 #ifndef _WIN32
  88 #include <unistd.h>
  89 #endif
  90
  91 #include "project.h"
  92 #include "jcc.h"
  93 #include "list.h"
  94 #include "miscutil.h"
  95
  96 const char list_h_rcs[] = LIST_H_VERSION;
  97
  98 /*********************************************************************
  99  *
 100  * Function    :  enlist
 101  *
 102  * Description :  Append a string into a specified string list.
 103  *
 104  * Parameters  :
 105  *          1  :  header = pointer to list 'dummy' header
 106  *          2  :  str = string to add to the list (maybe NULL)
 107  *
 108  * Returns     :  N/A
 109  *
 110  *********************************************************************/
 111 void enlist(struct list *header, const char *str)
 112 {
 113    struct list *cur = (struct list *)malloc(sizeof(*cur));
 114    struct list *last;
 115
 116    if (cur)
 117    {
 118       cur->str  = (str ? strdup(str) : NULL);
 119       cur->next = NULL;
 120
 121       last = header->last;
 122       if (last == NULL)
 123       {
 124          last = header;
 125       }
 126
 127       last->next   = cur;
 128       header->last = cur;
 129    }
 130
 131 }
 132
 133
 134 /*********************************************************************
 135  *
 136  * Function    :  enlist_first
 137  *
 138  * Description :  Append a string as first element into a specified
 139  *                string list.
 140  *
 141  * Parameters  :
 142  *          1  :  header = pointer to list 'dummy' header
 143  *          2  :  str = string to add to the list (maybe NULL)
 144  *
 145  * Returns     :  N/A
 146  *
 147  *********************************************************************/
 148 void enlist_first(struct list *header, const char *str)
 149 {
 150    struct list *cur = (struct list *)malloc(sizeof(*cur));
 151
 152    if (cur)
 153    {
 154       cur->str  = (str ? strdup(str) : NULL);
 155       cur->next = header->next;
 156
 157       header->next = cur;
 158       if (header->last == NULL)
 159       {
 160          header->last = cur;
 161       }
 162    }
 163
 164 }
 165
 166
 167 /*********************************************************************
 168  *
 169  * Function    :  enlist_unique
 170  *
 171  * Description :  Append a string into a specified string list,
 172  *                if & only if it's not there already.
 173  *                If the n argument is nonzero, only compare up to
 174  *                the nth character.
 175  *
 176  * Parameters  :
 177  *          1  :  header = pointer to list 'dummy' header
 178  *          2  :  str = string to add to the list (maybe NULL)
 179  *          3  :  n = number of chars to use for uniqueness test
 180  *
 181  * Returns     :  N/A
 182  *
 183  *********************************************************************/
 184 void enlist_unique(struct list *header, const char *str, int n)
 185 {
 186    struct list *last;
 187    struct list *cur = header->next;
 188
 189    while (cur != NULL)
 190    {
 191       if ((cur->str != NULL) && (
 192          (n && (0 == strncmp(str, cur->str, n))) ||
 193          (!n && (0 == strcmp(str, cur->str)))))
 194       {
 195          /* Already there */
 196          return;
 197       }
 198       cur = cur->next;
 199    }
 200
 201    cur = (struct list *)malloc(sizeof(*cur));
 202
 203    if (cur != NULL)
 204    {
 205       cur->str  = (str ? strdup(str) : NULL); /* FIXME check retval */
 206       cur->next = NULL;
 207
 208       last = header->last;
 209       if (last == NULL)
 210       {
 211          last = header;
 212       }
 213       last->next   = cur;
 214       header->last = cur;
 215    }
 216 }
 217
 218
 219 /*********************************************************************
 220  *
 221  * Function    :  enlist_unique_header
 222  *
 223  * Description :  Make a HTTP header from the two strings name and value,
 224  *                and append the result into a specified string list,
 225  *                if & only if there isn't already a header with that name.
 226  *
 227  * Parameters  :
 228  *          1  :  header = pointer to list 'dummy' header
 229  *          2  :  first = first string to add to the list (maybe NULL)
 230  *          3  :  second = number of chars to use for uniqueness test
 231  *
 232  * Returns     :  N/A
 233  *
 234  *********************************************************************/
 235 void enlist_unique_header(struct list *header, const char *name, const char *value)
 236 {
 237    struct list *last;
 238    struct list *cur = header->next;
 239    int length;
 240    char *dummy;
 241
 242    if (name == NULL || value == NULL) return;
 243
 244    dummy = strdup(name);
 245    dummy = strsav(dummy, ": ");
 246    length = strlen(dummy);
 247
 248    while (cur != NULL)
 249    {
 250       if ((cur->str != NULL) &&
 251                 (0 == strncmp(dummy, cur->str, length)))
 252       {
 253          /* Already there */
 254          return;
 255       }
 256       cur = cur->next;
 257    }
 258
 259    cur = (struct list *)malloc(sizeof(*cur));
 260
 261    if (cur != NULL)
 262    {
 263       cur->str  = strsav(dummy, value);
 264       cur->next = NULL;
 265
 266       last = header->last;
 267       if (last == NULL)
 268       {
 269          last = header;
 270       }
 271       last->next   = cur;
 272       header->last = cur;
 273    }
 274 }
 275
 276
 277 /*********************************************************************
 278  *
 279  * Function    :  destroy_list
 280  *
 281  * Description :  Destroy a string list (opposite of enlist)
 282  *
 283  * Parameters  :
 284  *          1  :  header = pointer to list 'dummy' header
 285  *
 286  * Returns     :  N/A
 287  *
 288  *********************************************************************/
 289 void destroy_list(struct list *header)
 290 {
 291    struct list *p, *n;
 292
 293    for (p = header->next; p ; p = n)
 294    {
 295       n = p->next;
 296       freez(p->str);
 297       free(p);
 298    }
 299
 300    memset(header, '\0', sizeof(*header));
 301
 302 }
 303
 304
 305 /*********************************************************************
 306  *
 307  * Function    :  list_to_text
 308  *
 309  * Description :  "Flaten" a string list into 1 long \r\n delimited string,
 310  *                adding an empty line at the end.
 311  *
 312  * Parameters  :
 313  *          1  :  h = pointer to list 'dummy' header
 314  *
 315  * Returns     :  NULL on malloc error, else new long string.
 316  *
 317  *********************************************************************/
 318 char *list_to_text(struct list *h)
 319 {
 320    struct list *p;
 321    char *ret = NULL;
 322    char *s;
 323    int size = 2;
 324
 325    for (p = h->next; p ; p = p->next)
 326    {
 327       if (p->str)
 328       {
 329          size += strlen(p->str) + 2;
 330       }
 331    }
 332
 333    if ((ret = (char *)malloc(size + 1)) == NULL)
 334    {
 335       return(NULL);
 336    }
 337
 338    ret[size] = '\0';
 339
 340    s = ret;
 341
 342    for (p = h->next; p ; p = p->next)
 343    {
 344       if (p->str)
 345       {
 346          strcpy(s, p->str);
 347          s += strlen(s);
 348          *s++ = '\r'; *s++ = '\n';
 349       }
 350    }
 351    *s++ = '\r'; *s++ = '\n';
 352
 353    return(ret);
 354
 355 }
 356
 357
 358 /*********************************************************************
 359  *
 360  * Function    :  list_remove_item
 361  *
 362  * Description :  Remove a string from a specified string list.
 363  *
 364  * Parameters  :
 365  *          1  :  header = pointer to list 'dummy' header
 366  *          2  :  str = string to remove from the list
 367  *
 368  * Returns     :  Number of times it was removed.
 369  *
 370  *********************************************************************/
 371 int list_remove_item(struct list *header, const char *str)
 372 {
 373    struct list *prev = header;
 374    struct list *cur = prev->next;
 375    int count = 0;
 376
 377    while (cur != NULL)
 378    {
 379       if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
 380       {
 381          count++;
 382
 383          prev->next = cur->next;
 384          free(cur->str);
 385          free(cur);
 386       }
 387       else
 388       {
 389          prev = cur;
 390       }
 391       cur = prev->next;
 392    }
 393
 394    header->last = prev;
 395
 396    return count;
 397 }
 398
 399
 400 /*********************************************************************
 401  *
 402  * Function    :  list_remove_list
 403  *
 404  * Description :  Remove all strings in one list from another list.
 405  *                This is currently a brute-force algorithm
 406  *                (it compares every pair of strings).
 407  *
 408  * Parameters  :
 409  *          1  :  dest = list to change
 410  *          2  :  src = list of strings to remove
 411  *
 412  * Returns     :  Total number of strings removed.
 413  *
 414  *********************************************************************/
 415 int list_remove_list(struct list *dest, const struct list *src)
 416 {
 417    struct list *cur = src->next;
 418    int count = 0;
 419
 420    while (cur != NULL)
 421    {
 422       if (cur->str != NULL)
 423       {
 424          count += list_remove_item(dest, cur->str);
 425       }
 426       cur = cur->next;
 427    }
 428
 429    return count;
 430 }
 431
 432
 433 /*********************************************************************
 434  *
 435  * Function    :  list_duplicate
 436  *
 437  * Description :  Duplicate a string list
 438  *
 439  * Parameters  :
 440  *          1  :  dest = pointer to destination for copy.  Caller allocs.
 441  *          2  :  src = pointer to source for copy.
 442  *
 443  * Returns     :  N/A
 444  *
 445  *********************************************************************/
 446 void list_duplicate(struct list *dest, const struct list *src)
 447 {
 448    struct list * cur_src = src->next;
 449    struct list * cur_dest = dest;
 450
 451    memset(dest, '\0', sizeof(*dest));
 452
 453    while (cur_src)
 454    {
 455       cur_dest = cur_dest->next = (struct list *)zalloc(sizeof(*cur_dest));
 456       if (cur_dest == NULL)
 457       {
 458          return;
 459       }
 460       cur_dest->str = strdup(cur_src->str);
 461       cur_src = cur_src->next;
 462    }
 463
 464    dest->last = cur_dest;
 465
 466 }
 467
 468
 469 /*********************************************************************
 470  *
 471  * Function    :  list_append_list_unique
 472  *
 473  * Description :  Append a string list to another list.
 474  *                Duplicate items are not added.
 475  *
 476  * Parameters  :
 477  *          1  :  dest = pointer to destination for merge.  Caller allocs.
 478  *          2  :  src = pointer to source for merge.
 479  *
 480  * Returns     :  N/A
 481  *
 482  *********************************************************************/
 483 void list_append_list_unique(struct list *dest, const struct list *src)
 484 {
 485    struct list * cur = src->next;
 486
 487    while (cur)
 488    {
 489       enlist_unique(dest, cur->str, 0);
 490       cur = cur->next;
 491    }
 492 }
 493
 494
 495 /*********************************************************************
 496  *
 497  * Function    :  map
 498  *
 499  * Description :  Add a mapping from given name to given value to a
 500  *                given map.
 501  *
 502  *                Note: Since all strings will be free()d in free_map()
 503  *                      later, use the copy flags for constants or
 504  *                      strings that will be independantly free()d.
 505  *
 506  * Parameters  :
 507  *          1  :  the_map = map to add to
 508  *          2  :  name = name to add
 509  *          3  :  nc = flag set if a copy of name should be used
 510  *          4  :  value = value to add
 511  *          5  :  vc = flag set if a copy of value should be used
 512  *
 513  * Returns     :  N/A
 514  *
 515  *********************************************************************/
 516 void map(struct map *the_map, const char *name, int nc, const char *value, int vc)
 517 {
 518    struct map_entry *new_entry;
 519
 520    if (NULL == (new_entry = zalloc(sizeof(*new_entry))))
 521    {
 522       return;
 523    }
 524
 525    new_entry->name  = nc ? strdup(name) : name;
 526    new_entry->value = vc ? strdup(value) : value;
 527    /* new_entry->next = NULL;  - implied by zalloc */
 528
 529    if (the_map->last)
 530    {
 531       the_map->last = the_map->last->next = new_entry;
 532    }
 533    else
 534    {
 535       the_map->last = the_map->first = new_entry;
 536    }
 537 }
 538
 539
 540 /*********************************************************************
 541  *
 542  * Function    :  lookup
 543  *
 544  * Description :  Look up an item with a given name in a map, and
 545  *                return its value
 546  *
 547  * Parameters  :
 548  *          1  :  name = name parameter to look for
 549  *
 550  * Returns     :  the value if found, else the empty string
 551  *
 552  *********************************************************************/
 553 const char *lookup(const struct map *the_map, const char *name)
 554 {
 555    const struct map_entry *cur_entry = the_map->first;
 556
 557    while (cur_entry)
 558    {
 559       if (!strcmp(name, cur_entry->name))
 560       {
 561          return cur_entry->value;
 562       }
 563       cur_entry = cur_entry->next;
 564    }
 565    return "";
 566 }
 567
 568
 569 /*********************************************************************
 570  *
 571  * Function    :  new_nap
 572  *
 573  * Description :  Create a new, empty map.
 574  *
 575  * Parameters  :
 576  *
 577  * Returns     :  A new, empty map, or NULL if out of memory.
 578  *
 579  *********************************************************************/
 580 struct map *new_map(void)
 581 {
 582    return (struct map *) zalloc(sizeof(struct map));
 583 }
 584
 585
 586 /*********************************************************************
 587  *
 588  * Function    :  free_map
 589  *
 590  * Description :  Free the memory occupied by a map and its
 591  *                depandant strings
 592  *
 593  * Parameters  :
 594  *          1  :  cur_entry = map to be freed.  May be NULL.
 595  *
 596  * Returns     :  N/A
 597  *
 598  *********************************************************************/
 599 void free_map(struct map *the_map)
 600 {
 601    struct map_entry *cur_entry;
 602    struct map_entry *next_entry;
 603
 604    if (the_map == NULL)
 605    {
 606       return;
 607    }
 608
 609    for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = next_entry)
 610    {
 611       freez((char *)cur_entry->name);
 612       freez((char *)cur_entry->value);
 613
 614       next_entry = cur_entry->next;
 615       free(cur_entry);
 616    }
 617
 618    the_map->first = the_map->last = NULL;
 619
 620    free(the_map);
 621 }
 622
 623
 624 /*
 625   Local Variables:
 626   tab-width: 3
 627   end:
 628 */