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