1 const char list_rcs[] = "$Id: list.c,v 1.17 2006/07/18 14:48:46 david__schmidt Exp $";
2 /*********************************************************************
4 * File : $Source: /cvsroot/ijbswa/current/list.c,v $
6 * Purpose : Declares functions to handle lists.
7 * Functions declared include:
8 * `destroy_list', `enlist' and `list_to_text'
10 * Copyright : Written by and Copyright (C) 2001 the SourceForge
11 * Privoxy team. http://www.privoxy.org/
13 * Based on the Internet Junkbuster originally written
14 * by and Copyright (C) 1997 Anonymous Coders and
15 * Junkbusters Corporation. http://www.junkbusters.com
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.
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.
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.
37 * Revision 1.17 2006/07/18 14:48:46 david__schmidt
38 * Reorganizing the repository: swapping out what was HEAD (the old 3.1 branch)
39 * with what was really the latest development (the v_3_0_branch branch)
41 * Revision 1.15.2.2 2004/05/25 02:04:23 david__schmidt
42 * Removed the "arbitrary" 1000 filter limit in file.c. See tracker #911950.
44 * Revision 1.15.2.1 2002/11/28 18:14:54 oes
45 * Added unmap function that removes all items with a given
48 * Revision 1.15 2002/03/26 22:29:55 swa
49 * we have a new homepage!
51 * Revision 1.14 2002/03/24 13:25:43 swa
52 * name change related issues
54 * Revision 1.13 2002/03/07 03:46:17 oes
55 * Fixed compiler warnings
57 * Revision 1.12 2001/10/25 03:40:48 david__schmidt
58 * Change in porting tactics: OS/2's EMX porting layer doesn't allow multiple
59 * threads to call select() simultaneously. So, it's time to do a real, live,
60 * native OS/2 port. See defines for __EMX__ (the porting layer) vs. __OS2__
61 * (native). Both versions will work, but using __OS2__ offers multi-threading.
63 * Revision 1.11 2001/10/23 21:21:03 jongfoster
64 * New error handling - error codes are now jb_errs, not ints.
65 * Changed the way map() handles out-of-memory, to dramatically
66 * reduce the amount of error-checking clutter needed.
68 * Revision 1.10 2001/09/16 17:30:24 jongfoster
69 * Fixing a compiler warning.
71 * Revision 1.9 2001/09/16 13:20:29 jongfoster
72 * Rewrite of list library. Now has seperate header and list_entry
73 * structures. Also added a large sprinking of assert()s to the list
76 * Revision 1.8 2001/08/07 14:00:20 oes
79 * Revision 1.7 2001/08/05 16:06:20 jongfoster
80 * Modifiying "struct map" so that there are now separate header and
81 * "map_entry" structures. This means that functions which modify a
82 * map no longer need to return a pointer to the modified map.
83 * Also, it no longer reverses the order of the entries (which may be
84 * important with some advanced template substitutions).
86 * Revision 1.6 2001/07/31 14:44:51 oes
87 * list_to_text() now appends empty line at end
89 * Revision 1.5 2001/06/29 21:45:41 oes
90 * Indentation, CRLF->LF, Tab-> Space
92 * Revision 1.4 2001/06/29 13:30:22 oes
93 * - Added Convenience function enlist_unique_header(),
94 * which takes the Header name and value as separate
95 * arguments and thus saves the pain of sprintf()ing
96 * and determining the Header name length to enlist_unique
98 * - Removed logentry from cancelled commit
100 * Revision 1.3 2001/06/03 19:12:24 oes
101 * functions for new struct map, extended enlist_unique
103 * Revision 1.2 2001/06/01 18:49:17 jongfoster
104 * Replaced "list_share" with "list" - the tiny memory gain was not
105 * worth the extra complexity.
107 * Revision 1.1 2001/05/31 21:11:53 jongfoster
108 * - Moved linked list support to new "list.c" file.
109 * Structure definitions are still in project.h,
110 * function prototypes are now in "list.h".
111 * - Added support for "struct list_share", which is identical
112 * to "struct list" except it saves memory by not duplicating
113 * the strings. Obviously, this only works if there is some
114 * other way of managing the memory used by the strings.
115 * (These list_share lists are used for lists which last
116 * for only 1 request, and where all the list entries are
117 * just coming directly from entries in the actionsfile.)
118 * Note that you still need to destroy list_share lists
119 * properly to free the nodes - it's only the strings
123 *********************************************************************/
129 /* FIXME: The following headers are not needed for Win32. Are they
130 * needed on other platforms?
133 #include <sys/types.h>
139 #if !defined(_WIN32) && !defined(__OS2__)
147 #include "miscutil.h"
149 const char list_h_rcs[] = LIST_H_VERSION;
152 static int list_is_valid (const struct list *the_list);
155 /*********************************************************************
157 * Function : init_list
159 * Description : Create a new, empty list in user-allocated memory.
160 * Caller should allocate a "struct list" variable,
161 * then pass it to this function.
162 * (Implementation note: Rather than calling this
163 * function, you can also just memset the memory to
164 * zero, e.g. if you have a larger structure you
165 * want to initialize quickly. However, that isn't
166 * really good design.)
169 * 1 : the_list = pointer to list
173 *********************************************************************/
174 void init_list(struct list *the_list)
176 memset(the_list, '\0', sizeof(*the_list));
180 /*********************************************************************
182 * Function : destroy_list
184 * Description : Destroy a string list (opposite of list_init).
185 * On return, the memory used by the list entries has
186 * been freed, but not the memory used by the_list
187 * itself. You should not re-use the_list without
188 * calling list_init().
190 * (Implementation note: You *can* reuse the_list
191 * without calling list_init(), but please don't.
192 * If you want to remove all entries from a list
193 * and still have a usable list, then use
194 * list_remove_all().)
197 * 1 : the_list = pointer to list
201 *********************************************************************/
202 void destroy_list (struct list *the_list)
204 struct list_entry *cur_entry, *next_entry;
208 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
210 next_entry = cur_entry->next;
211 freez(cur_entry->str);
215 the_list->first = NULL;
216 the_list->last = NULL;
220 /*********************************************************************
222 * Function : list_is_valid
224 * Description : Check that a string list is valid. The intended
225 * usage is "assert(list_is_valid(the_list))".
226 * Currently this checks that "the_list->last"
227 * is correct, and that the list dosn't contain
228 * circular references. It is likely to crash if
229 * it's passed complete garbage.
232 * 1 : the_list = pointer to list. Must be non-null.
234 * Returns : 1 if list is valid, 0 otherwise.
236 *********************************************************************/
237 static int list_is_valid (const struct list *the_list)
240 * If you don't want this check, just change the line below
241 * from "#if 1" to "#if 0".
244 const struct list_entry *cur_entry;
245 const struct list_entry *last_entry = NULL;
250 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
252 last_entry = cur_entry;
257 * Just check that this string can be accessed - i.e. it's a valid
260 (void)strlen(cur_entry->str);
264 * Check for looping back to first
266 if ((entry++ != 0) && (cur_entry == the_list->first))
272 * Arbitrarily limit list length to prevent infinite loops.
273 * Note that the 1000 limit was hit by a real user in tracker 911950;
274 * removing it for now. Real circular references should eventually
275 * be caught by the check above, anyway.
285 * Check this isn't marked as the last entry, unless of course it's
286 * *really* the last entry.
288 if ((the_list->last == cur_entry) && (cur_entry->next != NULL))
290 /* This is the last entry, but there's data after it !!?? */
295 return (the_list->last == last_entry);
301 /*********************************************************************
305 * Description : Append a string into a specified string list.
308 * 1 : the_list = pointer to list
309 * 2 : str = string to add to the list (maybe NULL)
311 * Returns : JB_ERR_OK on success
312 * JB_ERR_MEMORY on out-of-memory error.
313 * On error, the_list will be unchanged.
315 *********************************************************************/
316 jb_err enlist(struct list *the_list, const char *str)
318 struct list_entry *cur;
321 assert(list_is_valid(the_list));
323 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
325 return JB_ERR_MEMORY;
330 if (NULL == (cur->str = strdup(str)))
333 return JB_ERR_MEMORY;
336 /* else { cur->str = NULL; } - implied by zalloc */
338 /* cur->next = NULL; - implied by zalloc */
342 the_list->last->next = cur;
343 the_list->last = cur;
347 the_list->first = cur;
348 the_list->last = cur;
351 assert(list_is_valid(the_list));
356 /*********************************************************************
358 * Function : enlist_first
360 * Description : Append a string as first element into a specified
364 * 1 : the_list = pointer to list
365 * 2 : str = string to add to the list (maybe NULL)
367 * Returns : JB_ERR_OK on success
368 * JB_ERR_MEMORY on out-of-memory error.
369 * On error, the_list will be unchanged.
371 *********************************************************************/
372 jb_err enlist_first(struct list *the_list, const char *str)
374 struct list_entry *cur;
377 assert(list_is_valid(the_list));
379 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
381 return JB_ERR_MEMORY;
386 if (NULL == (cur->str = strdup(str)))
389 return JB_ERR_MEMORY;
392 /* else { cur->str = NULL; } - implied by zalloc */
394 cur->next = the_list->first;
396 the_list->first = cur;
397 if (the_list->last == NULL)
399 the_list->last = cur;
402 assert(list_is_valid(the_list));
407 /*********************************************************************
409 * Function : enlist_unique
411 * Description : Append a string into a specified string list,
412 * if & only if it's not there already.
413 * If the num_significant_chars argument is nonzero,
414 * only compare up to the nth character.
417 * 1 : the_list = pointer to list
418 * 2 : str = string to add to the list
419 * 3 : num_significant_chars = number of chars to use
420 * for uniqueness test, or 0 to require an exact match.
422 * Returns : JB_ERR_OK on success
423 * JB_ERR_MEMORY on out-of-memory error.
424 * On error, the_list will be unchanged.
425 * "Success" does not indicate whether or not the
426 * item was already in the list.
428 *********************************************************************/
429 jb_err enlist_unique(struct list *the_list, const char *str,
430 size_t num_significant_chars)
432 struct list_entry *cur_entry;
435 assert(list_is_valid(the_list));
437 assert(num_significant_chars >= 0);
438 assert(num_significant_chars <= strlen(str));
440 if (num_significant_chars > 0)
442 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
444 if ( (cur_entry->str != NULL)
445 && (0 == strncmp(str, cur_entry->str, num_significant_chars)))
454 /* Test whole string */
455 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
457 if ( (cur_entry->str != NULL) && (0 == strcmp(str, cur_entry->str)))
465 return enlist(the_list, str);
469 /*********************************************************************
471 * Function : enlist_unique_header
473 * Description : Make a HTTP header from the two strings name and value,
474 * and append the result into a specified string list,
475 * if & only if there isn't already a header with that name.
478 * 1 : the_list = pointer to list
479 * 2 : name = HTTP header name (e.g. "Content-type")
480 * 3 : value = HTTP header value (e.g. "text/html")
482 * Returns : JB_ERR_OK on success
483 * JB_ERR_MEMORY on out-of-memory error.
484 * On error, the_list will be unchanged.
485 * "Success" does not indicate whether or not the
486 * header was already in the list.
488 *********************************************************************/
489 jb_err enlist_unique_header(struct list *the_list, const char *name,
497 assert(list_is_valid(the_list));
501 length = strlen(name) + 2;
502 if (NULL == (str = (char *)malloc(length + strlen(value) + 1)))
504 return JB_ERR_MEMORY;
507 str[length - 2] = ':';
508 str[length - 1] = ' ';
509 strcpy(str + length, value);
511 result = enlist_unique(the_list, str, length);
515 assert(list_is_valid(the_list));
522 /*********************************************************************
524 * Function : list_remove_all
526 * Description : Remove all entries from a list. On return, the_list
527 * is a valid, empty list. Note that this is similar
528 * to destroy_list(), but the difference is that this
529 * function guarantees that the list structure is still
530 * valid after the call.
533 * 1 : the_list = pointer to list
537 *********************************************************************/
538 void list_remove_all(struct list *the_list)
540 struct list_entry *cur_entry;
541 struct list_entry *next_entry;
544 assert(list_is_valid(the_list));
546 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
548 next_entry = cur_entry->next;
549 freez(cur_entry->str);
553 the_list->first = the_list->last = NULL;
555 assert(list_is_valid(the_list));
559 /*********************************************************************
561 * Function : list_to_text
563 * Description : "Flatten" a string list into 1 long \r\n delimited string,
564 * adding an empty line at the end. NULL entries are ignored.
565 * This function does not change the_list.
568 * 1 : the_list = pointer to list
570 * Returns : NULL on malloc error, else new long string.
571 * Caller must free() it.
573 *********************************************************************/
574 char *list_to_text(const struct list *the_list)
576 struct list_entry *cur_entry;
582 assert(list_is_valid(the_list));
584 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
588 size += strlen(cur_entry->str) + 2;
592 if ((ret = (char *)malloc(size + 1)) == NULL)
601 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
605 strcpy(s, cur_entry->str);
607 *s++ = '\r'; *s++ = '\n';
610 *s++ = '\r'; *s++ = '\n';
616 /*********************************************************************
618 * Function : list_remove_item
620 * Description : Remove a string from a specified string list.
623 * 1 : the_list = pointer to list
624 * 2 : str = string to remove from the list - non-NULL
626 * Returns : Number of times it was removed.
628 *********************************************************************/
629 int list_remove_item(struct list *the_list, const char *str)
631 struct list_entry *prev = NULL;
632 struct list_entry *cur;
633 struct list_entry *next;
637 assert(list_is_valid(the_list));
640 cur = the_list->first;
646 if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
656 the_list->first = next;
658 free((char *)cur->str);
668 the_list->last = prev;
670 assert(list_is_valid(the_list));
676 /*********************************************************************
678 * Function : list_remove_list
680 * Description : Remove all strings in one list from another list.
681 * This is currently a brute-force algorithm
682 * (it compares every pair of strings).
685 * 1 : dest = list to change
686 * 2 : src = list of strings to remove
688 * Returns : Total number of strings removed.
690 *********************************************************************/
691 int list_remove_list(struct list *dest, const struct list *src)
693 struct list_entry *cur;
698 assert(list_is_valid(src));
699 assert(list_is_valid(dest));
701 for (cur = src->first; cur != NULL; cur = cur->next)
703 if (cur->str != NULL)
705 count += list_remove_item(dest, cur->str);
709 assert(list_is_valid(src));
710 assert(list_is_valid(dest));
716 /*********************************************************************
718 * Function : list_duplicate
720 * Description : Copy a string list
723 * 1 : dest = Destination list. Must be a valid list.
724 * All existing entries will be removed.
725 * 1 : src = pointer to source list for copy.
727 * Returns : JB_ERR_OK on success
728 * JB_ERR_MEMORY on out-of-memory error.
729 * On error, dest will be empty.
731 *********************************************************************/
732 jb_err list_duplicate(struct list *dest, const struct list *src)
734 struct list_entry * cur_src;
735 struct list_entry * cur_dest;
739 assert(list_is_valid(src));
740 assert(list_is_valid(dest));
742 list_remove_all(dest);
744 /* Need to process first entry specially so we can set dest->first */
745 cur_src = src->first;
748 cur_dest = dest->first = (struct list_entry *)zalloc(sizeof(*cur_dest));
749 if (cur_dest == NULL)
753 assert(list_is_valid(src));
754 assert(list_is_valid(dest));
756 return JB_ERR_MEMORY;
761 cur_dest->str = strdup(cur_src->str);
762 if (cur_dest->str == NULL)
766 assert(list_is_valid(src));
767 assert(list_is_valid(dest));
769 return JB_ERR_MEMORY;
772 /* else { cur_dest->str = NULL; } - implied by zalloc */
774 /* Now process the rest */
775 for (cur_src = cur_src->next; cur_src; cur_src = cur_src->next)
777 cur_dest = cur_dest->next = (struct list_entry *)zalloc(sizeof(*cur_dest));
778 if (cur_dest == NULL)
782 assert(list_is_valid(src));
783 assert(list_is_valid(dest));
785 return JB_ERR_MEMORY;
789 cur_dest->str = strdup(cur_src->str);
790 if (cur_dest->str == NULL)
794 assert(list_is_valid(src));
795 assert(list_is_valid(dest));
797 return JB_ERR_MEMORY;
800 /* else { cur_dest->str = NULL; } - implied by zalloc */
803 dest->last = cur_dest;
806 assert(list_is_valid(src));
807 assert(list_is_valid(dest));
813 /*********************************************************************
815 * Function : list_append_list_unique
817 * Description : Append a string list to another list.
818 * Duplicate items are not added.
821 * 1 : dest = pointer to destination list for merge.
822 * 2 : src = pointer to source for merge.
824 * Returns : JB_ERR_OK on success
825 * JB_ERR_MEMORY on out-of-memory error.
826 * On error, some (but not all) of src might have
827 * been copied into dest.
829 *********************************************************************/
830 jb_err list_append_list_unique(struct list *dest, const struct list *src)
832 struct list_entry * cur;
836 assert(list_is_valid(src));
837 assert(list_is_valid(dest));
839 for (cur = src->first; cur; cur = cur->next)
843 if (enlist_unique(dest, cur->str, 0))
845 assert(list_is_valid(src));
846 assert(list_is_valid(dest));
848 return JB_ERR_MEMORY;
853 assert(list_is_valid(src));
854 assert(list_is_valid(dest));
860 /*********************************************************************
862 * Function : list_is_empty
864 * Description : Test whether a list is empty. Does not change the list.
867 * 1 : the_list = pointer to list to test.
869 * Returns : Nonzero iff the list contains no entries.
871 *********************************************************************/
872 int list_is_empty(const struct list *the_list)
875 assert(list_is_valid(the_list));
877 return (the_list->first == NULL);
881 /*********************************************************************
885 * Description : Create a new, empty map.
889 * Returns : A new, empty map, or NULL if out of memory.
891 *********************************************************************/
892 struct map *new_map(void)
894 return (struct map *) zalloc(sizeof(struct map));
898 /*********************************************************************
900 * Function : free_map
902 * Description : Free the memory occupied by a map and its
906 * 1 : the_map = map to be freed. May be NULL.
910 *********************************************************************/
911 void free_map(struct map *the_map)
913 struct map_entry *cur_entry;
914 struct map_entry *next_entry;
921 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = next_entry)
923 freez(cur_entry->name);
924 freez(cur_entry->value);
926 next_entry = cur_entry->next;
930 the_map->first = the_map->last = NULL;
936 /*********************************************************************
940 * Description : Add a mapping from given name to given value to a
943 * Note: Since all strings will be free()d in free_map()
944 * later, set the copy flags for constants or
945 * strings that will be independantly free()d.
947 * Note2: This function allows NULL parameters - it
948 * returns JB_ERR_MEMORY in that case.
950 * Note3: If this function returns JB_ERR_MEMORY,
951 * it will free(name) unless you specify
952 * name_needs_copying, and similarly it will
953 * free(value) unless you specify
954 * value_needs_copying.
956 * Due to Note2 and Note3 above, the following code
957 * is legal, and will never crash or leak memory even
958 * if the system runs out of memory:
960 * err = map(mymap, "xyz", 1, html_encode(somestring), 0);
962 * err will be set to JB_ERR_MEMORY if either call runs
963 * out-of-memory. Without these features, you would
964 * need to check the return value of html_encode in the
965 * above example for NULL, which (at least) doubles the
966 * amount of error-checking code needed.
969 * 1 : the_map = map to add to
970 * 2 : name = name to add
971 * 3 : name_needs_copying = flag set if a copy of name should be used
972 * 4 : value = value to add
973 * 5 : value_needs_copying = flag set if a copy of value should be used
975 * Returns : JB_ERR_OK on success
976 * JB_ERR_MEMORY on out-of-memory error.
978 *********************************************************************/
979 jb_err map(struct map *the_map,
980 const char *name, int name_needs_copying,
981 const char *value, int value_needs_copying)
983 struct map_entry *new_entry;
989 || (NULL == (new_entry = zalloc(sizeof(*new_entry)))) )
991 if ((name != NULL) && (!name_needs_copying))
995 if ((value != NULL) && (!value_needs_copying))
999 return JB_ERR_MEMORY;
1002 if (name_needs_copying)
1004 if (NULL == (name = strdup(name)))
1007 if (!value_needs_copying)
1009 free((char *)value);
1011 return JB_ERR_MEMORY;
1015 if (value_needs_copying)
1017 if (NULL == (value = strdup(value)))
1021 return JB_ERR_MEMORY;
1025 new_entry->name = name;
1026 new_entry->value = value;
1027 /* new_entry->next = NULL; - implied by zalloc */
1031 the_map->last->next = new_entry;
1032 the_map->last = new_entry;
1036 the_map->first = new_entry;
1037 the_map->last = new_entry;
1044 /*********************************************************************
1048 * Description : Remove all map_entry structs with a given name from
1052 * 1 : the_map = map to look in
1053 * 2 : name = name to unmap
1055 * Returns : JB_ERR_OK
1057 *********************************************************************/
1058 jb_err unmap(struct map *the_map, const char *name)
1060 struct map_entry *cur_entry, *last_entry;
1065 last_entry = the_map->first;
1067 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
1069 if (!strcmp(name, cur_entry->name))
1072 * Update the incoming pointer
1074 if (cur_entry == the_map->first)
1076 the_map->first = cur_entry->next;
1080 last_entry->next = cur_entry->next;
1084 * Update the map's last pointer
1086 if (cur_entry == the_map->last)
1088 the_map->last = last_entry;
1092 * Free the map_entry
1094 freez(cur_entry->name);
1095 freez(cur_entry->value);
1098 cur_entry = last_entry;
1102 last_entry = cur_entry;
1109 /*********************************************************************
1113 * Description : Look up an item with a given name in a map, and
1117 * 1 : the_map = map to look in
1118 * 2 : name = name parameter to look for
1120 * Returns : the value if found, else the empty string.
1121 * Return value is alloced as part of the map, so
1122 * it is freed when the map is destroyed. Caller
1123 * must not free or modify it.
1125 *********************************************************************/
1126 const char *lookup(const struct map *the_map, const char *name)
1128 const struct map_entry *cur_entry;
1133 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
1135 if (!strcmp(name, cur_entry->name))
1137 return cur_entry->value;