list.c

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