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>
59 static int list_is_valid (const struct list *the_list);
62 /*********************************************************************
64 * Function : init_list
66 * Description : Create a new, empty list in user-allocated memory.
67 * Caller should allocate a "struct list" variable,
68 * then pass it to this function.
69 * (Implementation note: Rather than calling this
70 * function, you can also just memset the memory to
71 * zero, e.g. if you have a larger structure you
72 * want to initialize quickly. However, that isn't
73 * really good design.)
76 * 1 : the_list = pointer to list
80 *********************************************************************/
81 void init_list(struct list *the_list)
83 memset(the_list, '\0', sizeof(*the_list));
87 /*********************************************************************
89 * Function : destroy_list
91 * Description : Destroy a string list (opposite of list_init).
92 * On return, the memory used by the list entries has
93 * been freed, but not the memory used by the_list
94 * itself. You should not re-use the_list without
95 * calling list_init().
97 * (Implementation note: You *can* reuse the_list
98 * without calling list_init(), but please don't.
99 * If you want to remove all entries from a list
100 * and still have a usable list, then use
101 * list_remove_all().)
104 * 1 : the_list = pointer to list
108 *********************************************************************/
109 void destroy_list (struct list *the_list)
111 struct list_entry *cur_entry, *next_entry;
115 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
117 next_entry = cur_entry->next;
118 freez(cur_entry->str);
122 the_list->first = NULL;
123 the_list->last = NULL;
128 /*********************************************************************
130 * Function : list_is_valid
132 * Description : Check that a string list is valid. The intended
133 * usage is "assert(list_is_valid(the_list))".
134 * Currently this checks that "the_list->last"
135 * is correct, and that the list doesn't contain
136 * circular references. It is likely to crash if
137 * it's passed complete garbage.
140 * 1 : the_list = pointer to list. Must be non-null.
142 * Returns : 1 if list is valid, 0 otherwise.
144 *********************************************************************/
145 static int list_is_valid (const struct list *the_list)
147 const struct list_entry *cur_entry;
148 const struct list_entry *last_entry = NULL;
153 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
155 last_entry = cur_entry;
160 * Just check that this string can be accessed - i.e. it's a valid
163 (void)strlen(cur_entry->str);
167 * Check for looping back to first
169 if ((entry++ != 0) && (cur_entry == the_list->first))
175 * Arbitrarily limit list length to prevent infinite loops.
176 * Note that the 1000 limit was hit by a real user in tracker 911950;
177 * removing it for now. Real circular references should eventually
178 * be caught by the check above, anyway.
188 * Check this isn't marked as the last entry, unless of course it's
189 * *really* the last entry.
191 if ((the_list->last == cur_entry) && (cur_entry->next != NULL))
193 /* This is the last entry, but there's data after it !!?? */
198 return (the_list->last == last_entry);
201 #endif /* ndef NDEBUG */
204 /*********************************************************************
208 * Description : Append a string into a specified string list.
211 * 1 : the_list = pointer to list
212 * 2 : str = string to add to the list (maybe NULL)
214 * Returns : JB_ERR_OK on success
215 * JB_ERR_MEMORY on out-of-memory error.
216 * On error, the_list will be unchanged.
218 *********************************************************************/
219 jb_err enlist(struct list *the_list, const char *str)
221 struct list_entry *cur;
224 assert(list_is_valid(the_list));
226 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
228 return JB_ERR_MEMORY;
233 if (NULL == (cur->str = strdup(str)))
236 return JB_ERR_MEMORY;
239 /* else { cur->str = NULL; } - implied by zalloc */
241 /* cur->next = NULL; - implied by zalloc */
245 the_list->last->next = cur;
246 the_list->last = cur;
250 the_list->first = cur;
251 the_list->last = cur;
254 assert(list_is_valid(the_list));
259 /*********************************************************************
261 * Function : enlist_first
263 * Description : Append a string as first element into a specified
267 * 1 : the_list = pointer to list
268 * 2 : str = string to add to the list (maybe NULL)
270 * Returns : JB_ERR_OK on success
271 * JB_ERR_MEMORY on out-of-memory error.
272 * On error, the_list will be unchanged.
274 *********************************************************************/
275 jb_err enlist_first(struct list *the_list, const char *str)
277 struct list_entry *cur;
280 assert(list_is_valid(the_list));
282 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
284 return JB_ERR_MEMORY;
289 if (NULL == (cur->str = strdup(str)))
292 return JB_ERR_MEMORY;
295 /* else { cur->str = NULL; } - implied by zalloc */
297 cur->next = the_list->first;
299 the_list->first = cur;
300 if (the_list->last == NULL)
302 the_list->last = cur;
305 assert(list_is_valid(the_list));
310 /*********************************************************************
312 * Function : enlist_unique
314 * Description : Append a string into a specified string list,
315 * if & only if it's not there already.
316 * If the num_significant_chars argument is nonzero,
317 * only compare up to the nth character.
320 * 1 : the_list = pointer to list
321 * 2 : str = string to add to the list
322 * 3 : num_significant_chars = number of chars to use
323 * for uniqueness test, or 0 to require an exact match.
325 * Returns : JB_ERR_OK on success
326 * JB_ERR_MEMORY on out-of-memory error.
327 * On error, the_list will be unchanged.
328 * "Success" does not indicate whether or not the
329 * item was already in the list.
331 *********************************************************************/
332 jb_err enlist_unique(struct list *the_list, const char *str,
333 size_t num_significant_chars)
335 struct list_entry *cur_entry;
338 assert(list_is_valid(the_list));
340 assert(num_significant_chars >= 0);
341 assert(num_significant_chars <= strlen(str));
343 if (num_significant_chars > 0)
345 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
347 if ((cur_entry->str != NULL)
348 && (0 == strncmp(str, cur_entry->str, num_significant_chars)))
357 /* Test whole string */
358 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
360 if ((cur_entry->str != NULL) && (0 == strcmp(str, cur_entry->str)))
368 return enlist(the_list, str);
372 /*********************************************************************
374 * Function : enlist_unique_header
376 * Description : Make a HTTP header from the two strings name and value,
377 * and append the result into a specified string list,
378 * if & only if there isn't already a header with that name.
381 * 1 : the_list = pointer to list
382 * 2 : name = HTTP header name (e.g. "Content-type")
383 * 3 : value = HTTP header value (e.g. "text/html")
385 * Returns : JB_ERR_OK on success
386 * JB_ERR_MEMORY on out-of-memory error.
387 * On error, the_list will be unchanged.
388 * "Success" does not indicate whether or not the
389 * header was already in the list.
391 *********************************************************************/
392 jb_err enlist_unique_header(struct list *the_list, const char *name,
395 jb_err result = JB_ERR_MEMORY;
400 assert(list_is_valid(the_list));
404 /* + 2 for the ': ', + 1 for the \0 */
405 header_size = strlen(name) + 2 + strlen(value) + 1;
406 header = (char *)malloc(header_size);
410 const size_t bytes_to_compare = strlen(name) + 2;
413 snprintf(header, header_size, "%s: %s", name, value);
415 * The trailing "\r\n" is added by list_to_text(),
416 * if the caller passed them anyway, cut the header
417 * at the first one or dump core if this is a debug
422 if ((*p == '\r') || (*p == '\n'))
429 result = enlist_unique(the_list, header, bytes_to_compare);
431 assert(list_is_valid(the_list));
439 /*********************************************************************
441 * Function : list_remove_all
443 * Description : Remove all entries from a list. On return, the_list
444 * is a valid, empty list. Note that this is similar
445 * to destroy_list(), but the difference is that this
446 * function guarantees that the list structure is still
447 * valid after the call.
450 * 1 : the_list = pointer to list
454 *********************************************************************/
455 void list_remove_all(struct list *the_list)
457 struct list_entry *cur_entry;
458 struct list_entry *next_entry;
461 assert(list_is_valid(the_list));
463 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
465 next_entry = cur_entry->next;
466 freez(cur_entry->str);
470 the_list->first = the_list->last = NULL;
472 assert(list_is_valid(the_list));
476 /*********************************************************************
478 * Function : list_to_text
480 * Description : "Flatten" a string list into 1 long \r\n delimited string,
481 * adding an empty line at the end. NULL entries are ignored.
482 * This function does not change the_list.
484 * XXX: Should probably be renamed as it's only
485 * useful (and used) to flatten header lists.
488 * 1 : the_list = pointer to list
490 * Returns : NULL on malloc error, else new long string.
491 * Caller must free() it.
493 *********************************************************************/
494 char *list_to_text(const struct list *the_list)
496 struct list_entry *cur_entry;
503 assert(list_is_valid(the_list));
506 * Calculate the length of the final text.
507 * '2' because of the '\r\n' at the end of
508 * each string and at the end of the text.
511 for (cur_entry = the_list->first; cur_entry; cur_entry = cur_entry->next)
515 text_length += strlen(cur_entry->str) + 2;
519 bytes_left = text_length + 1;
521 text = (char *)malloc(bytes_left);
529 for (cur_entry = the_list->first; cur_entry; cur_entry = cur_entry->next)
533 const int written = snprintf(cursor, bytes_left, "%s\r\n", cur_entry->str);
536 assert(written < bytes_left);
538 bytes_left -= (size_t)written;
539 cursor += (size_t)written;
543 assert(bytes_left == 3);
549 assert(text_length == cursor - text);
550 assert(text[text_length] == '\0');
556 /*********************************************************************
558 * Function : list_remove_item
560 * Description : Remove a string from a specified string list.
563 * 1 : the_list = pointer to list
564 * 2 : str = string to remove from the list - non-NULL
566 * Returns : Number of times it was removed.
568 *********************************************************************/
569 int list_remove_item(struct list *the_list, const char *str)
571 struct list_entry *prev = NULL;
572 struct list_entry *cur;
573 struct list_entry *next;
577 assert(list_is_valid(the_list));
580 cur = the_list->first;
586 if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
596 the_list->first = next;
598 free((char *)cur->str);
608 the_list->last = prev;
610 assert(list_is_valid(the_list));
616 /*********************************************************************
618 * Function : list_remove_list
620 * Description : Remove all strings in one list from another list.
621 * This is currently a brute-force algorithm
622 * (it compares every pair of strings).
625 * 1 : dest = list to change
626 * 2 : src = list of strings to remove
628 * Returns : Total number of strings removed.
630 *********************************************************************/
631 int list_remove_list(struct list *dest, const struct list *src)
633 struct list_entry *cur;
638 assert(list_is_valid(src));
639 assert(list_is_valid(dest));
641 for (cur = src->first; cur != NULL; cur = cur->next)
643 if (cur->str != NULL)
645 count += list_remove_item(dest, cur->str);
649 assert(list_is_valid(src));
650 assert(list_is_valid(dest));
656 /*********************************************************************
658 * Function : list_duplicate
660 * Description : Copy a string list
663 * 1 : dest = Destination list. Must be a valid list.
664 * All existing entries will be removed.
665 * 1 : src = pointer to source list for copy.
667 * Returns : JB_ERR_OK on success
668 * JB_ERR_MEMORY on out-of-memory error.
669 * On error, dest will be empty.
671 *********************************************************************/
672 jb_err list_duplicate(struct list *dest, const struct list *src)
674 struct list_entry * cur_src;
675 struct list_entry * cur_dest;
679 assert(list_is_valid(src));
680 assert(list_is_valid(dest));
682 list_remove_all(dest);
684 /* Need to process first entry specially so we can set dest->first */
685 cur_src = src->first;
688 cur_dest = dest->first = (struct list_entry *)zalloc(sizeof(*cur_dest));
689 if (cur_dest == NULL)
693 assert(list_is_valid(src));
694 assert(list_is_valid(dest));
696 return JB_ERR_MEMORY;
701 cur_dest->str = strdup(cur_src->str);
702 if (cur_dest->str == NULL)
706 assert(list_is_valid(src));
707 assert(list_is_valid(dest));
709 return JB_ERR_MEMORY;
712 /* else { cur_dest->str = NULL; } - implied by zalloc */
714 /* Now process the rest */
715 for (cur_src = cur_src->next; cur_src; cur_src = cur_src->next)
717 cur_dest = cur_dest->next = (struct list_entry *)zalloc(sizeof(*cur_dest));
718 if (cur_dest == NULL)
722 assert(list_is_valid(src));
723 assert(list_is_valid(dest));
725 return JB_ERR_MEMORY;
729 cur_dest->str = strdup(cur_src->str);
730 if (cur_dest->str == NULL)
734 assert(list_is_valid(src));
735 assert(list_is_valid(dest));
737 return JB_ERR_MEMORY;
740 /* else { cur_dest->str = NULL; } - implied by zalloc */
743 dest->last = cur_dest;
746 assert(list_is_valid(src));
747 assert(list_is_valid(dest));
753 /*********************************************************************
755 * Function : list_append_list_unique
757 * Description : Append a string list to another list.
758 * Duplicate items are not added.
761 * 1 : dest = pointer to destination list for merge.
762 * 2 : src = pointer to source for merge.
764 * Returns : JB_ERR_OK on success
765 * JB_ERR_MEMORY on out-of-memory error.
766 * On error, some (but not all) of src might have
767 * been copied into dest.
769 *********************************************************************/
770 jb_err list_append_list_unique(struct list *dest, const struct list *src)
772 struct list_entry * cur;
776 assert(list_is_valid(src));
777 assert(list_is_valid(dest));
779 for (cur = src->first; cur; cur = cur->next)
783 if (enlist_unique(dest, cur->str, 0))
785 assert(list_is_valid(src));
786 assert(list_is_valid(dest));
788 return JB_ERR_MEMORY;
793 assert(list_is_valid(src));
794 assert(list_is_valid(dest));
800 /*********************************************************************
802 * Function : list_is_empty
804 * Description : Test whether a list is empty. Does not change the list.
807 * 1 : the_list = pointer to list to test.
809 * Returns : Nonzero if the list contains no entries.
811 *********************************************************************/
812 int list_is_empty(const struct list *the_list)
815 assert(list_is_valid(the_list));
817 return (the_list->first == NULL);
821 /*********************************************************************
823 * Function : list_contains_item
825 * Description : Tests whether a list item is already set.
826 * Does not change the list.
829 * 1 : the_list = list to search in
830 * 2 : str = string to search for
832 * Returns : TRUE if the item was found,
835 *********************************************************************/
836 int list_contains_item(const struct list *the_list, const char *str)
838 struct list_entry *entry;
841 assert(list_is_valid(the_list));
844 for (entry = the_list->first; entry != NULL; entry = entry->next)
846 if (entry->str == NULL)
849 * NULL pointers are allowed in some lists.
850 * For example for csp->headers in case a
851 * header was removed.
856 if (0 == strcmp(str, entry->str))
867 /*********************************************************************
871 * Description : Create a new, empty map.
872 * Causes program exit if the memory allocation fails.
876 * Returns : A new, empty map
878 *********************************************************************/
879 struct map *new_map(void)
881 struct map *empty_map = zalloc(sizeof(struct map));
883 if (NULL == empty_map)
893 /*********************************************************************
895 * Function : free_map
897 * Description : Free the memory occupied by a map and its
901 * 1 : the_map = map to be freed. May be NULL.
905 *********************************************************************/
906 void free_map(struct map *the_map)
908 struct map_entry *cur_entry;
909 struct map_entry *next_entry;
916 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = next_entry)
918 freez(cur_entry->name);
919 freez(cur_entry->value);
921 next_entry = cur_entry->next;
925 the_map->first = the_map->last = NULL;
931 /*********************************************************************
935 * Description : Add a mapping from given name to given value to a
938 * Note: Since all strings will be free()d in free_map()
939 * later, set the copy flags for constants or
940 * strings that will be independently free()d.
942 * Note2: This function allows NULL parameters - it
943 * returns JB_ERR_MEMORY in that case.
945 * Note3: If this function returns JB_ERR_MEMORY,
946 * it will free(name) unless you specify
947 * name_needs_copying, and similarly it will
948 * free(value) unless you specify
949 * value_needs_copying.
951 * Due to Note2 and Note3 above, the following code
952 * is legal, and will never crash or leak memory even
953 * if the system runs out of memory:
955 * err = map(mymap, "xyz", 1, html_encode(somestring), 0);
957 * err will be set to JB_ERR_MEMORY if either call runs
958 * out-of-memory. Without these features, you would
959 * need to check the return value of html_encode in the
960 * above example for NULL, which (at least) doubles the
961 * amount of error-checking code needed.
964 * 1 : the_map = map to add to
965 * 2 : name = name to add
966 * 3 : name_needs_copying = flag set if a copy of name should be used
967 * 4 : value = value to add
968 * 5 : value_needs_copying = flag set if a copy of value should be used
970 * Returns : JB_ERR_OK on success
971 * JB_ERR_MEMORY on out-of-memory error.
973 *********************************************************************/
974 jb_err map(struct map *the_map,
975 const char *name, int name_needs_copying,
976 const char *value, int value_needs_copying)
978 struct map_entry *new_entry;
984 || (NULL == (new_entry = zalloc(sizeof(*new_entry)))))
986 if ((name != NULL) && (!name_needs_copying))
990 if ((value != NULL) && (!value_needs_copying))
994 return JB_ERR_MEMORY;
997 if (name_needs_copying)
999 if (NULL == (name = strdup(name)))
1002 if (!value_needs_copying)
1004 free((char *)value);
1006 return JB_ERR_MEMORY;
1010 if (value_needs_copying)
1012 if (NULL == (value = strdup(value)))
1016 return JB_ERR_MEMORY;
1020 new_entry->name = name;
1021 new_entry->value = value;
1022 /* new_entry->next = NULL; - implied by zalloc */
1026 the_map->last->next = new_entry;
1027 the_map->last = new_entry;
1031 the_map->first = new_entry;
1032 the_map->last = new_entry;
1039 /*********************************************************************
1043 * Description : Remove all map_entry structs with a given name from
1047 * 1 : the_map = map to look in
1048 * 2 : name = name to unmap
1050 * Returns : JB_ERR_OK
1052 *********************************************************************/
1053 jb_err unmap(struct map *the_map, const char *name)
1055 struct map_entry *cur_entry, *last_entry;
1062 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
1064 if (!strcmp(name, cur_entry->name))
1067 * Update the incoming pointer
1069 if (cur_entry == the_map->first)
1071 the_map->first = cur_entry->next;
1075 last_entry->next = cur_entry->next;
1079 * Update the map's last pointer
1081 if (cur_entry == the_map->last)
1083 the_map->last = last_entry;
1087 * Free the map_entry
1089 freez(cur_entry->name);
1090 freez(cur_entry->value);
1092 if (last_entry == NULL)
1094 /* The map only had a single entry which has just been removed. */
1097 cur_entry = last_entry;
1101 last_entry = cur_entry;
1108 /*********************************************************************
1112 * Description : Look up an item with a given name in a map, and
1116 * 1 : the_map = map to look in
1117 * 2 : name = name parameter to look for
1119 * Returns : the value if found, else the empty string.
1120 * Return value is allocated as part of the map, so
1121 * it is freed when the map is destroyed. Caller
1122 * must not free or modify it.
1124 *********************************************************************/
1125 const char *lookup(const struct map *the_map, const char *name)
1127 const struct map_entry *cur_entry;
1132 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
1134 if (!strcmp(name, cur_entry->name))
1136 return cur_entry->value;