1 const char list_rcs[] = "$Id: list.c,v 1.13 2002/03/07 03:46:17 oes 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://ijbswa.sourceforge.net
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.13 2002/03/07 03:46:17 oes
38 * Fixed compiler warnings
40 * Revision 1.12 2001/10/25 03:40:48 david__schmidt
41 * Change in porting tactics: OS/2's EMX porting layer doesn't allow multiple
42 * threads to call select() simultaneously. So, it's time to do a real, live,
43 * native OS/2 port. See defines for __EMX__ (the porting layer) vs. __OS2__
44 * (native). Both versions will work, but using __OS2__ offers multi-threading.
46 * Revision 1.11 2001/10/23 21:21:03 jongfoster
47 * New error handling - error codes are now jb_errs, not ints.
48 * Changed the way map() handles out-of-memory, to dramatically
49 * reduce the amount of error-checking clutter needed.
51 * Revision 1.10 2001/09/16 17:30:24 jongfoster
52 * Fixing a compiler warning.
54 * Revision 1.9 2001/09/16 13:20:29 jongfoster
55 * Rewrite of list library. Now has seperate header and list_entry
56 * structures. Also added a large sprinking of assert()s to the list
59 * Revision 1.8 2001/08/07 14:00:20 oes
62 * Revision 1.7 2001/08/05 16:06:20 jongfoster
63 * Modifiying "struct map" so that there are now separate header and
64 * "map_entry" structures. This means that functions which modify a
65 * map no longer need to return a pointer to the modified map.
66 * Also, it no longer reverses the order of the entries (which may be
67 * important with some advanced template substitutions).
69 * Revision 1.6 2001/07/31 14:44:51 oes
70 * list_to_text() now appends empty line at end
72 * Revision 1.5 2001/06/29 21:45:41 oes
73 * Indentation, CRLF->LF, Tab-> Space
75 * Revision 1.4 2001/06/29 13:30:22 oes
76 * - Added Convenience function enlist_unique_header(),
77 * which takes the Header name and value as separate
78 * arguments and thus saves the pain of sprintf()ing
79 * and determining the Header name length to enlist_unique
81 * - Removed logentry from cancelled commit
83 * Revision 1.3 2001/06/03 19:12:24 oes
84 * functions for new struct map, extended enlist_unique
86 * Revision 1.2 2001/06/01 18:49:17 jongfoster
87 * Replaced "list_share" with "list" - the tiny memory gain was not
88 * worth the extra complexity.
90 * Revision 1.1 2001/05/31 21:11:53 jongfoster
91 * - Moved linked list support to new "list.c" file.
92 * Structure definitions are still in project.h,
93 * function prototypes are now in "list.h".
94 * - Added support for "struct list_share", which is identical
95 * to "struct list" except it saves memory by not duplicating
96 * the strings. Obviously, this only works if there is some
97 * other way of managing the memory used by the strings.
98 * (These list_share lists are used for lists which last
99 * for only 1 request, and where all the list entries are
100 * just coming directly from entries in the actionsfile.)
101 * Note that you still need to destroy list_share lists
102 * properly to free the nodes - it's only the strings
106 *********************************************************************/
112 /* FIXME: The following headers are not needed for Win32. Are they
113 * needed on other platforms?
116 #include <sys/types.h>
122 #if !defined(_WIN32) && !defined(__OS2__)
130 #include "miscutil.h"
132 const char list_h_rcs[] = LIST_H_VERSION;
135 static int list_is_valid (const struct list *the_list);
138 /*********************************************************************
140 * Function : list_init
142 * Description : Create a new, empty list in user-allocated memory.
143 * Caller should allocate a "struct list" variable,
144 * then pass it to this function.
145 * (Implementation note: Rather than calling this
146 * function, you can also just memset the memory to
147 * zero, e.g. if you have a larger structure you
148 * want to initialize quickly. However, that isn't
149 * really good design.)
152 * 1 : the_list = pointer to list
156 *********************************************************************/
157 void init_list(struct list *the_list)
159 memset(the_list, '\0', sizeof(*the_list));
163 /*********************************************************************
165 * Function : destroy_list
167 * Description : Destroy a string list (opposite of list_init).
168 * On return, the memory used by the list entries has
169 * been freed, but not the memory used by the_list
170 * itself. You should not re-use the_list without
171 * calling list_init().
173 * (Implementation note: You *can* reuse the_list
174 * without calling list_init(), but please don't.
175 * If you want to remove all entries from a list
176 * and still have a usable list, then use
177 * list_remove_all().)
180 * 1 : the_list = pointer to list
184 *********************************************************************/
185 void destroy_list (struct list *the_list)
187 struct list_entry *cur_entry, *next_entry;
191 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
193 next_entry = cur_entry->next;
194 freez(cur_entry->str);
198 the_list->first = NULL;
199 the_list->last = NULL;
203 /*********************************************************************
205 * Function : list_is_valid
207 * Description : Check that a string list is valid. The intended
208 * usage is "assert(list_is_valid(the_list))".
209 * Currently this checks that "the_list->last"
210 * is correct, and that the list dosn't contain
211 * circular references. It is likely to crash if
212 * it's passed complete garbage.
215 * 1 : the_list = pointer to list. Must be non-null.
217 * Returns : 1 if list is valid, 0 otherwise.
219 *********************************************************************/
220 static int list_is_valid (const struct list *the_list)
223 * If you don't want this check, just change the line below
224 * from "#if 1" to "#if 0".
227 const struct list_entry *cur_entry;
228 const struct list_entry *last_entry = NULL;
233 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
235 last_entry = cur_entry;
240 * Just check that this string can be accessed - i.e. it's a valid
243 strlen(cur_entry->str);
247 * Check for looping back to first
249 if ((length != 0) && (cur_entry == the_list->first))
255 * Arbitrarily limit length to prevent infinite loops.
263 * Check this isn't marked as the last entry, unless of course it's
264 * *really* the last entry.
266 if ((the_list->last == cur_entry) && (cur_entry->next != NULL))
268 /* This is the last entry, but there's data after it !!?? */
273 return (the_list->last == last_entry);
279 /*********************************************************************
283 * Description : Append a string into a specified string list.
286 * 1 : the_list = pointer to list
287 * 2 : str = string to add to the list (maybe NULL)
289 * Returns : JB_ERR_OK on success
290 * JB_ERR_MEMORY on out-of-memory error.
291 * On error, the_list will be unchanged.
293 *********************************************************************/
294 jb_err enlist(struct list *the_list, const char *str)
296 struct list_entry *cur;
299 assert(list_is_valid(the_list));
301 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
303 return JB_ERR_MEMORY;
308 if (NULL == (cur->str = strdup(str)))
311 return JB_ERR_MEMORY;
314 /* else { cur->str = NULL; } - implied by zalloc */
316 /* cur->next = NULL; - implied by zalloc */
320 the_list->last->next = cur;
321 the_list->last = cur;
325 the_list->first = cur;
326 the_list->last = cur;
329 assert(list_is_valid(the_list));
334 /*********************************************************************
336 * Function : enlist_first
338 * Description : Append a string as first element into a specified
342 * 1 : the_list = pointer to list
343 * 2 : str = string to add to the list (maybe NULL)
345 * Returns : JB_ERR_OK on success
346 * JB_ERR_MEMORY on out-of-memory error.
347 * On error, the_list will be unchanged.
349 *********************************************************************/
350 jb_err enlist_first(struct list *the_list, const char *str)
352 struct list_entry *cur;
355 assert(list_is_valid(the_list));
357 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
359 return JB_ERR_MEMORY;
364 if (NULL == (cur->str = strdup(str)))
367 return JB_ERR_MEMORY;
370 /* else { cur->str = NULL; } - implied by zalloc */
372 cur->next = the_list->first;
374 the_list->first = cur;
375 if (the_list->last == NULL)
377 the_list->last = cur;
380 assert(list_is_valid(the_list));
385 /*********************************************************************
387 * Function : enlist_unique
389 * Description : Append a string into a specified string list,
390 * if & only if it's not there already.
391 * If the num_significant_chars argument is nonzero,
392 * only compare up to the nth character.
395 * 1 : the_list = pointer to list
396 * 2 : str = string to add to the list
397 * 3 : num_significant_chars = number of chars to use
398 * for uniqueness test, or 0 to require an exact match.
400 * Returns : JB_ERR_OK on success
401 * JB_ERR_MEMORY on out-of-memory error.
402 * On error, the_list will be unchanged.
403 * "Success" does not indicate whether or not the
404 * item was already in the list.
406 *********************************************************************/
407 jb_err enlist_unique(struct list *the_list, const char *str,
408 size_t num_significant_chars)
410 struct list_entry *cur_entry;
413 assert(list_is_valid(the_list));
415 assert(num_significant_chars >= 0);
416 assert(num_significant_chars <= strlen(str));
418 if (num_significant_chars > 0)
420 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
422 if ( (cur_entry->str != NULL)
423 && (0 == strncmp(str, cur_entry->str, num_significant_chars)))
432 /* Test whole string */
433 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
435 if ( (cur_entry->str != NULL) && (0 == strcmp(str, cur_entry->str)))
443 return enlist(the_list, str);
447 /*********************************************************************
449 * Function : enlist_unique_header
451 * Description : Make a HTTP header from the two strings name and value,
452 * and append the result into a specified string list,
453 * if & only if there isn't already a header with that name.
456 * 1 : the_list = pointer to list
457 * 2 : name = HTTP header name (e.g. "Content-type")
458 * 3 : value = HTTP header value (e.g. "text/html")
460 * Returns : JB_ERR_OK on success
461 * JB_ERR_MEMORY on out-of-memory error.
462 * On error, the_list will be unchanged.
463 * "Success" does not indicate whether or not the
464 * header was already in the list.
466 *********************************************************************/
467 jb_err enlist_unique_header(struct list *the_list, const char *name,
475 assert(list_is_valid(the_list));
479 length = strlen(name) + 2;
480 if (NULL == (str = (char *)malloc(length + strlen(value) + 1)))
482 return JB_ERR_MEMORY;
485 str[length - 2] = ':';
486 str[length - 1] = ' ';
487 strcpy(str + length, value);
489 result = enlist_unique(the_list, str, length);
493 assert(list_is_valid(the_list));
500 /*********************************************************************
502 * Function : list_remove_all
504 * Description : Remove all entries from a list. On return, the_list
505 * is a valid, empty list. Note that this is similar
506 * to destroy_list(), but the difference is that this
507 * function guarantees that the list structure is still
508 * valid after the call.
511 * 1 : the_list = pointer to list
515 *********************************************************************/
516 void list_remove_all(struct list *the_list)
518 struct list_entry *cur_entry;
519 struct list_entry *next_entry;
522 assert(list_is_valid(the_list));
524 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
526 next_entry = cur_entry->next;
527 freez(cur_entry->str);
531 the_list->first = the_list->last = NULL;
533 assert(list_is_valid(the_list));
537 /*********************************************************************
539 * Function : list_to_text
541 * Description : "Flatten" a string list into 1 long \r\n delimited string,
542 * adding an empty line at the end. NULL entries are ignored.
543 * This function does not change the_list.
546 * 1 : the_list = pointer to list
548 * Returns : NULL on malloc error, else new long string.
549 * Caller must free() it.
551 *********************************************************************/
552 char *list_to_text(const struct list *the_list)
554 struct list_entry *cur_entry;
560 assert(list_is_valid(the_list));
562 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
566 size += strlen(cur_entry->str) + 2;
570 if ((ret = (char *)malloc(size + 1)) == NULL)
579 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
583 strcpy(s, cur_entry->str);
585 *s++ = '\r'; *s++ = '\n';
588 *s++ = '\r'; *s++ = '\n';
594 /*********************************************************************
596 * Function : list_remove_item
598 * Description : Remove a string from a specified string list.
601 * 1 : the_list = pointer to list
602 * 2 : str = string to remove from the list - non-NULL
604 * Returns : Number of times it was removed.
606 *********************************************************************/
607 int list_remove_item(struct list *the_list, const char *str)
609 struct list_entry *prev = NULL;
610 struct list_entry *cur;
611 struct list_entry *next;
615 assert(list_is_valid(the_list));
618 cur = the_list->first;
624 if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
634 the_list->first = next;
636 free((char *)cur->str);
646 the_list->last = prev;
648 assert(list_is_valid(the_list));
654 /*********************************************************************
656 * Function : list_remove_list
658 * Description : Remove all strings in one list from another list.
659 * This is currently a brute-force algorithm
660 * (it compares every pair of strings).
663 * 1 : dest = list to change
664 * 2 : src = list of strings to remove
666 * Returns : Total number of strings removed.
668 *********************************************************************/
669 int list_remove_list(struct list *dest, const struct list *src)
671 struct list_entry *cur;
676 assert(list_is_valid(src));
677 assert(list_is_valid(dest));
679 for (cur = src->first; cur != NULL; cur = cur->next)
681 if (cur->str != NULL)
683 count += list_remove_item(dest, cur->str);
687 assert(list_is_valid(src));
688 assert(list_is_valid(dest));
694 /*********************************************************************
696 * Function : list_duplicate
698 * Description : Copy a string list
701 * 1 : dest = Destination list. Must be a valid list.
702 * All existing entries will be removed.
703 * 1 : src = pointer to source list for copy.
705 * Returns : JB_ERR_OK on success
706 * JB_ERR_MEMORY on out-of-memory error.
707 * On error, dest will be empty.
709 *********************************************************************/
710 jb_err list_duplicate(struct list *dest, const struct list *src)
712 struct list_entry * cur_src;
713 struct list_entry * cur_dest;
717 assert(list_is_valid(src));
718 assert(list_is_valid(dest));
720 list_remove_all(dest);
722 /* Need to process first entry specially so we can set dest->first */
723 cur_src = src->first;
726 cur_dest = dest->first = (struct list_entry *)zalloc(sizeof(*cur_dest));
727 if (cur_dest == NULL)
731 assert(list_is_valid(src));
732 assert(list_is_valid(dest));
734 return JB_ERR_MEMORY;
739 cur_dest->str = strdup(cur_src->str);
740 if (cur_dest->str == NULL)
744 assert(list_is_valid(src));
745 assert(list_is_valid(dest));
747 return JB_ERR_MEMORY;
750 /* else { cur_dest->str = NULL; } - implied by zalloc */
752 /* Now process the rest */
753 for (cur_src = cur_src->next; cur_src; cur_src = cur_src->next)
755 cur_dest = cur_dest->next = (struct list_entry *)zalloc(sizeof(*cur_dest));
756 if (cur_dest == NULL)
760 assert(list_is_valid(src));
761 assert(list_is_valid(dest));
763 return JB_ERR_MEMORY;
767 cur_dest->str = strdup(cur_src->str);
768 if (cur_dest->str == NULL)
772 assert(list_is_valid(src));
773 assert(list_is_valid(dest));
775 return JB_ERR_MEMORY;
778 /* else { cur_dest->str = NULL; } - implied by zalloc */
781 dest->last = cur_dest;
784 assert(list_is_valid(src));
785 assert(list_is_valid(dest));
791 /*********************************************************************
793 * Function : list_append_list_unique
795 * Description : Append a string list to another list.
796 * Duplicate items are not added.
799 * 1 : dest = pointer to destination list for merge.
800 * 2 : src = pointer to source for merge.
802 * Returns : JB_ERR_OK on success
803 * JB_ERR_MEMORY on out-of-memory error.
804 * On error, some (but not all) of src might have
805 * been copied into dest.
807 *********************************************************************/
808 jb_err list_append_list_unique(struct list *dest, const struct list *src)
810 struct list_entry * cur;
814 assert(list_is_valid(src));
815 assert(list_is_valid(dest));
817 for (cur = src->first; cur; cur = cur->next)
821 if (enlist_unique(dest, cur->str, 0))
823 assert(list_is_valid(src));
824 assert(list_is_valid(dest));
826 return JB_ERR_MEMORY;
831 assert(list_is_valid(src));
832 assert(list_is_valid(dest));
838 /*********************************************************************
840 * Function : list_is_empty
842 * Description : Test whether a list is empty. Does not change the list.
845 * 1 : the_list = pointer to list to test.
847 * Returns : Nonzero iff the list contains no entries.
849 *********************************************************************/
850 int list_is_empty(const struct list *the_list)
853 assert(list_is_valid(the_list));
855 return (the_list->first == NULL);
859 /*********************************************************************
863 * Description : Create a new, empty map.
867 * Returns : A new, empty map, or NULL if out of memory.
869 *********************************************************************/
870 struct map *new_map(void)
872 return (struct map *) zalloc(sizeof(struct map));
876 /*********************************************************************
878 * Function : free_map
880 * Description : Free the memory occupied by a map and its
884 * 1 : the_map = map to be freed. May be NULL.
888 *********************************************************************/
889 void free_map(struct map *the_map)
891 struct map_entry *cur_entry;
892 struct map_entry *next_entry;
899 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = next_entry)
901 freez(cur_entry->name);
902 freez(cur_entry->value);
904 next_entry = cur_entry->next;
908 the_map->first = the_map->last = NULL;
914 /*********************************************************************
918 * Description : Add a mapping from given name to given value to a
921 * Note: Since all strings will be free()d in free_map()
922 * later, set the copy flags for constants or
923 * strings that will be independantly free()d.
925 * Note2: This function allows NULL parameters - it
926 * returns JB_ERR_MEMORY in that case.
928 * Note3: If this function returns JB_ERR_MEMORY,
929 * it will free(name) unless you specify
930 * name_needs_copying, and similarly it will
931 * free(value) unless you specify
932 * value_needs_copying.
934 * Due to Note2 and Note3 above, the following code
935 * is legal, and will never crash or leak memory even
936 * if the system runs out of memory:
938 * err = map(mymap, "xyz", 1, html_encode(somestring), 0);
940 * err will be set to JB_ERR_MEMORY if either call runs
941 * out-of-memory. Without these features, you would
942 * need to check the return value of html_encode in the
943 * above example for NULL, which (at least) doubles the
944 * amount of error-checking code needed.
947 * 1 : the_map = map to add to
948 * 2 : name = name to add
949 * 3 : name_needs_copying = flag set if a copy of name should be used
950 * 4 : value = value to add
951 * 5 : value_needs_copying = flag set if a copy of value should be used
953 * Returns : JB_ERR_OK on success
954 * JB_ERR_MEMORY on out-of-memory error.
956 *********************************************************************/
957 jb_err map(struct map *the_map,
958 const char *name, int name_needs_copying,
959 const char *value, int value_needs_copying)
961 struct map_entry *new_entry;
967 || (NULL == (new_entry = zalloc(sizeof(*new_entry)))) )
969 if ((name != NULL) && (!name_needs_copying))
973 if ((value != NULL) && (!value_needs_copying))
977 return JB_ERR_MEMORY;
980 if (name_needs_copying)
982 if (NULL == (name = strdup(name)))
985 if (!value_needs_copying)
989 return JB_ERR_MEMORY;
993 if (value_needs_copying)
995 if (NULL == (value = strdup(value)))
999 return JB_ERR_MEMORY;
1003 new_entry->name = name;
1004 new_entry->value = value;
1005 /* new_entry->next = NULL; - implied by zalloc */
1009 the_map->last->next = new_entry;
1010 the_map->last = new_entry;
1014 the_map->first = new_entry;
1015 the_map->last = new_entry;
1022 /*********************************************************************
1026 * Description : Look up an item with a given name in a map, and
1030 * 1 : the_map = map to look in
1031 * 2 : name = name parameter to look for
1033 * Returns : the value if found, else the empty string.
1034 * Return value is alloced as part of the map, so
1035 * it is freed when the map is destroyed. Caller
1036 * must not free or modify it.
1038 *********************************************************************/
1039 const char *lookup(const struct map *the_map, const char *name)
1041 const struct map_entry *cur_entry;
1046 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
1048 if (!strcmp(name, cur_entry->name))
1050 return cur_entry->value;