1 const char list_rcs[] = "$Id: list.c,v 1.9 2001/09/16 13:20:29 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.9 2001/09/16 13:20:29 jongfoster
38 * Rewrite of list library. Now has seperate header and list_entry
39 * structures. Also added a large sprinking of assert()s to the list
42 * Revision 1.8 2001/08/07 14:00:20 oes
45 * Revision 1.7 2001/08/05 16:06:20 jongfoster
46 * Modifiying "struct map" so that there are now separate header and
47 * "map_entry" structures. This means that functions which modify a
48 * map no longer need to return a pointer to the modified map.
49 * Also, it no longer reverses the order of the entries (which may be
50 * important with some advanced template substitutions).
52 * Revision 1.6 2001/07/31 14:44:51 oes
53 * list_to_text() now appends empty line at end
55 * Revision 1.5 2001/06/29 21:45:41 oes
56 * Indentation, CRLF->LF, Tab-> Space
58 * Revision 1.4 2001/06/29 13:30:22 oes
59 * - Added Convenience function enlist_unique_header(),
60 * which takes the Header name and value as separate
61 * arguments and thus saves the pain of sprintf()ing
62 * and determining the Header name length to enlist_unique
64 * - Removed logentry from cancelled commit
66 * Revision 1.3 2001/06/03 19:12:24 oes
67 * functions for new struct map, extended enlist_unique
69 * Revision 1.2 2001/06/01 18:49:17 jongfoster
70 * Replaced "list_share" with "list" - the tiny memory gain was not
71 * worth the extra complexity.
73 * Revision 1.1 2001/05/31 21:11:53 jongfoster
74 * - Moved linked list support to new "list.c" file.
75 * Structure definitions are still in project.h,
76 * function prototypes are now in "list.h".
77 * - Added support for "struct list_share", which is identical
78 * to "struct list" except it saves memory by not duplicating
79 * the strings. Obviously, this only works if there is some
80 * other way of managing the memory used by the strings.
81 * (These list_share lists are used for lists which last
82 * for only 1 request, and where all the list entries are
83 * just coming directly from entries in the actionsfile.)
84 * Note that you still need to destroy list_share lists
85 * properly to free the nodes - it's only the strings
89 *********************************************************************/
95 /* FIXME: The following headers are not needed for Win32. Are they
96 * needed on other platforms?
99 #include <sys/types.h>
113 #include "miscutil.h"
115 const char list_h_rcs[] = LIST_H_VERSION;
118 static int list_is_valid (const struct list *the_list);
121 /*********************************************************************
123 * Function : list_init
125 * Description : Create a new, empty list in user-allocated memory.
126 * Caller should allocate a "struct list" variable,
127 * then pass it to this function.
128 * (Implementation note: Rather than calling this
129 * function, you can also just memset the memory to
130 * zero, e.g. if you have a larger structure you
131 * want to initialize quickly. However, that isn't
132 * really good design.)
135 * 1 : the_list = pointer to list
139 *********************************************************************/
140 void init_list(struct list *the_list)
142 memset(the_list, '\0', sizeof(*the_list));
146 /*********************************************************************
148 * Function : destroy_list
150 * Description : Destroy a string list (opposite of list_init).
151 * On return, the memory used by the list entries has
152 * been freed, but not the memory used by the_list
153 * itself. You should not re-use the_list without
154 * calling list_init().
156 * (Implementation note: You *can* reuse the_list
157 * without calling list_init(), but please don't.
158 * If you want to remove all entries from a list
159 * and still have a usable list, then use
160 * list_remove_all().)
163 * 1 : the_list = pointer to list
167 *********************************************************************/
168 void destroy_list (struct list *the_list)
170 struct list_entry *cur_entry, *next_entry;
174 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
176 next_entry = cur_entry->next;
177 freez((char *)cur_entry->str);
181 the_list->first = NULL;
182 the_list->last = NULL;
186 /*********************************************************************
188 * Function : list_is_valid
190 * Description : Check that a string list is valid. The intended
191 * usage is "assert(list_is_valid(the_list))".
192 * Currently this checks that "the_list->last"
193 * is correct, and that the list dosn't contain
194 * circular references. It is likely to crash if
195 * it's passed complete garbage.
198 * 1 : the_list = pointer to list. Must be non-null.
200 * Returns : 1 if list is valid, 0 otherwise.
202 *********************************************************************/
203 static int list_is_valid (const struct list *the_list)
206 * If you don't want this check, just change the line below
207 * from "#if 1" to "#if 0".
210 const struct list_entry *cur_entry;
211 const struct list_entry *last_entry = NULL;
216 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
218 last_entry = cur_entry;
223 * Just check that this string can be accessed - i.e. it's a valid
226 strlen(cur_entry->str);
230 * Check for looping back to first
232 if ((length != 0) && (cur_entry == the_list->first))
238 * Arbitrarily limit length to prevent infinite loops.
246 * Check this isn't marked as the last entry, unless of course it's
247 * *really* the last entry.
249 if ((the_list->last == cur_entry) && (cur_entry->next != NULL))
251 /* This is the last entry, but there's data after it !!?? */
256 return (the_list->last == last_entry);
262 /*********************************************************************
266 * Description : Append a string into a specified string list.
269 * 1 : the_list = pointer to list
270 * 2 : str = string to add to the list (maybe NULL)
272 * Returns : 0 on success, nonzero on out-of-memory error. On
273 * error, the_list will be unchanged.
275 *********************************************************************/
276 int enlist(struct list *the_list, const char *str)
278 struct list_entry *cur;
281 assert(list_is_valid(the_list));
283 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
290 if (NULL == (cur->str = strdup(str)))
296 /* else { cur->str = NULL; } - implied by zalloc */
298 /* cur->next = NULL; - implied by zalloc */
302 the_list->last->next = cur;
303 the_list->last = cur;
307 the_list->first = cur;
308 the_list->last = cur;
311 assert(list_is_valid(the_list));
316 /*********************************************************************
318 * Function : enlist_first
320 * Description : Append a string as first element into a specified
324 * 1 : the_list = pointer to list
325 * 2 : str = string to add to the list (maybe NULL)
327 * Returns : 0 on success, nonzero on out-of-memory error. On
328 * error, the_list will be unchanged.
330 *********************************************************************/
331 int enlist_first(struct list *the_list, const char *str)
333 struct list_entry *cur;
336 assert(list_is_valid(the_list));
338 if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
345 if (NULL == (cur->str = strdup(str)))
351 /* else { cur->str = NULL; } - implied by zalloc */
353 cur->next = the_list->first;
355 the_list->first = cur;
356 if (the_list->last == NULL)
358 the_list->last = cur;
361 assert(list_is_valid(the_list));
366 /*********************************************************************
368 * Function : enlist_unique
370 * Description : Append a string into a specified string list,
371 * if & only if it's not there already.
372 * If the num_significant_chars argument is nonzero,
373 * only compare up to the nth character.
376 * 1 : the_list = pointer to list
377 * 2 : str = string to add to the list
378 * 3 : num_significant_chars = number of chars to use
379 * for uniqueness test, or 0 to require an exact match.
381 * Returns : 0 on success, nonzero on out-of-memory error. On
382 * error, the_list will be unchanged. "Success"
383 * does not indicate whether or not the item was
384 * already in the list.
386 *********************************************************************/
387 int enlist_unique(struct list *the_list, const char *str,
388 int num_significant_chars)
390 struct list_entry *cur_entry;
393 assert(list_is_valid(the_list));
395 assert(num_significant_chars >= 0);
396 assert((size_t)num_significant_chars <= strlen(str));
398 if (num_significant_chars > 0)
400 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
402 if ( (cur_entry->str != NULL)
403 && (0 == strncmp(str, cur_entry->str, num_significant_chars)))
412 /* Test whole string */
413 for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
415 if ( (cur_entry->str != NULL) && (0 == strcmp(str, cur_entry->str)))
423 return enlist(the_list, str);
427 /*********************************************************************
429 * Function : enlist_unique_header
431 * Description : Make a HTTP header from the two strings name and value,
432 * and append the result into a specified string list,
433 * if & only if there isn't already a header with that name.
436 * 1 : the_list = pointer to list
437 * 2 : name = HTTP header name (e.g. "Content-type")
438 * 3 : value = HTTP header value (e.g. "text/html")
440 * Returns : 0 on success, nonzero on out-of-memory error. On
441 * error, the_list will be unchanged. "Success"
442 * does not indicate whether or not the header was
443 * already in the list.
445 *********************************************************************/
446 int enlist_unique_header(struct list *the_list, const char *name, const char *value)
453 assert(list_is_valid(the_list));
457 length = strlen(name) + 2;
458 if (NULL == (str = (char *)malloc(length + strlen(value) + 1)))
463 str[length - 2] = ':';
464 str[length - 1] = ' ';
465 strcpy(str + length, value);
467 result = enlist_unique(the_list, str, length);
471 assert(list_is_valid(the_list));
477 /*********************************************************************
479 * Function : list_remove_all
481 * Description : Remove all entries from a list. On return, the_list
482 * is a valid, empty list. Note that this is similar
483 * to destroy_list(), but the difference is that this
484 * function guarantees that the list structure is still
485 * valid after the call.
488 * 1 : the_list = pointer to list
492 *********************************************************************/
493 void list_remove_all(struct list *the_list)
495 struct list_entry *cur_entry;
496 struct list_entry *next_entry;
499 assert(list_is_valid(the_list));
501 for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
503 next_entry = cur_entry->next;
504 freez((char *)cur_entry->str);
508 the_list->first = the_list->last = NULL;
510 assert(list_is_valid(the_list));
514 /*********************************************************************
516 * Function : list_to_text
518 * Description : "Flatten" a string list into 1 long \r\n delimited string,
519 * adding an empty line at the end. NULL entries are ignored.
520 * This function does not change the_list.
523 * 1 : the_list = pointer to list
525 * Returns : NULL on malloc error, else new long string.
526 * Caller must free() it.
528 *********************************************************************/
529 char *list_to_text(const struct list *the_list)
531 struct list_entry *cur_entry;
537 assert(list_is_valid(the_list));
539 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
543 size += strlen(cur_entry->str) + 2;
547 if ((ret = (char *)malloc(size + 1)) == NULL)
556 for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
560 strcpy(s, cur_entry->str);
562 *s++ = '\r'; *s++ = '\n';
565 *s++ = '\r'; *s++ = '\n';
571 /*********************************************************************
573 * Function : list_remove_item
575 * Description : Remove a string from a specified string list.
578 * 1 : the_list = pointer to list
579 * 2 : str = string to remove from the list - non-NULL
581 * Returns : Number of times it was removed.
583 *********************************************************************/
584 int list_remove_item(struct list *the_list, const char *str)
586 struct list_entry *prev = NULL;
587 struct list_entry *cur;
588 struct list_entry *next;
592 assert(list_is_valid(the_list));
595 cur = the_list->first;
601 if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
611 the_list->first = next;
613 free((char *)cur->str);
623 the_list->last = prev;
625 assert(list_is_valid(the_list));
631 /*********************************************************************
633 * Function : list_remove_list
635 * Description : Remove all strings in one list from another list.
636 * This is currently a brute-force algorithm
637 * (it compares every pair of strings).
640 * 1 : dest = list to change
641 * 2 : src = list of strings to remove
643 * Returns : Total number of strings removed.
645 *********************************************************************/
646 int list_remove_list(struct list *dest, const struct list *src)
648 struct list_entry *cur;
653 assert(list_is_valid(src));
654 assert(list_is_valid(dest));
656 for (cur = src->first; cur != NULL; cur = cur->next)
658 if (cur->str != NULL)
660 count += list_remove_item(dest, cur->str);
664 assert(list_is_valid(src));
665 assert(list_is_valid(dest));
671 /*********************************************************************
673 * Function : list_duplicate
675 * Description : Copy a string list
678 * 1 : dest = Destination list. Must be a valid list.
679 * All existing entries will be removed.
680 * 1 : src = pointer to source list for copy.
682 * Returns : 0 on success, nonzero on error. On error, dest
685 *********************************************************************/
686 int list_duplicate(struct list *dest, const struct list *src)
688 struct list_entry * cur_src;
689 struct list_entry * cur_dest;
693 assert(list_is_valid(src));
694 assert(list_is_valid(dest));
696 list_remove_all(dest);
698 /* Need to process first entry specially so we can set dest->first */
699 cur_src = src->first;
702 cur_dest = dest->first = (struct list_entry *)zalloc(sizeof(*cur_dest));
703 if (cur_dest == NULL)
707 assert(list_is_valid(src));
708 assert(list_is_valid(dest));
715 cur_dest->str = strdup(cur_src->str);
716 if (cur_dest->str == NULL)
720 assert(list_is_valid(src));
721 assert(list_is_valid(dest));
726 /* else { cur_dest->str = NULL; } - implied by zalloc */
728 /* Now process the rest */
729 for (cur_src = cur_src->next; cur_src; cur_src = cur_src->next)
731 cur_dest = cur_dest->next = (struct list_entry *)zalloc(sizeof(*cur_dest));
732 if (cur_dest == NULL)
736 assert(list_is_valid(src));
737 assert(list_is_valid(dest));
743 cur_dest->str = strdup(cur_src->str);
744 if (cur_dest->str == NULL)
748 assert(list_is_valid(src));
749 assert(list_is_valid(dest));
754 /* else { cur_dest->str = NULL; } - implied by zalloc */
757 dest->last = cur_dest;
760 assert(list_is_valid(src));
761 assert(list_is_valid(dest));
767 /*********************************************************************
769 * Function : list_append_list_unique
771 * Description : Append a string list to another list.
772 * Duplicate items are not added.
775 * 1 : dest = pointer to destination list for merge.
776 * 2 : src = pointer to source for merge.
778 * Returns : 0 on success, nonzero on out-of-memory error.
779 * On error, some (but not all) of src might have
780 * been copied into dest.
782 *********************************************************************/
783 int list_append_list_unique(struct list *dest, const struct list *src)
785 struct list_entry * cur;
789 assert(list_is_valid(src));
790 assert(list_is_valid(dest));
792 for (cur = src->first; cur; cur = cur->next)
796 if (enlist_unique(dest, cur->str, 0))
798 assert(list_is_valid(src));
799 assert(list_is_valid(dest));
806 assert(list_is_valid(src));
807 assert(list_is_valid(dest));
813 /*********************************************************************
815 * Function : list_is_empty
817 * Description : Test whether a list is empty. Does not change the list.
820 * 1 : the_list = pointer to list to test.
822 * Returns : Nonzero iff the list contains no entries.
824 *********************************************************************/
825 int list_is_empty(const struct list *the_list)
828 assert(list_is_valid(the_list));
830 return (the_list->first == NULL);
834 /*********************************************************************
838 * Description : Create a new, empty map.
842 * Returns : A new, empty map, or NULL if out of memory.
844 *********************************************************************/
845 struct map *new_map(void)
847 return (struct map *) zalloc(sizeof(struct map));
851 /*********************************************************************
853 * Function : free_map
855 * Description : Free the memory occupied by a map and its
859 * 1 : the_map = map to be freed. May be NULL.
863 *********************************************************************/
864 void free_map(struct map *the_map)
866 struct map_entry *cur_entry;
867 struct map_entry *next_entry;
874 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = next_entry)
876 freez((char *)cur_entry->name);
877 freez((char *)cur_entry->value);
879 next_entry = cur_entry->next;
883 the_map->first = the_map->last = NULL;
889 /*********************************************************************
893 * Description : Add a mapping from given name to given value to a
896 * Note: Since all strings will be free()d in free_map()
897 * later, set the copy flags for constants or
898 * strings that will be independantly free()d.
901 * 1 : the_map = map to add to
902 * 2 : name = name to add
903 * 3 : name_needs_copying = flag set if a copy of name should be used
904 * 4 : value = value to add
905 * 5 : value_needs_copying = flag set if a copy of value should be used
907 * Returns : 0 on success, nonzero on out-of-memory error.
909 *********************************************************************/
910 int map(struct map *the_map,
911 const char *name, int name_needs_copying,
912 const char *value, int value_needs_copying)
914 struct map_entry *new_entry;
920 if (NULL == (new_entry = zalloc(sizeof(*new_entry))))
925 if (name_needs_copying)
927 if (NULL == (name = strdup(name)))
934 if (value_needs_copying)
936 if (NULL == (value = strdup(value)))
938 if (name_needs_copying)
947 new_entry->name = name;
948 new_entry->value = value;
949 /* new_entry->next = NULL; - implied by zalloc */
953 the_map->last->next = new_entry;
954 the_map->last = new_entry;
958 the_map->first = new_entry;
959 the_map->last = new_entry;
966 /*********************************************************************
970 * Description : Look up an item with a given name in a map, and
974 * 1 : the_map = map to look in
975 * 2 : name = name parameter to look for
977 * Returns : the value if found, else the empty string.
978 * Return value is alloced as part of the map, so
979 * it is freed when the map is destroyed. Caller
980 * must not free or modify it.
982 *********************************************************************/
983 const char *lookup(const struct map *the_map, const char *name)
985 const struct map_entry *cur_entry;
990 for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
992 if (!strcmp(name, cur_entry->name))
994 return cur_entry->value;