1 const char list_rcs[] = "$Id: list.c,v 1.10 2001/09/16 17:30:24 jongfoster 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 * IJBSWA 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.10 2001/09/16 17:30:24 jongfoster
38 * Fixing a compiler warning.
40 * Revision 1.9 2001/09/16 13:20:29 jongfoster
41 * Rewrite of list library. Now has seperate header and list_entry
42 * structures. Also added a large sprinking of assert()s to the list
45 * Revision 1.8 2001/08/07 14:00:20 oes
48 * Revision 1.7 2001/08/05 16:06:20 jongfoster
49 * Modifiying "struct map" so that there are now separate header and
50 * "map_entry" structures. This means that functions which modify a
51 * map no longer need to return a pointer to the modified map.
52 * Also, it no longer reverses the order of the entries (which may be
53 * important with some advanced template substitutions).
55 * Revision 1.6 2001/07/31 14:44:51 oes
56 * list_to_text() now appends empty line at end
58 * Revision 1.5 2001/06/29 21:45:41 oes
59 * Indentation, CRLF->LF, Tab-> Space
61 * Revision 1.4 2001/06/29 13:30:22 oes
62 * - Added Convenience function enlist_unique_header(),
63 * which takes the Header name and value as separate
64 * arguments and thus saves the pain of sprintf()ing
65 * and determining the Header name length to enlist_unique
67 * - Removed logentry from cancelled commit
69 * Revision 1.3 2001/06/03 19:12:24 oes
70 * functions for new struct map, extended enlist_unique
72 * Revision 1.2 2001/06/01 18:49:17 jongfoster
73 * Replaced "list_share" with "list" - the tiny memory gain was not
74 * worth the extra complexity.
76 * Revision 1.1 2001/05/31 21:11:53 jongfoster
77 * - Moved linked list support to new "list.c" file.
78 * Structure definitions are still in project.h,
79 * function prototypes are now in "list.h".
80 * - Added support for "struct list_share", which is identical
81 * to "struct list" except it saves memory by not duplicating
82 * the strings. Obviously, this only works if there is some
83 * other way of managing the memory used by the strings.
84 * (These list_share lists are used for lists which last
85 * for only 1 request, and where all the list entries are
86 * just coming directly from entries in the actionsfile.)
87 * Note that you still need to destroy list_share lists
88 * properly to free the nodes - it's only the strings
92 *********************************************************************/
98 /* FIXME: The following headers are not needed for Win32. Are they
99 * needed on other platforms?
102 #include <sys/types.h>
116 #include "miscutil.h"
118 const char list_h_rcs[] = LIST_H_VERSION;
121 static int list_is_valid (const struct list *the_list);
124 /*********************************************************************
126 * Function : list_init
128 * Description : Create a new, empty list in user-allocated memory.
129 * Caller should allocate a "struct list" variable,
130 * then pass it to this function.
131 * (Implementation note: Rather than calling this
132 * function, you can also just memset the memory to
133 * zero, e.g. if you have a larger structure you
134 * want to initialize quickly. However, that isn't
135 * really good design.)
138 * 1 : the_list = pointer to list
142 *********************************************************************/
143 void init_list(struct list *the_list)
145 memset(the_list, '\0', sizeof(*the_list));
149 /*********************************************************************
151 * Function : destroy_list
153 * Description : Destroy a string list (opposite of list_init).
154 * On return, the memory used by the list entries has
155 * been freed, but not the memory used by the_list
156 * itself. You should not re-use the_list without
157 * calling list_init().
159 * (Implementation note: You *can* reuse the_list
160 * without calling list_init(), but please don't.
161 * If you want to remove all entries from a list
162 * and still have a usable list, then use
163 * list_remove_all().)
166 * 1 : the_list = pointer to list
170 *********************************************************************/
171 void destroy_list (struct list *the_list)
173 struct list_entry *cur_entry, *next_entry;
177 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
179 next_entry = cur_entry->next;
180 freez((char *)cur_entry->str);
184 the_list->first = NULL;
185 the_list->last = NULL;
189 /*********************************************************************
191 * Function : list_is_valid
193 * Description : Check that a string list is valid. The intended
194 * usage is "assert(list_is_valid(the_list))".
195 * Currently this checks that "the_list->last"
196 * is correct, and that the list dosn't contain
197 * circular references. It is likely to crash if
198 * it's passed complete garbage.
201 * 1 : the_list = pointer to list. Must be non-null.
203 * Returns : 1 if list is valid, 0 otherwise.
205 *********************************************************************/
206 static int list_is_valid (const struct list *the_list)
209 * If you don't want this check, just change the line below
210 * from "#if 1" to "#if 0".
213 const struct list_entry *cur_entry;
214 const struct list_entry *last_entry = NULL;
219 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
221 last_entry = cur_entry;
226 * Just check that this string can be accessed - i.e. it's a valid
229 strlen(cur_entry->str);
233 * Check for looping back to first
235 if ((length != 0) && (cur_entry == the_list->first))
241 * Arbitrarily limit length to prevent infinite loops.
249 * Check this isn't marked as the last entry, unless of course it's
250 * *really* the last entry.
252 if ((the_list->last == cur_entry) && (cur_entry->next != NULL))
254 /* This is the last entry, but there's data after it !!?? */
259 return (the_list->last == last_entry);
265 /*********************************************************************
269 * Description : Append a string into a specified string list.
272 * 1 : the_list = pointer to list
273 * 2 : str = string to add to the list (maybe NULL)
275 * Returns : JB_ERR_OK on success
276 * JB_ERR_MEMORY on out-of-memory error.
277 * On error, the_list will be unchanged.
279 *********************************************************************/
280 jb_err enlist(struct list *the_list, const char *str)
282 struct list_entry *cur;
285 assert(list_is_valid(the_list));
287 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
289 return JB_ERR_MEMORY;
294 if (NULL == (cur->str = strdup(str)))
297 return JB_ERR_MEMORY;
300 /* else { cur->str = NULL; } - implied by zalloc */
302 /* cur->next = NULL; - implied by zalloc */
306 the_list->last->next = cur;
307 the_list->last = cur;
311 the_list->first = cur;
312 the_list->last = cur;
315 assert(list_is_valid(the_list));
320 /*********************************************************************
322 * Function : enlist_first
324 * Description : Append a string as first element into a specified
328 * 1 : the_list = pointer to list
329 * 2 : str = string to add to the list (maybe NULL)
331 * Returns : JB_ERR_OK on success
332 * JB_ERR_MEMORY on out-of-memory error.
333 * On error, the_list will be unchanged.
335 *********************************************************************/
336 jb_err enlist_first(struct list *the_list, const char *str)
338 struct list_entry *cur;
341 assert(list_is_valid(the_list));
343 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
345 return JB_ERR_MEMORY;
350 if (NULL == (cur->str = strdup(str)))
353 return JB_ERR_MEMORY;
356 /* else { cur->str = NULL; } - implied by zalloc */
358 cur->next = the_list->first;
360 the_list->first = cur;
361 if (the_list->last == NULL)
363 the_list->last = cur;
366 assert(list_is_valid(the_list));
371 /*********************************************************************
373 * Function : enlist_unique
375 * Description : Append a string into a specified string list,
376 * if & only if it's not there already.
377 * If the num_significant_chars argument is nonzero,
378 * only compare up to the nth character.
381 * 1 : the_list = pointer to list
382 * 2 : str = string to add to the list
383 * 3 : num_significant_chars = number of chars to use
384 * for uniqueness test, or 0 to require an exact match.
386 * Returns : JB_ERR_OK on success
387 * JB_ERR_MEMORY on out-of-memory error.
388 * On error, the_list will be unchanged.
389 * "Success" does not indicate whether or not the
390 * item was already in the list.
392 *********************************************************************/
393 jb_err enlist_unique(struct list *the_list, const char *str,
394 int num_significant_chars)
396 struct list_entry *cur_entry;
399 assert(list_is_valid(the_list));
401 assert(num_significant_chars >= 0);
402 assert((size_t)num_significant_chars <= strlen(str));
404 if (num_significant_chars > 0)
406 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
408 if ( (cur_entry->str != NULL)
409 && (0 == strncmp(str, cur_entry->str, num_significant_chars)))
418 /* Test whole string */
419 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
421 if ( (cur_entry->str != NULL) && (0 == strcmp(str, cur_entry->str)))
429 return enlist(the_list, str);
433 /*********************************************************************
435 * Function : enlist_unique_header
437 * Description : Make a HTTP header from the two strings name and value,
438 * and append the result into a specified string list,
439 * if & only if there isn't already a header with that name.
442 * 1 : the_list = pointer to list
443 * 2 : name = HTTP header name (e.g. "Content-type")
444 * 3 : value = HTTP header value (e.g. "text/html")
446 * Returns : JB_ERR_OK on success
447 * JB_ERR_MEMORY on out-of-memory error.
448 * On error, the_list will be unchanged.
449 * "Success" does not indicate whether or not the
450 * header was already in the list.
452 *********************************************************************/
453 jb_err enlist_unique_header(struct list *the_list, const char *name,
461 assert(list_is_valid(the_list));
465 length = strlen(name) + 2;
466 if (NULL == (str = (char *)malloc(length + strlen(value) + 1)))
468 return JB_ERR_MEMORY;
471 str[length - 2] = ':';
472 str[length - 1] = ' ';
473 strcpy(str + length, value);
475 result = enlist_unique(the_list, str, length);
479 assert(list_is_valid(the_list));
485 /*********************************************************************
487 * Function : list_remove_all
489 * Description : Remove all entries from a list. On return, the_list
490 * is a valid, empty list. Note that this is similar
491 * to destroy_list(), but the difference is that this
492 * function guarantees that the list structure is still
493 * valid after the call.
496 * 1 : the_list = pointer to list
500 *********************************************************************/
501 void list_remove_all(struct list *the_list)
503 struct list_entry *cur_entry;
504 struct list_entry *next_entry;
507 assert(list_is_valid(the_list));
509 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
511 next_entry = cur_entry->next;
512 freez((char *)cur_entry->str);
516 the_list->first = the_list->last = NULL;
518 assert(list_is_valid(the_list));
522 /*********************************************************************
524 * Function : list_to_text
526 * Description : "Flatten" a string list into 1 long \r\n delimited string,
527 * adding an empty line at the end. NULL entries are ignored.
528 * This function does not change the_list.
531 * 1 : the_list = pointer to list
533 * Returns : NULL on malloc error, else new long string.
534 * Caller must free() it.
536 *********************************************************************/
537 char *list_to_text(const struct list *the_list)
539 struct list_entry *cur_entry;
545 assert(list_is_valid(the_list));
547 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
551 size += strlen(cur_entry->str) + 2;
555 if ((ret = (char *)malloc(size + 1)) == NULL)
564 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
568 strcpy(s, cur_entry->str);
570 *s++ = '\r'; *s++ = '\n';
573 *s++ = '\r'; *s++ = '\n';
579 /*********************************************************************
581 * Function : list_remove_item
583 * Description : Remove a string from a specified string list.
586 * 1 : the_list = pointer to list
587 * 2 : str = string to remove from the list - non-NULL
589 * Returns : Number of times it was removed.
591 *********************************************************************/
592 int list_remove_item(struct list *the_list, const char *str)
594 struct list_entry *prev = NULL;
595 struct list_entry *cur;
596 struct list_entry *next;
600 assert(list_is_valid(the_list));
603 cur = the_list->first;
609 if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
619 the_list->first = next;
621 free((char *)cur->str);
631 the_list->last = prev;
633 assert(list_is_valid(the_list));
639 /*********************************************************************
641 * Function : list_remove_list
643 * Description : Remove all strings in one list from another list.
644 * This is currently a brute-force algorithm
645 * (it compares every pair of strings).
648 * 1 : dest = list to change
649 * 2 : src = list of strings to remove
651 * Returns : Total number of strings removed.
653 *********************************************************************/
654 int list_remove_list(struct list *dest, const struct list *src)
656 struct list_entry *cur;
661 assert(list_is_valid(src));
662 assert(list_is_valid(dest));
664 for (cur = src->first; cur != NULL; cur = cur->next)
666 if (cur->str != NULL)
668 count += list_remove_item(dest, cur->str);
672 assert(list_is_valid(src));
673 assert(list_is_valid(dest));
679 /*********************************************************************
681 * Function : list_duplicate
683 * Description : Copy a string list
686 * 1 : dest = Destination list. Must be a valid list.
687 * All existing entries will be removed.
688 * 1 : src = pointer to source list for copy.
690 * Returns : JB_ERR_OK on success
691 * JB_ERR_MEMORY on out-of-memory error.
692 * On error, dest will be empty.
694 *********************************************************************/
695 jb_err list_duplicate(struct list *dest, const struct list *src)
697 struct list_entry * cur_src;
698 struct list_entry * cur_dest;
702 assert(list_is_valid(src));
703 assert(list_is_valid(dest));
705 list_remove_all(dest);
707 /* Need to process first entry specially so we can set dest->first */
708 cur_src = src->first;
711 cur_dest = dest->first = (struct list_entry *)zalloc(sizeof(*cur_dest));
712 if (cur_dest == NULL)
716 assert(list_is_valid(src));
717 assert(list_is_valid(dest));
719 return JB_ERR_MEMORY;
724 cur_dest->str = strdup(cur_src->str);
725 if (cur_dest->str == NULL)
729 assert(list_is_valid(src));
730 assert(list_is_valid(dest));
732 return JB_ERR_MEMORY;
735 /* else { cur_dest->str = NULL; } - implied by zalloc */
737 /* Now process the rest */
738 for (cur_src = cur_src->next; cur_src; cur_src = cur_src->next)
740 cur_dest = cur_dest->next = (struct list_entry *)zalloc(sizeof(*cur_dest));
741 if (cur_dest == NULL)
745 assert(list_is_valid(src));
746 assert(list_is_valid(dest));
748 return JB_ERR_MEMORY;
752 cur_dest->str = strdup(cur_src->str);
753 if (cur_dest->str == NULL)
757 assert(list_is_valid(src));
758 assert(list_is_valid(dest));
760 return JB_ERR_MEMORY;
763 /* else { cur_dest->str = NULL; } - implied by zalloc */
766 dest->last = cur_dest;
769 assert(list_is_valid(src));
770 assert(list_is_valid(dest));
776 /*********************************************************************
778 * Function : list_append_list_unique
780 * Description : Append a string list to another list.
781 * Duplicate items are not added.
784 * 1 : dest = pointer to destination list for merge.
785 * 2 : src = pointer to source for merge.
787 * Returns : JB_ERR_OK on success
788 * JB_ERR_MEMORY on out-of-memory error.
789 * On error, some (but not all) of src might have
790 * been copied into dest.
792 *********************************************************************/
793 jb_err list_append_list_unique(struct list *dest, const struct list *src)
795 struct list_entry * cur;
799 assert(list_is_valid(src));
800 assert(list_is_valid(dest));
802 for (cur = src->first; cur; cur = cur->next)
806 if (enlist_unique(dest, cur->str, 0))
808 assert(list_is_valid(src));
809 assert(list_is_valid(dest));
811 return JB_ERR_MEMORY;
816 assert(list_is_valid(src));
817 assert(list_is_valid(dest));
823 /*********************************************************************
825 * Function : list_is_empty
827 * Description : Test whether a list is empty. Does not change the list.
830 * 1 : the_list = pointer to list to test.
832 * Returns : Nonzero iff the list contains no entries.
834 *********************************************************************/
835 int list_is_empty(const struct list *the_list)
838 assert(list_is_valid(the_list));
840 return (the_list->first == NULL);
844 /*********************************************************************
848 * Description : Create a new, empty map.
852 * Returns : A new, empty map, or NULL if out of memory.
854 *********************************************************************/
855 struct map *new_map(void)
857 return (struct map *) zalloc(sizeof(struct map));
861 /*********************************************************************
863 * Function : free_map
865 * Description : Free the memory occupied by a map and its
869 * 1 : the_map = map to be freed. May be NULL.
873 *********************************************************************/
874 void free_map(struct map *the_map)
876 struct map_entry *cur_entry;
877 struct map_entry *next_entry;
884 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = next_entry)
886 freez((char *)cur_entry->name);
887 freez((char *)cur_entry->value);
889 next_entry = cur_entry->next;
893 the_map->first = the_map->last = NULL;
899 /*********************************************************************
903 * Description : Add a mapping from given name to given value to a
906 * Note: Since all strings will be free()d in free_map()
907 * later, set the copy flags for constants or
908 * strings that will be independantly free()d.
910 * Note2: This function allows NULL parameters - it
911 * returns JB_ERR_MEMORY in that case.
913 * Note3: If this function returns JB_ERR_MEMORY,
914 * it will free(name) unless you specify
915 * name_needs_copying, and similarly it will
916 * free(value) unless you specify
917 * value_needs_copying.
919 * Due to Note2 and Note3 above, the following code
920 * is legal, and will never crash or leak memory even
921 * if the system runs out of memory:
923 * err = map(mymap, "xyz", 1, html_encode(somestring), 0);
925 * err will be set to JB_ERR_MEMORY if either call runs
926 * out-of-memory. Without these features, you would
927 * need to check the return value of html_encode in the
928 * above example for NULL, which (at least) doubles the
929 * amount of error-checking code needed.
932 * 1 : the_map = map to add to
933 * 2 : name = name to add
934 * 3 : name_needs_copying = flag set if a copy of name should be used
935 * 4 : value = value to add
936 * 5 : value_needs_copying = flag set if a copy of value should be used
938 * Returns : JB_ERR_OK on success
939 * JB_ERR_MEMORY on out-of-memory error.
941 *********************************************************************/
942 jb_err map(struct map *the_map,
943 const char *name, int name_needs_copying,
944 const char *value, int value_needs_copying)
946 struct map_entry *new_entry;
952 || (NULL == (new_entry = zalloc(sizeof(*new_entry)))) )
954 if ((name != NULL) && (!name_needs_copying))
958 if ((value != NULL) && (!value_needs_copying))
962 return JB_ERR_MEMORY;
965 if (name_needs_copying)
967 if (NULL == (name = strdup(name)))
970 if (!value_needs_copying)
974 return JB_ERR_MEMORY;
978 if (value_needs_copying)
980 if (NULL == (value = strdup(value)))
984 return JB_ERR_MEMORY;
988 new_entry->name = name;
989 new_entry->value = value;
990 /* new_entry->next = NULL; - implied by zalloc */
994 the_map->last->next = new_entry;
995 the_map->last = new_entry;
999 the_map->first = new_entry;
1000 the_map->last = new_entry;
1007 /*********************************************************************
1011 * Description : Look up an item with a given name in a map, and
1015 * 1 : the_map = map to look in
1016 * 2 : name = name parameter to look for
1018 * Returns : the value if found, else the empty string.
1019 * Return value is alloced as part of the map, so
1020 * it is freed when the map is destroyed. Caller
1021 * must not free or modify it.
1023 *********************************************************************/
1024 const char *lookup(const struct map *the_map, const char *name)
1026 const struct map_entry *cur_entry;
1031 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
1033 if (!strcmp(name, cur_entry->name))
1035 return cur_entry->value;