1 /*********************************************************************
3 * File : $Source: /cvsroot/ijbswa/current/list.c,v $
5 * Purpose : Declares functions to handle lists.
7 * Copyright : Written by and Copyright (C) 2001-2007 members of the
8 * Privoxy team. https://www.privoxy.org/
10 * Based on the Internet Junkbuster originally written
11 * by and Copyright (C) 1997 Anonymous Coders and
12 * Junkbusters Corporation. http://www.junkbusters.com
14 * This program is free software; you can redistribute it
15 * and/or modify it under the terms of the GNU General
16 * Public License as published by the Free Software
17 * Foundation; either version 2 of the License, or (at
18 * your option) any later version.
20 * This program is distributed in the hope that it will
21 * be useful, but WITHOUT ANY WARRANTY; without even the
22 * implied warranty of MERCHANTABILITY or FITNESS FOR A
23 * PARTICULAR PURPOSE. See the GNU General Public
24 * License for more details.
26 * The GNU General Public License should be included with
27 * this file. If not, you can view it at
28 * http://www.gnu.org/copyleft/gpl.html
29 * or write to the Free Software Foundation, Inc., 59
30 * Temple Place - Suite 330, Boston, MA 02111-1307, USA.
32 *********************************************************************/
38 /* FIXME: The following headers are not needed for Win32. Are they
39 * needed on other platforms?
42 #include <sys/types.h>
58 static int list_is_valid (const struct list *the_list);
61 /*********************************************************************
63 * Function : init_list
65 * Description : Create a new, empty list in user-allocated memory.
66 * Caller should allocate a "struct list" variable,
67 * then pass it to this function.
68 * (Implementation note: Rather than calling this
69 * function, you can also just memset the memory to
70 * zero, e.g. if you have a larger structure you
71 * want to initialize quickly. However, that isn't
72 * really good design.)
75 * 1 : the_list = pointer to list
79 *********************************************************************/
80 void init_list(struct list *the_list)
82 memset(the_list, '\0', sizeof(*the_list));
86 /*********************************************************************
88 * Function : destroy_list
90 * Description : Destroy a string list (opposite of list_init).
91 * On return, the memory used by the list entries has
92 * been freed, but not the memory used by the_list
93 * itself. You should not re-use the_list without
94 * calling list_init().
96 * (Implementation note: You *can* reuse the_list
97 * without calling list_init(), but please don't.
98 * If you want to remove all entries from a list
99 * and still have a usable list, then use
100 * list_remove_all().)
103 * 1 : the_list = pointer to list
107 *********************************************************************/
108 void destroy_list (struct list *the_list)
110 struct list_entry *cur_entry, *next_entry;
114 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
116 next_entry = cur_entry->next;
117 freez(cur_entry->str);
121 the_list->first = NULL;
122 the_list->last = NULL;
126 /*********************************************************************
128 * Function : list_is_valid
130 * Description : Check that a string list is valid. The intended
131 * usage is "assert(list_is_valid(the_list))".
132 * Currently this checks that "the_list->last"
133 * is correct, and that the list doesn't contain
134 * circular references. It is likely to crash if
135 * it's passed complete garbage.
138 * 1 : the_list = pointer to list. Must be non-null.
140 * Returns : 1 if list is valid, 0 otherwise.
142 *********************************************************************/
143 static int list_is_valid (const struct list *the_list)
146 * If you don't want this check, just change the line below
147 * from "#if 1" to "#if 0".
150 const struct list_entry *cur_entry;
151 const struct list_entry *last_entry = NULL;
156 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
158 last_entry = cur_entry;
163 * Just check that this string can be accessed - i.e. it's a valid
166 (void)strlen(cur_entry->str);
170 * Check for looping back to first
172 if ((entry++ != 0) && (cur_entry == the_list->first))
178 * Arbitrarily limit list length to prevent infinite loops.
179 * Note that the 1000 limit was hit by a real user in tracker 911950;
180 * removing it for now. Real circular references should eventually
181 * be caught by the check above, anyway.
191 * Check this isn't marked as the last entry, unless of course it's
192 * *really* the last entry.
194 if ((the_list->last == cur_entry) && (cur_entry->next != NULL))
196 /* This is the last entry, but there's data after it !!?? */
201 return (the_list->last == last_entry);
207 /*********************************************************************
211 * Description : Append a string into a specified string list.
214 * 1 : the_list = pointer to list
215 * 2 : str = string to add to the list (maybe NULL)
217 * Returns : JB_ERR_OK on success
218 * JB_ERR_MEMORY on out-of-memory error.
219 * On error, the_list will be unchanged.
221 *********************************************************************/
222 jb_err enlist(struct list *the_list, const char *str)
224 struct list_entry *cur;
227 assert(list_is_valid(the_list));
229 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
231 return JB_ERR_MEMORY;
236 if (NULL == (cur->str = strdup(str)))
239 return JB_ERR_MEMORY;
242 /* else { cur->str = NULL; } - implied by zalloc */
244 /* cur->next = NULL; - implied by zalloc */
248 the_list->last->next = cur;
249 the_list->last = cur;
253 the_list->first = cur;
254 the_list->last = cur;
257 assert(list_is_valid(the_list));
262 /*********************************************************************
264 * Function : enlist_first
266 * Description : Append a string as first element into a specified
270 * 1 : the_list = pointer to list
271 * 2 : str = string to add to the list (maybe NULL)
273 * Returns : JB_ERR_OK on success
274 * JB_ERR_MEMORY on out-of-memory error.
275 * On error, the_list will be unchanged.
277 *********************************************************************/
278 jb_err enlist_first(struct list *the_list, const char *str)
280 struct list_entry *cur;
283 assert(list_is_valid(the_list));
285 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
287 return JB_ERR_MEMORY;
292 if (NULL == (cur->str = strdup(str)))
295 return JB_ERR_MEMORY;
298 /* else { cur->str = NULL; } - implied by zalloc */
300 cur->next = the_list->first;
302 the_list->first = cur;
303 if (the_list->last == NULL)
305 the_list->last = cur;
308 assert(list_is_valid(the_list));
313 /*********************************************************************
315 * Function : enlist_unique
317 * Description : Append a string into a specified string list,
318 * if & only if it's not there already.
319 * If the num_significant_chars argument is nonzero,
320 * only compare up to the nth character.
323 * 1 : the_list = pointer to list
324 * 2 : str = string to add to the list
325 * 3 : num_significant_chars = number of chars to use
326 * for uniqueness test, or 0 to require an exact match.
328 * Returns : JB_ERR_OK on success
329 * JB_ERR_MEMORY on out-of-memory error.
330 * On error, the_list will be unchanged.
331 * "Success" does not indicate whether or not the
332 * item was already in the list.
334 *********************************************************************/
335 jb_err enlist_unique(struct list *the_list, const char *str,
336 size_t num_significant_chars)
338 struct list_entry *cur_entry;
341 assert(list_is_valid(the_list));
343 assert(num_significant_chars >= 0);
344 assert(num_significant_chars <= strlen(str));
346 if (num_significant_chars > 0)
348 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
350 if ((cur_entry->str != NULL)
351 && (0 == strncmp(str, cur_entry->str, num_significant_chars)))
360 /* Test whole string */
361 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
363 if ((cur_entry->str != NULL) && (0 == strcmp(str, cur_entry->str)))
371 return enlist(the_list, str);
375 /*********************************************************************
377 * Function : enlist_unique_header
379 * Description : Make a HTTP header from the two strings name and value,
380 * and append the result into a specified string list,
381 * if & only if there isn't already a header with that name.
384 * 1 : the_list = pointer to list
385 * 2 : name = HTTP header name (e.g. "Content-type")
386 * 3 : value = HTTP header value (e.g. "text/html")
388 * Returns : JB_ERR_OK on success
389 * JB_ERR_MEMORY on out-of-memory error.
390 * On error, the_list will be unchanged.
391 * "Success" does not indicate whether or not the
392 * header was already in the list.
394 *********************************************************************/
395 jb_err enlist_unique_header(struct list *the_list, const char *name,
398 jb_err result = JB_ERR_MEMORY;
403 assert(list_is_valid(the_list));
407 /* + 2 for the ': ', + 1 for the \0 */
408 header_size = strlen(name) + 2 + strlen(value) + 1;
409 header = (char *)malloc(header_size);
413 const size_t bytes_to_compare = strlen(name) + 2;
416 snprintf(header, header_size, "%s: %s", name, value);
418 * The trailing "\r\n" is added by list_to_text(),
419 * if the caller passed them anyway, cut the header
420 * at the first one or dump core if this is a debug
425 if ((*p == '\r') || (*p == '\n'))
432 result = enlist_unique(the_list, header, bytes_to_compare);
434 assert(list_is_valid(the_list));
442 /*********************************************************************
444 * Function : list_remove_all
446 * Description : Remove all entries from a list. On return, the_list
447 * is a valid, empty list. Note that this is similar
448 * to destroy_list(), but the difference is that this
449 * function guarantees that the list structure is still
450 * valid after the call.
453 * 1 : the_list = pointer to list
457 *********************************************************************/
458 void list_remove_all(struct list *the_list)
460 struct list_entry *cur_entry;
461 struct list_entry *next_entry;
464 assert(list_is_valid(the_list));
466 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
468 next_entry = cur_entry->next;
469 freez(cur_entry->str);
473 the_list->first = the_list->last = NULL;
475 assert(list_is_valid(the_list));
479 /*********************************************************************
481 * Function : list_to_text
483 * Description : "Flatten" a string list into 1 long \r\n delimited string,
484 * adding an empty line at the end. NULL entries are ignored.
485 * This function does not change the_list.
487 * XXX: Should probably be renamed as it's only
488 * useful (and used) to flatten header lists.
491 * 1 : the_list = pointer to list
493 * Returns : NULL on malloc error, else new long string.
494 * Caller must free() it.
496 *********************************************************************/
497 char *list_to_text(const struct list *the_list)
499 struct list_entry *cur_entry;
506 assert(list_is_valid(the_list));
509 * Calculate the length of the final text.
510 * '2' because of the '\r\n' at the end of
511 * each string and at the end of the text.
514 for (cur_entry = the_list->first; cur_entry; cur_entry = cur_entry->next)
518 text_length += strlen(cur_entry->str) + 2;
522 bytes_left = text_length + 1;
524 text = (char *)malloc(bytes_left);
532 for (cur_entry = the_list->first; cur_entry; cur_entry = cur_entry->next)
536 const int written = snprintf(cursor, bytes_left, "%s\r\n", cur_entry->str);
539 assert(written < bytes_left);
541 bytes_left -= (size_t)written;
542 cursor += (size_t)written;
546 assert(bytes_left == 3);
552 assert(text_length == cursor - text);
553 assert(text[text_length] == '\0');
559 /*********************************************************************
561 * Function : list_remove_item
563 * Description : Remove a string from a specified string list.
566 * 1 : the_list = pointer to list
567 * 2 : str = string to remove from the list - non-NULL
569 * Returns : Number of times it was removed.
571 *********************************************************************/
572 int list_remove_item(struct list *the_list, const char *str)
574 struct list_entry *prev = NULL;
575 struct list_entry *cur;
576 struct list_entry *next;
580 assert(list_is_valid(the_list));
583 cur = the_list->first;
589 if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
599 the_list->first = next;
601 free((char *)cur->str);
611 the_list->last = prev;
613 assert(list_is_valid(the_list));
619 /*********************************************************************
621 * Function : list_remove_list
623 * Description : Remove all strings in one list from another list.
624 * This is currently a brute-force algorithm
625 * (it compares every pair of strings).
628 * 1 : dest = list to change
629 * 2 : src = list of strings to remove
631 * Returns : Total number of strings removed.
633 *********************************************************************/
634 int list_remove_list(struct list *dest, const struct list *src)
636 struct list_entry *cur;
641 assert(list_is_valid(src));
642 assert(list_is_valid(dest));
644 for (cur = src->first; cur != NULL; cur = cur->next)
646 if (cur->str != NULL)
648 count += list_remove_item(dest, cur->str);
652 assert(list_is_valid(src));
653 assert(list_is_valid(dest));
659 /*********************************************************************
661 * Function : list_duplicate
663 * Description : Copy a string list
666 * 1 : dest = Destination list. Must be a valid list.
667 * All existing entries will be removed.
668 * 1 : src = pointer to source list for copy.
670 * Returns : JB_ERR_OK on success
671 * JB_ERR_MEMORY on out-of-memory error.
672 * On error, dest will be empty.
674 *********************************************************************/
675 jb_err list_duplicate(struct list *dest, const struct list *src)
677 struct list_entry * cur_src;
678 struct list_entry * cur_dest;
682 assert(list_is_valid(src));
683 assert(list_is_valid(dest));
685 list_remove_all(dest);
687 /* Need to process first entry specially so we can set dest->first */
688 cur_src = src->first;
691 cur_dest = dest->first = (struct list_entry *)zalloc(sizeof(*cur_dest));
692 if (cur_dest == NULL)
696 assert(list_is_valid(src));
697 assert(list_is_valid(dest));
699 return JB_ERR_MEMORY;
704 cur_dest->str = strdup(cur_src->str);
705 if (cur_dest->str == NULL)
709 assert(list_is_valid(src));
710 assert(list_is_valid(dest));
712 return JB_ERR_MEMORY;
715 /* else { cur_dest->str = NULL; } - implied by zalloc */
717 /* Now process the rest */
718 for (cur_src = cur_src->next; cur_src; cur_src = cur_src->next)
720 cur_dest = cur_dest->next = (struct list_entry *)zalloc(sizeof(*cur_dest));
721 if (cur_dest == NULL)
725 assert(list_is_valid(src));
726 assert(list_is_valid(dest));
728 return JB_ERR_MEMORY;
732 cur_dest->str = strdup(cur_src->str);
733 if (cur_dest->str == NULL)
737 assert(list_is_valid(src));
738 assert(list_is_valid(dest));
740 return JB_ERR_MEMORY;
743 /* else { cur_dest->str = NULL; } - implied by zalloc */
746 dest->last = cur_dest;
749 assert(list_is_valid(src));
750 assert(list_is_valid(dest));
756 /*********************************************************************
758 * Function : list_append_list_unique
760 * Description : Append a string list to another list.
761 * Duplicate items are not added.
764 * 1 : dest = pointer to destination list for merge.
765 * 2 : src = pointer to source for merge.
767 * Returns : JB_ERR_OK on success
768 * JB_ERR_MEMORY on out-of-memory error.
769 * On error, some (but not all) of src might have
770 * been copied into dest.
772 *********************************************************************/
773 jb_err list_append_list_unique(struct list *dest, const struct list *src)
775 struct list_entry * cur;
779 assert(list_is_valid(src));
780 assert(list_is_valid(dest));
782 for (cur = src->first; cur; cur = cur->next)
786 if (enlist_unique(dest, cur->str, 0))
788 assert(list_is_valid(src));
789 assert(list_is_valid(dest));
791 return JB_ERR_MEMORY;
796 assert(list_is_valid(src));
797 assert(list_is_valid(dest));
803 /*********************************************************************
805 * Function : list_is_empty
807 * Description : Test whether a list is empty. Does not change the list.
810 * 1 : the_list = pointer to list to test.
812 * Returns : Nonzero if the list contains no entries.
814 *********************************************************************/
815 int list_is_empty(const struct list *the_list)
818 assert(list_is_valid(the_list));
820 return (the_list->first == NULL);
824 /*********************************************************************
826 * Function : list_contains_item
828 * Description : Tests whether a list item is already set.
829 * Does not change the list.
832 * 1 : the_list = list to search in
833 * 2 : str = string to search for
835 * Returns : TRUE if the item was found,
838 *********************************************************************/
839 int list_contains_item(const struct list *the_list, const char *str)
841 struct list_entry *entry;
844 assert(list_is_valid(the_list));
847 for (entry = the_list->first; entry != NULL; entry = entry->next)
849 if (entry->str == NULL)
852 * NULL pointers are allowed in some lists.
853 * For example for csp->headers in case a
854 * header was removed.
859 if (0 == strcmp(str, entry->str))
870 /*********************************************************************
874 * Description : Create a new, empty map.
875 * Causes program exit if the memory allocation fails.
879 * Returns : A new, empty map
881 *********************************************************************/
882 struct map *new_map(void)
884 struct map *empty_map = zalloc(sizeof(struct map));
886 if (NULL == empty_map)
896 /*********************************************************************
898 * Function : free_map
900 * Description : Free the memory occupied by a map and its
904 * 1 : the_map = map to be freed. May be NULL.
908 *********************************************************************/
909 void free_map(struct map *the_map)
911 struct map_entry *cur_entry;
912 struct map_entry *next_entry;
919 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = next_entry)
921 freez(cur_entry->name);
922 freez(cur_entry->value);
924 next_entry = cur_entry->next;
928 the_map->first = the_map->last = NULL;
934 /*********************************************************************
938 * Description : Add a mapping from given name to given value to a
941 * Note: Since all strings will be free()d in free_map()
942 * later, set the copy flags for constants or
943 * strings that will be independently free()d.
945 * Note2: This function allows NULL parameters - it
946 * returns JB_ERR_MEMORY in that case.
948 * Note3: If this function returns JB_ERR_MEMORY,
949 * it will free(name) unless you specify
950 * name_needs_copying, and similarly it will
951 * free(value) unless you specify
952 * value_needs_copying.
954 * Due to Note2 and Note3 above, the following code
955 * is legal, and will never crash or leak memory even
956 * if the system runs out of memory:
958 * err = map(mymap, "xyz", 1, html_encode(somestring), 0);
960 * err will be set to JB_ERR_MEMORY if either call runs
961 * out-of-memory. Without these features, you would
962 * need to check the return value of html_encode in the
963 * above example for NULL, which (at least) doubles the
964 * amount of error-checking code needed.
967 * 1 : the_map = map to add to
968 * 2 : name = name to add
969 * 3 : name_needs_copying = flag set if a copy of name should be used
970 * 4 : value = value to add
971 * 5 : value_needs_copying = flag set if a copy of value should be used
973 * Returns : JB_ERR_OK on success
974 * JB_ERR_MEMORY on out-of-memory error.
976 *********************************************************************/
977 jb_err map(struct map *the_map,
978 const char *name, int name_needs_copying,
979 const char *value, int value_needs_copying)
981 struct map_entry *new_entry;
987 || (NULL == (new_entry = zalloc(sizeof(*new_entry)))))
989 if ((name != NULL) && (!name_needs_copying))
993 if ((value != NULL) && (!value_needs_copying))
997 return JB_ERR_MEMORY;
1000 if (name_needs_copying)
1002 if (NULL == (name = strdup(name)))
1005 if (!value_needs_copying)
1007 free((char *)value);
1009 return JB_ERR_MEMORY;
1013 if (value_needs_copying)
1015 if (NULL == (value = strdup(value)))
1019 return JB_ERR_MEMORY;
1023 new_entry->name = name;
1024 new_entry->value = value;
1025 /* new_entry->next = NULL; - implied by zalloc */
1029 the_map->last->next = new_entry;
1030 the_map->last = new_entry;
1034 the_map->first = new_entry;
1035 the_map->last = new_entry;
1042 /*********************************************************************
1046 * Description : Remove all map_entry structs with a given name from
1050 * 1 : the_map = map to look in
1051 * 2 : name = name to unmap
1053 * Returns : JB_ERR_OK
1055 *********************************************************************/
1056 jb_err unmap(struct map *the_map, const char *name)
1058 struct map_entry *cur_entry, *last_entry;
1065 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
1067 if (!strcmp(name, cur_entry->name))
1070 * Update the incoming pointer
1072 if (cur_entry == the_map->first)
1074 the_map->first = cur_entry->next;
1078 last_entry->next = cur_entry->next;
1082 * Update the map's last pointer
1084 if (cur_entry == the_map->last)
1086 the_map->last = last_entry;
1090 * Free the map_entry
1092 freez(cur_entry->name);
1093 freez(cur_entry->value);
1095 if (last_entry == NULL)
1097 /* The map only had a single entry which has just been removed. */
1100 cur_entry = last_entry;
1104 last_entry = cur_entry;
1111 /*********************************************************************
1115 * Description : Look up an item with a given name in a map, and
1119 * 1 : the_map = map to look in
1120 * 2 : name = name parameter to look for
1122 * Returns : the value if found, else the empty string.
1123 * Return value is allocated as part of the map, so
1124 * it is freed when the map is destroyed. Caller
1125 * must not free or modify it.
1127 *********************************************************************/
1128 const char *lookup(const struct map *the_map, const char *name)
1130 const struct map_entry *cur_entry;
1135 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
1137 if (!strcmp(name, cur_entry->name))
1139 return cur_entry->value;