1 const char list_rcs[] = "$Id: list.c,v 1.25 2011/09/04 11:10:56 fabiankeil Exp $";
2 /*********************************************************************
4 * File : $Source: /cvsroot/ijbswa/current/list.c,v $
6 * Purpose : Declares functions to handle lists.
8 * Copyright : Written by and Copyright (C) 2001-2007 the SourceForge
9 * Privoxy team. http://www.privoxy.org/
11 * Based on the Internet Junkbuster originally written
12 * by and Copyright (C) 1997 Anonymous Coders and
13 * Junkbusters Corporation. http://www.junkbusters.com
15 * This program is free software; you can redistribute it
16 * and/or modify it under the terms of the GNU General
17 * Public License as published by the Free Software
18 * Foundation; either version 2 of the License, or (at
19 * your option) any later version.
21 * This program is distributed in the hope that it will
22 * be useful, but WITHOUT ANY WARRANTY; without even the
23 * implied warranty of MERCHANTABILITY or FITNESS FOR A
24 * PARTICULAR PURPOSE. See the GNU General Public
25 * License for more details.
27 * The GNU General Public License should be included with
28 * this file. If not, you can view it at
29 * http://www.gnu.org/copyleft/gpl.html
30 * or write to the Free Software Foundation, Inc., 59
31 * Temple Place - Suite 330, Boston, MA 02111-1307, USA.
33 *********************************************************************/
39 /* FIXME: The following headers are not needed for Win32. Are they
40 * needed on other platforms?
43 #include <sys/types.h>
49 #if !defined(_WIN32) && !defined(__OS2__)
59 const char list_h_rcs[] = LIST_H_VERSION;
62 static int list_is_valid (const struct list *the_list);
65 /*********************************************************************
67 * Function : init_list
69 * Description : Create a new, empty list in user-allocated memory.
70 * Caller should allocate a "struct list" variable,
71 * then pass it to this function.
72 * (Implementation note: Rather than calling this
73 * function, you can also just memset the memory to
74 * zero, e.g. if you have a larger structure you
75 * want to initialize quickly. However, that isn't
76 * really good design.)
79 * 1 : the_list = pointer to list
83 *********************************************************************/
84 void init_list(struct list *the_list)
86 memset(the_list, '\0', sizeof(*the_list));
90 /*********************************************************************
92 * Function : destroy_list
94 * Description : Destroy a string list (opposite of list_init).
95 * On return, the memory used by the list entries has
96 * been freed, but not the memory used by the_list
97 * itself. You should not re-use the_list without
98 * calling list_init().
100 * (Implementation note: You *can* reuse the_list
101 * without calling list_init(), but please don't.
102 * If you want to remove all entries from a list
103 * and still have a usable list, then use
104 * list_remove_all().)
107 * 1 : the_list = pointer to list
111 *********************************************************************/
112 void destroy_list (struct list *the_list)
114 struct list_entry *cur_entry, *next_entry;
118 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
120 next_entry = cur_entry->next;
121 freez(cur_entry->str);
125 the_list->first = NULL;
126 the_list->last = NULL;
130 /*********************************************************************
132 * Function : list_is_valid
134 * Description : Check that a string list is valid. The intended
135 * usage is "assert(list_is_valid(the_list))".
136 * Currently this checks that "the_list->last"
137 * is correct, and that the list dosn't contain
138 * circular references. It is likely to crash if
139 * it's passed complete garbage.
142 * 1 : the_list = pointer to list. Must be non-null.
144 * Returns : 1 if list is valid, 0 otherwise.
146 *********************************************************************/
147 static int list_is_valid (const struct list *the_list)
150 * If you don't want this check, just change the line below
151 * from "#if 1" to "#if 0".
154 const struct list_entry *cur_entry;
155 const struct list_entry *last_entry = NULL;
160 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
162 last_entry = cur_entry;
167 * Just check that this string can be accessed - i.e. it's a valid
170 (void)strlen(cur_entry->str);
174 * Check for looping back to first
176 if ((entry++ != 0) && (cur_entry == the_list->first))
182 * Arbitrarily limit list length to prevent infinite loops.
183 * Note that the 1000 limit was hit by a real user in tracker 911950;
184 * removing it for now. Real circular references should eventually
185 * be caught by the check above, anyway.
195 * Check this isn't marked as the last entry, unless of course it's
196 * *really* the last entry.
198 if ((the_list->last == cur_entry) && (cur_entry->next != NULL))
200 /* This is the last entry, but there's data after it !!?? */
205 return (the_list->last == last_entry);
211 /*********************************************************************
215 * Description : Append a string into a specified string list.
218 * 1 : the_list = pointer to list
219 * 2 : str = string to add to the list (maybe NULL)
221 * Returns : JB_ERR_OK on success
222 * JB_ERR_MEMORY on out-of-memory error.
223 * On error, the_list will be unchanged.
225 *********************************************************************/
226 jb_err enlist(struct list *the_list, const char *str)
228 struct list_entry *cur;
231 assert(list_is_valid(the_list));
233 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
235 return JB_ERR_MEMORY;
240 if (NULL == (cur->str = strdup(str)))
243 return JB_ERR_MEMORY;
246 /* else { cur->str = NULL; } - implied by zalloc */
248 /* cur->next = NULL; - implied by zalloc */
252 the_list->last->next = cur;
253 the_list->last = cur;
257 the_list->first = cur;
258 the_list->last = cur;
261 assert(list_is_valid(the_list));
266 /*********************************************************************
268 * Function : enlist_first
270 * Description : Append a string as first element into a specified
274 * 1 : the_list = pointer to list
275 * 2 : str = string to add to the list (maybe NULL)
277 * Returns : JB_ERR_OK on success
278 * JB_ERR_MEMORY on out-of-memory error.
279 * On error, the_list will be unchanged.
281 *********************************************************************/
282 jb_err enlist_first(struct list *the_list, const char *str)
284 struct list_entry *cur;
287 assert(list_is_valid(the_list));
289 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
291 return JB_ERR_MEMORY;
296 if (NULL == (cur->str = strdup(str)))
299 return JB_ERR_MEMORY;
302 /* else { cur->str = NULL; } - implied by zalloc */
304 cur->next = the_list->first;
306 the_list->first = cur;
307 if (the_list->last == NULL)
309 the_list->last = cur;
312 assert(list_is_valid(the_list));
317 /*********************************************************************
319 * Function : enlist_unique
321 * Description : Append a string into a specified string list,
322 * if & only if it's not there already.
323 * If the num_significant_chars argument is nonzero,
324 * only compare up to the nth character.
327 * 1 : the_list = pointer to list
328 * 2 : str = string to add to the list
329 * 3 : num_significant_chars = number of chars to use
330 * for uniqueness test, or 0 to require an exact match.
332 * Returns : JB_ERR_OK on success
333 * JB_ERR_MEMORY on out-of-memory error.
334 * On error, the_list will be unchanged.
335 * "Success" does not indicate whether or not the
336 * item was already in the list.
338 *********************************************************************/
339 jb_err enlist_unique(struct list *the_list, const char *str,
340 size_t num_significant_chars)
342 struct list_entry *cur_entry;
345 assert(list_is_valid(the_list));
347 assert(num_significant_chars >= 0);
348 assert(num_significant_chars <= strlen(str));
350 if (num_significant_chars > 0)
352 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
354 if ( (cur_entry->str != NULL)
355 && (0 == strncmp(str, cur_entry->str, num_significant_chars)))
364 /* Test whole string */
365 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
367 if ( (cur_entry->str != NULL) && (0 == strcmp(str, cur_entry->str)))
375 return enlist(the_list, str);
379 /*********************************************************************
381 * Function : enlist_unique_header
383 * Description : Make a HTTP header from the two strings name and value,
384 * and append the result into a specified string list,
385 * if & only if there isn't already a header with that name.
388 * 1 : the_list = pointer to list
389 * 2 : name = HTTP header name (e.g. "Content-type")
390 * 3 : value = HTTP header value (e.g. "text/html")
392 * Returns : JB_ERR_OK on success
393 * JB_ERR_MEMORY on out-of-memory error.
394 * On error, the_list will be unchanged.
395 * "Success" does not indicate whether or not the
396 * header was already in the list.
398 *********************************************************************/
399 jb_err enlist_unique_header(struct list *the_list, const char *name,
402 jb_err result = JB_ERR_MEMORY;
407 assert(list_is_valid(the_list));
411 /* + 2 for the ': ', + 1 for the \0 */
412 header_size = strlen(name) + 2 + strlen(value) + 1;
413 header = (char *)malloc(header_size);
417 const size_t bytes_to_compare = strlen(name) + 2;
419 snprintf(header, header_size, "%s: %s", name, value);
420 result = enlist_unique(the_list, header, bytes_to_compare);
422 assert(list_is_valid(the_list));
430 /*********************************************************************
432 * Function : list_remove_all
434 * Description : Remove all entries from a list. On return, the_list
435 * is a valid, empty list. Note that this is similar
436 * to destroy_list(), but the difference is that this
437 * function guarantees that the list structure is still
438 * valid after the call.
441 * 1 : the_list = pointer to list
445 *********************************************************************/
446 void list_remove_all(struct list *the_list)
448 struct list_entry *cur_entry;
449 struct list_entry *next_entry;
452 assert(list_is_valid(the_list));
454 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
456 next_entry = cur_entry->next;
457 freez(cur_entry->str);
461 the_list->first = the_list->last = NULL;
463 assert(list_is_valid(the_list));
467 /*********************************************************************
469 * Function : list_to_text
471 * Description : "Flatten" a string list into 1 long \r\n delimited string,
472 * adding an empty line at the end. NULL entries are ignored.
473 * This function does not change the_list.
475 * XXX: Should probably be renamed as it's only
476 * useful (and used) to flatten header lists.
479 * 1 : the_list = pointer to list
481 * Returns : NULL on malloc error, else new long string.
482 * Caller must free() it.
484 *********************************************************************/
485 char *list_to_text(const struct list *the_list)
487 struct list_entry *cur_entry;
494 assert(list_is_valid(the_list));
497 * Calculate the length of the final text.
498 * '2' because of the '\r\n' at the end of
499 * each string and at the end of the text.
502 for (cur_entry = the_list->first; cur_entry; cur_entry = cur_entry->next)
506 text_length += strlen(cur_entry->str) + 2;
510 bytes_left = text_length + 1;
512 text = (char *)malloc(bytes_left);
520 for (cur_entry = the_list->first; cur_entry; cur_entry = cur_entry->next)
524 const int written = snprintf(cursor, bytes_left, "%s\r\n", cur_entry->str);
527 assert(written < bytes_left);
529 bytes_left -= (size_t)written;
530 cursor += (size_t)written;
534 assert(bytes_left == 3);
540 assert(text_length == cursor - text);
541 assert(text[text_length] == '\0');
547 /*********************************************************************
549 * Function : list_remove_item
551 * Description : Remove a string from a specified string list.
554 * 1 : the_list = pointer to list
555 * 2 : str = string to remove from the list - non-NULL
557 * Returns : Number of times it was removed.
559 *********************************************************************/
560 int list_remove_item(struct list *the_list, const char *str)
562 struct list_entry *prev = NULL;
563 struct list_entry *cur;
564 struct list_entry *next;
568 assert(list_is_valid(the_list));
571 cur = the_list->first;
577 if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
587 the_list->first = next;
589 free((char *)cur->str);
599 the_list->last = prev;
601 assert(list_is_valid(the_list));
607 /*********************************************************************
609 * Function : list_remove_list
611 * Description : Remove all strings in one list from another list.
612 * This is currently a brute-force algorithm
613 * (it compares every pair of strings).
616 * 1 : dest = list to change
617 * 2 : src = list of strings to remove
619 * Returns : Total number of strings removed.
621 *********************************************************************/
622 int list_remove_list(struct list *dest, const struct list *src)
624 struct list_entry *cur;
629 assert(list_is_valid(src));
630 assert(list_is_valid(dest));
632 for (cur = src->first; cur != NULL; cur = cur->next)
634 if (cur->str != NULL)
636 count += list_remove_item(dest, cur->str);
640 assert(list_is_valid(src));
641 assert(list_is_valid(dest));
647 /*********************************************************************
649 * Function : list_duplicate
651 * Description : Copy a string list
654 * 1 : dest = Destination list. Must be a valid list.
655 * All existing entries will be removed.
656 * 1 : src = pointer to source list for copy.
658 * Returns : JB_ERR_OK on success
659 * JB_ERR_MEMORY on out-of-memory error.
660 * On error, dest will be empty.
662 *********************************************************************/
663 jb_err list_duplicate(struct list *dest, const struct list *src)
665 struct list_entry * cur_src;
666 struct list_entry * cur_dest;
670 assert(list_is_valid(src));
671 assert(list_is_valid(dest));
673 list_remove_all(dest);
675 /* Need to process first entry specially so we can set dest->first */
676 cur_src = src->first;
679 cur_dest = dest->first = (struct list_entry *)zalloc(sizeof(*cur_dest));
680 if (cur_dest == NULL)
684 assert(list_is_valid(src));
685 assert(list_is_valid(dest));
687 return JB_ERR_MEMORY;
692 cur_dest->str = strdup(cur_src->str);
693 if (cur_dest->str == NULL)
697 assert(list_is_valid(src));
698 assert(list_is_valid(dest));
700 return JB_ERR_MEMORY;
703 /* else { cur_dest->str = NULL; } - implied by zalloc */
705 /* Now process the rest */
706 for (cur_src = cur_src->next; cur_src; cur_src = cur_src->next)
708 cur_dest = cur_dest->next = (struct list_entry *)zalloc(sizeof(*cur_dest));
709 if (cur_dest == NULL)
713 assert(list_is_valid(src));
714 assert(list_is_valid(dest));
716 return JB_ERR_MEMORY;
720 cur_dest->str = strdup(cur_src->str);
721 if (cur_dest->str == NULL)
725 assert(list_is_valid(src));
726 assert(list_is_valid(dest));
728 return JB_ERR_MEMORY;
731 /* else { cur_dest->str = NULL; } - implied by zalloc */
734 dest->last = cur_dest;
737 assert(list_is_valid(src));
738 assert(list_is_valid(dest));
744 /*********************************************************************
746 * Function : list_append_list_unique
748 * Description : Append a string list to another list.
749 * Duplicate items are not added.
752 * 1 : dest = pointer to destination list for merge.
753 * 2 : src = pointer to source for merge.
755 * Returns : JB_ERR_OK on success
756 * JB_ERR_MEMORY on out-of-memory error.
757 * On error, some (but not all) of src might have
758 * been copied into dest.
760 *********************************************************************/
761 jb_err list_append_list_unique(struct list *dest, const struct list *src)
763 struct list_entry * cur;
767 assert(list_is_valid(src));
768 assert(list_is_valid(dest));
770 for (cur = src->first; cur; cur = cur->next)
774 if (enlist_unique(dest, cur->str, 0))
776 assert(list_is_valid(src));
777 assert(list_is_valid(dest));
779 return JB_ERR_MEMORY;
784 assert(list_is_valid(src));
785 assert(list_is_valid(dest));
791 /*********************************************************************
793 * Function : list_is_empty
795 * Description : Test whether a list is empty. Does not change the list.
798 * 1 : the_list = pointer to list to test.
800 * Returns : Nonzero if the list contains no entries.
802 *********************************************************************/
803 int list_is_empty(const struct list *the_list)
806 assert(list_is_valid(the_list));
808 return (the_list->first == NULL);
812 /*********************************************************************
814 * Function : list_contains_item
816 * Description : Tests whether a list item is already set.
817 * Does not change the list.
820 * 1 : the_list = list to search in
821 * 2 : str = string to search for
823 * Returns : TRUE if the item was found,
826 *********************************************************************/
827 int list_contains_item(const struct list *the_list, const char *str)
829 struct list_entry *entry;
832 assert(list_is_valid(the_list));
835 for (entry = the_list->first; entry != NULL; entry = entry->next)
837 if (entry->str == NULL)
840 * NULL pointers are allowed in some lists.
841 * For example for csp->headers in case a
842 * header was removed.
847 if (0 == strcmp(str, entry->str))
858 /*********************************************************************
862 * Description : Create a new, empty map.
866 * Returns : A new, empty map, or NULL if out of memory.
868 *********************************************************************/
869 struct map *new_map(void)
871 return (struct map *) zalloc(sizeof(struct map));
875 /*********************************************************************
877 * Function : free_map
879 * Description : Free the memory occupied by a map and its
883 * 1 : the_map = map to be freed. May be NULL.
887 *********************************************************************/
888 void free_map(struct map *the_map)
890 struct map_entry *cur_entry;
891 struct map_entry *next_entry;
898 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = next_entry)
900 freez(cur_entry->name);
901 freez(cur_entry->value);
903 next_entry = cur_entry->next;
907 the_map->first = the_map->last = NULL;
913 /*********************************************************************
917 * Description : Add a mapping from given name to given value to a
920 * Note: Since all strings will be free()d in free_map()
921 * later, set the copy flags for constants or
922 * strings that will be independently free()d.
924 * Note2: This function allows NULL parameters - it
925 * returns JB_ERR_MEMORY in that case.
927 * Note3: If this function returns JB_ERR_MEMORY,
928 * it will free(name) unless you specify
929 * name_needs_copying, and similarly it will
930 * free(value) unless you specify
931 * value_needs_copying.
933 * Due to Note2 and Note3 above, the following code
934 * is legal, and will never crash or leak memory even
935 * if the system runs out of memory:
937 * err = map(mymap, "xyz", 1, html_encode(somestring), 0);
939 * err will be set to JB_ERR_MEMORY if either call runs
940 * out-of-memory. Without these features, you would
941 * need to check the return value of html_encode in the
942 * above example for NULL, which (at least) doubles the
943 * amount of error-checking code needed.
946 * 1 : the_map = map to add to
947 * 2 : name = name to add
948 * 3 : name_needs_copying = flag set if a copy of name should be used
949 * 4 : value = value to add
950 * 5 : value_needs_copying = flag set if a copy of value should be used
952 * Returns : JB_ERR_OK on success
953 * JB_ERR_MEMORY on out-of-memory error.
955 *********************************************************************/
956 jb_err map(struct map *the_map,
957 const char *name, int name_needs_copying,
958 const char *value, int value_needs_copying)
960 struct map_entry *new_entry;
966 || (NULL == (new_entry = zalloc(sizeof(*new_entry)))) )
968 if ((name != NULL) && (!name_needs_copying))
972 if ((value != NULL) && (!value_needs_copying))
976 return JB_ERR_MEMORY;
979 if (name_needs_copying)
981 if (NULL == (name = strdup(name)))
984 if (!value_needs_copying)
988 return JB_ERR_MEMORY;
992 if (value_needs_copying)
994 if (NULL == (value = strdup(value)))
998 return JB_ERR_MEMORY;
1002 new_entry->name = name;
1003 new_entry->value = value;
1004 /* new_entry->next = NULL; - implied by zalloc */
1008 the_map->last->next = new_entry;
1009 the_map->last = new_entry;
1013 the_map->first = new_entry;
1014 the_map->last = new_entry;
1021 /*********************************************************************
1025 * Description : Remove all map_entry structs with a given name from
1029 * 1 : the_map = map to look in
1030 * 2 : name = name to unmap
1032 * Returns : JB_ERR_OK
1034 *********************************************************************/
1035 jb_err unmap(struct map *the_map, const char *name)
1037 struct map_entry *cur_entry, *last_entry;
1042 last_entry = the_map->first;
1044 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
1046 if (!strcmp(name, cur_entry->name))
1049 * Update the incoming pointer
1051 if (cur_entry == the_map->first)
1053 the_map->first = cur_entry->next;
1057 last_entry->next = cur_entry->next;
1061 * Update the map's last pointer
1063 if (cur_entry == the_map->last)
1065 the_map->last = last_entry;
1069 * Free the map_entry
1071 freez(cur_entry->name);
1072 freez(cur_entry->value);
1075 cur_entry = last_entry;
1079 last_entry = cur_entry;
1086 /*********************************************************************
1090 * Description : Look up an item with a given name in a map, and
1094 * 1 : the_map = map to look in
1095 * 2 : name = name parameter to look for
1097 * Returns : the value if found, else the empty string.
1098 * Return value is alloced as part of the map, so
1099 * it is freed when the map is destroyed. Caller
1100 * must not free or modify it.
1102 *********************************************************************/
1103 const char *lookup(const struct map *the_map, const char *name)
1105 const struct map_entry *cur_entry;
1110 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
1112 if (!strcmp(name, cur_entry->name))
1114 return cur_entry->value;