1 const char list_rcs[] = "$Id: list.c,v 1.30 2014/10/18 11:31:52 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;
420 snprintf(header, header_size, "%s: %s", name, value);
422 * The trailing "\r\n" is added by list_to_text(),
423 * if the caller passed them anyway, cut the header
424 * at the first one or dump core if this is a debug
429 if ((*p == '\r') || (*p == '\n'))
436 result = enlist_unique(the_list, header, bytes_to_compare);
438 assert(list_is_valid(the_list));
446 /*********************************************************************
448 * Function : list_remove_all
450 * Description : Remove all entries from a list. On return, the_list
451 * is a valid, empty list. Note that this is similar
452 * to destroy_list(), but the difference is that this
453 * function guarantees that the list structure is still
454 * valid after the call.
457 * 1 : the_list = pointer to list
461 *********************************************************************/
462 void list_remove_all(struct list *the_list)
464 struct list_entry *cur_entry;
465 struct list_entry *next_entry;
468 assert(list_is_valid(the_list));
470 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
472 next_entry = cur_entry->next;
473 freez(cur_entry->str);
477 the_list->first = the_list->last = NULL;
479 assert(list_is_valid(the_list));
483 /*********************************************************************
485 * Function : list_to_text
487 * Description : "Flatten" a string list into 1 long \r\n delimited string,
488 * adding an empty line at the end. NULL entries are ignored.
489 * This function does not change the_list.
491 * XXX: Should probably be renamed as it's only
492 * useful (and used) to flatten header lists.
495 * 1 : the_list = pointer to list
497 * Returns : NULL on malloc error, else new long string.
498 * Caller must free() it.
500 *********************************************************************/
501 char *list_to_text(const struct list *the_list)
503 struct list_entry *cur_entry;
510 assert(list_is_valid(the_list));
513 * Calculate the length of the final text.
514 * '2' because of the '\r\n' at the end of
515 * each string and at the end of the text.
518 for (cur_entry = the_list->first; cur_entry; cur_entry = cur_entry->next)
522 text_length += strlen(cur_entry->str) + 2;
526 bytes_left = text_length + 1;
528 text = (char *)malloc(bytes_left);
536 for (cur_entry = the_list->first; cur_entry; cur_entry = cur_entry->next)
540 const int written = snprintf(cursor, bytes_left, "%s\r\n", cur_entry->str);
543 assert(written < bytes_left);
545 bytes_left -= (size_t)written;
546 cursor += (size_t)written;
550 assert(bytes_left == 3);
556 assert(text_length == cursor - text);
557 assert(text[text_length] == '\0');
563 /*********************************************************************
565 * Function : list_remove_item
567 * Description : Remove a string from a specified string list.
570 * 1 : the_list = pointer to list
571 * 2 : str = string to remove from the list - non-NULL
573 * Returns : Number of times it was removed.
575 *********************************************************************/
576 int list_remove_item(struct list *the_list, const char *str)
578 struct list_entry *prev = NULL;
579 struct list_entry *cur;
580 struct list_entry *next;
584 assert(list_is_valid(the_list));
587 cur = the_list->first;
593 if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
603 the_list->first = next;
605 free((char *)cur->str);
615 the_list->last = prev;
617 assert(list_is_valid(the_list));
623 /*********************************************************************
625 * Function : list_remove_list
627 * Description : Remove all strings in one list from another list.
628 * This is currently a brute-force algorithm
629 * (it compares every pair of strings).
632 * 1 : dest = list to change
633 * 2 : src = list of strings to remove
635 * Returns : Total number of strings removed.
637 *********************************************************************/
638 int list_remove_list(struct list *dest, const struct list *src)
640 struct list_entry *cur;
645 assert(list_is_valid(src));
646 assert(list_is_valid(dest));
648 for (cur = src->first; cur != NULL; cur = cur->next)
650 if (cur->str != NULL)
652 count += list_remove_item(dest, cur->str);
656 assert(list_is_valid(src));
657 assert(list_is_valid(dest));
663 /*********************************************************************
665 * Function : list_duplicate
667 * Description : Copy a string list
670 * 1 : dest = Destination list. Must be a valid list.
671 * All existing entries will be removed.
672 * 1 : src = pointer to source list for copy.
674 * Returns : JB_ERR_OK on success
675 * JB_ERR_MEMORY on out-of-memory error.
676 * On error, dest will be empty.
678 *********************************************************************/
679 jb_err list_duplicate(struct list *dest, const struct list *src)
681 struct list_entry * cur_src;
682 struct list_entry * cur_dest;
686 assert(list_is_valid(src));
687 assert(list_is_valid(dest));
689 list_remove_all(dest);
691 /* Need to process first entry specially so we can set dest->first */
692 cur_src = src->first;
695 cur_dest = dest->first = (struct list_entry *)zalloc(sizeof(*cur_dest));
696 if (cur_dest == NULL)
700 assert(list_is_valid(src));
701 assert(list_is_valid(dest));
703 return JB_ERR_MEMORY;
708 cur_dest->str = strdup(cur_src->str);
709 if (cur_dest->str == NULL)
713 assert(list_is_valid(src));
714 assert(list_is_valid(dest));
716 return JB_ERR_MEMORY;
719 /* else { cur_dest->str = NULL; } - implied by zalloc */
721 /* Now process the rest */
722 for (cur_src = cur_src->next; cur_src; cur_src = cur_src->next)
724 cur_dest = cur_dest->next = (struct list_entry *)zalloc(sizeof(*cur_dest));
725 if (cur_dest == NULL)
729 assert(list_is_valid(src));
730 assert(list_is_valid(dest));
732 return JB_ERR_MEMORY;
736 cur_dest->str = strdup(cur_src->str);
737 if (cur_dest->str == NULL)
741 assert(list_is_valid(src));
742 assert(list_is_valid(dest));
744 return JB_ERR_MEMORY;
747 /* else { cur_dest->str = NULL; } - implied by zalloc */
750 dest->last = cur_dest;
753 assert(list_is_valid(src));
754 assert(list_is_valid(dest));
760 /*********************************************************************
762 * Function : list_append_list_unique
764 * Description : Append a string list to another list.
765 * Duplicate items are not added.
768 * 1 : dest = pointer to destination list for merge.
769 * 2 : src = pointer to source for merge.
771 * Returns : JB_ERR_OK on success
772 * JB_ERR_MEMORY on out-of-memory error.
773 * On error, some (but not all) of src might have
774 * been copied into dest.
776 *********************************************************************/
777 jb_err list_append_list_unique(struct list *dest, const struct list *src)
779 struct list_entry * cur;
783 assert(list_is_valid(src));
784 assert(list_is_valid(dest));
786 for (cur = src->first; cur; cur = cur->next)
790 if (enlist_unique(dest, cur->str, 0))
792 assert(list_is_valid(src));
793 assert(list_is_valid(dest));
795 return JB_ERR_MEMORY;
800 assert(list_is_valid(src));
801 assert(list_is_valid(dest));
807 /*********************************************************************
809 * Function : list_is_empty
811 * Description : Test whether a list is empty. Does not change the list.
814 * 1 : the_list = pointer to list to test.
816 * Returns : Nonzero if the list contains no entries.
818 *********************************************************************/
819 int list_is_empty(const struct list *the_list)
822 assert(list_is_valid(the_list));
824 return (the_list->first == NULL);
828 /*********************************************************************
830 * Function : list_contains_item
832 * Description : Tests whether a list item is already set.
833 * Does not change the list.
836 * 1 : the_list = list to search in
837 * 2 : str = string to search for
839 * Returns : TRUE if the item was found,
842 *********************************************************************/
843 int list_contains_item(const struct list *the_list, const char *str)
845 struct list_entry *entry;
848 assert(list_is_valid(the_list));
851 for (entry = the_list->first; entry != NULL; entry = entry->next)
853 if (entry->str == NULL)
856 * NULL pointers are allowed in some lists.
857 * For example for csp->headers in case a
858 * header was removed.
863 if (0 == strcmp(str, entry->str))
874 /*********************************************************************
878 * Description : Create a new, empty map.
879 * Causes program exit if the memory allocation fails.
883 * Returns : A new, empty map
885 *********************************************************************/
886 struct map *new_map(void)
888 struct map *empty_map = zalloc(sizeof(struct map));
890 if (NULL == empty_map)
900 /*********************************************************************
902 * Function : free_map
904 * Description : Free the memory occupied by a map and its
908 * 1 : the_map = map to be freed. May be NULL.
912 *********************************************************************/
913 void free_map(struct map *the_map)
915 struct map_entry *cur_entry;
916 struct map_entry *next_entry;
923 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = next_entry)
925 freez(cur_entry->name);
926 freez(cur_entry->value);
928 next_entry = cur_entry->next;
932 the_map->first = the_map->last = NULL;
938 /*********************************************************************
942 * Description : Add a mapping from given name to given value to a
945 * Note: Since all strings will be free()d in free_map()
946 * later, set the copy flags for constants or
947 * strings that will be independently free()d.
949 * Note2: This function allows NULL parameters - it
950 * returns JB_ERR_MEMORY in that case.
952 * Note3: If this function returns JB_ERR_MEMORY,
953 * it will free(name) unless you specify
954 * name_needs_copying, and similarly it will
955 * free(value) unless you specify
956 * value_needs_copying.
958 * Due to Note2 and Note3 above, the following code
959 * is legal, and will never crash or leak memory even
960 * if the system runs out of memory:
962 * err = map(mymap, "xyz", 1, html_encode(somestring), 0);
964 * err will be set to JB_ERR_MEMORY if either call runs
965 * out-of-memory. Without these features, you would
966 * need to check the return value of html_encode in the
967 * above example for NULL, which (at least) doubles the
968 * amount of error-checking code needed.
971 * 1 : the_map = map to add to
972 * 2 : name = name to add
973 * 3 : name_needs_copying = flag set if a copy of name should be used
974 * 4 : value = value to add
975 * 5 : value_needs_copying = flag set if a copy of value should be used
977 * Returns : JB_ERR_OK on success
978 * JB_ERR_MEMORY on out-of-memory error.
980 *********************************************************************/
981 jb_err map(struct map *the_map,
982 const char *name, int name_needs_copying,
983 const char *value, int value_needs_copying)
985 struct map_entry *new_entry;
991 || (NULL == (new_entry = zalloc(sizeof(*new_entry)))))
993 if ((name != NULL) && (!name_needs_copying))
997 if ((value != NULL) && (!value_needs_copying))
1001 return JB_ERR_MEMORY;
1004 if (name_needs_copying)
1006 if (NULL == (name = strdup(name)))
1009 if (!value_needs_copying)
1011 free((char *)value);
1013 return JB_ERR_MEMORY;
1017 if (value_needs_copying)
1019 if (NULL == (value = strdup(value)))
1023 return JB_ERR_MEMORY;
1027 new_entry->name = name;
1028 new_entry->value = value;
1029 /* new_entry->next = NULL; - implied by zalloc */
1033 the_map->last->next = new_entry;
1034 the_map->last = new_entry;
1038 the_map->first = new_entry;
1039 the_map->last = new_entry;
1046 /*********************************************************************
1050 * Description : Remove all map_entry structs with a given name from
1054 * 1 : the_map = map to look in
1055 * 2 : name = name to unmap
1057 * Returns : JB_ERR_OK
1059 *********************************************************************/
1060 jb_err unmap(struct map *the_map, const char *name)
1062 struct map_entry *cur_entry, *last_entry;
1067 last_entry = the_map->first;
1069 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
1071 if (!strcmp(name, cur_entry->name))
1074 * Update the incoming pointer
1076 if (cur_entry == the_map->first)
1078 the_map->first = cur_entry->next;
1082 last_entry->next = cur_entry->next;
1086 * Update the map's last pointer
1088 if (cur_entry == the_map->last)
1090 the_map->last = last_entry;
1094 * Free the map_entry
1096 freez(cur_entry->name);
1097 freez(cur_entry->value);
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 alloced 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;