-const char list_rcs[] = "$Id: list.c,v 1.15.2.2 2004/05/25 02:04:23 david__schmidt Exp $";
+const char list_rcs[] = "$Id: list.c,v 1.31 2014/10/21 12:01:59 fabiankeil Exp $";
/*********************************************************************
*
- * File : $Source: /cvsroot/ijbswa/current/Attic/list.c,v $
+ * File : $Source: /cvsroot/ijbswa/current/list.c,v $
*
* Purpose : Declares functions to handle lists.
- * Functions declared include:
- * `destroy_list', `enlist' and `list_to_text'
*
- * Copyright : Written by and Copyright (C) 2001 the SourceForge
+ * Copyright : Written by and Copyright (C) 2001-2007 the SourceForge
* Privoxy team. http://www.privoxy.org/
*
* Based on the Internet Junkbuster originally written
* or write to the Free Software Foundation, Inc., 59
* Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*
- * Revisions :
- * $Log: list.c,v $
- * Revision 1.15.2.2 2004/05/25 02:04:23 david__schmidt
- * Removed the "arbitrary" 1000 filter limit in file.c. See tracker #911950.
- *
- * Revision 1.15.2.1 2002/11/28 18:14:54 oes
- * Added unmap function that removes all items with a given
- * name from a map.
- *
- * Revision 1.15 2002/03/26 22:29:55 swa
- * we have a new homepage!
- *
- * Revision 1.14 2002/03/24 13:25:43 swa
- * name change related issues
- *
- * Revision 1.13 2002/03/07 03:46:17 oes
- * Fixed compiler warnings
- *
- * Revision 1.12 2001/10/25 03:40:48 david__schmidt
- * Change in porting tactics: OS/2's EMX porting layer doesn't allow multiple
- * threads to call select() simultaneously. So, it's time to do a real, live,
- * native OS/2 port. See defines for __EMX__ (the porting layer) vs. __OS2__
- * (native). Both versions will work, but using __OS2__ offers multi-threading.
- *
- * Revision 1.11 2001/10/23 21:21:03 jongfoster
- * New error handling - error codes are now jb_errs, not ints.
- * Changed the way map() handles out-of-memory, to dramatically
- * reduce the amount of error-checking clutter needed.
- *
- * Revision 1.10 2001/09/16 17:30:24 jongfoster
- * Fixing a compiler warning.
- *
- * Revision 1.9 2001/09/16 13:20:29 jongfoster
- * Rewrite of list library. Now has seperate header and list_entry
- * structures. Also added a large sprinking of assert()s to the list
- * code.
- *
- * Revision 1.8 2001/08/07 14:00:20 oes
- * Fixed comment
- *
- * Revision 1.7 2001/08/05 16:06:20 jongfoster
- * Modifiying "struct map" so that there are now separate header and
- * "map_entry" structures. This means that functions which modify a
- * map no longer need to return a pointer to the modified map.
- * Also, it no longer reverses the order of the entries (which may be
- * important with some advanced template substitutions).
- *
- * Revision 1.6 2001/07/31 14:44:51 oes
- * list_to_text() now appends empty line at end
- *
- * Revision 1.5 2001/06/29 21:45:41 oes
- * Indentation, CRLF->LF, Tab-> Space
- *
- * Revision 1.4 2001/06/29 13:30:22 oes
- * - Added Convenience function enlist_unique_header(),
- * which takes the Header name and value as separate
- * arguments and thus saves the pain of sprintf()ing
- * and determining the Header name length to enlist_unique
- * - Improved comments
- * - Removed logentry from cancelled commit
- *
- * Revision 1.3 2001/06/03 19:12:24 oes
- * functions for new struct map, extended enlist_unique
- *
- * Revision 1.2 2001/06/01 18:49:17 jongfoster
- * Replaced "list_share" with "list" - the tiny memory gain was not
- * worth the extra complexity.
- *
- * Revision 1.1 2001/05/31 21:11:53 jongfoster
- * - Moved linked list support to new "list.c" file.
- * Structure definitions are still in project.h,
- * function prototypes are now in "list.h".
- * - Added support for "struct list_share", which is identical
- * to "struct list" except it saves memory by not duplicating
- * the strings. Obviously, this only works if there is some
- * other way of managing the memory used by the strings.
- * (These list_share lists are used for lists which last
- * for only 1 request, and where all the list entries are
- * just coming directly from entries in the actionsfile.)
- * Note that you still need to destroy list_share lists
- * properly to free the nodes - it's only the strings
- * which are shared.
- *
- *
*********************************************************************/
-\f
+
#include "config.h"
/*********************************************************************
*
- * Function : list_init
+ * Function : init_list
*
* Description : Create a new, empty list in user-allocated memory.
* Caller should allocate a "struct list" variable,
#if 1
const struct list_entry *cur_entry;
const struct list_entry *last_entry = NULL;
- int length = 0;
+ int entry = 0;
assert(the_list);
* Just check that this string can be accessed - i.e. it's a valid
* pointer.
*/
- strlen(cur_entry->str);
+ (void)strlen(cur_entry->str);
}
/*
* Check for looping back to first
*/
- if ((length != 0) && (cur_entry == the_list->first))
+ if ((entry++ != 0) && (cur_entry == the_list->first))
{
return 0;
}
/*
- * Arbitrarily limit length to prevent infinite loops.
+ * Arbitrarily limit list length to prevent infinite loops.
* Note that the 1000 limit was hit by a real user in tracker 911950;
- * removing it for now. Symptoms of a real circular reference will
- * include 100% CPU usage, I'd imagine. It'll be obvious, anyway.
- */
+ * removing it for now. Real circular references should eventually
+ * be caught by the check above, anyway.
+ */
/*
- if (++length > 1000)
- {
+ if (entry > 1000)
+ {
return 0;
- }
- */
+ }
+ */
/*
* Check this isn't marked as the last entry, unless of course it's
{
for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
{
- if ( (cur_entry->str != NULL)
+ if ((cur_entry->str != NULL)
&& (0 == strncmp(str, cur_entry->str, num_significant_chars)))
{
/* Already there */
/* Test whole string */
for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
{
- if ( (cur_entry->str != NULL) && (0 == strcmp(str, cur_entry->str)))
+ if ((cur_entry->str != NULL) && (0 == strcmp(str, cur_entry->str)))
{
/* Already there */
return JB_ERR_OK;
jb_err enlist_unique_header(struct list *the_list, const char *name,
const char *value)
{
- size_t length;
- jb_err result;
- char *str;
+ jb_err result = JB_ERR_MEMORY;
+ char *header;
+ size_t header_size;
assert(the_list);
assert(list_is_valid(the_list));
assert(name);
assert(value);
- length = strlen(name) + 2;
- if (NULL == (str = (char *)malloc(length + strlen(value) + 1)))
- {
- return JB_ERR_MEMORY;
- }
- strcpy(str, name);
- str[length - 2] = ':';
- str[length - 1] = ' ';
- strcpy(str + length, value);
+ /* + 2 for the ': ', + 1 for the \0 */
+ header_size = strlen(name) + 2 + strlen(value) + 1;
+ header = (char *)malloc(header_size);
- result = enlist_unique(the_list, str, length);
-
- free(str);
+ if (NULL != header)
+ {
+ const size_t bytes_to_compare = strlen(name) + 2;
+ char *p = header;
- assert(list_is_valid(the_list));
+ snprintf(header, header_size, "%s: %s", name, value);
+ /*
+ * The trailing "\r\n" is added by list_to_text(),
+ * if the caller passed them anyway, cut the header
+ * at the first one or dump core if this is a debug
+ * build.
+ */
+ do
+ {
+ if ((*p == '\r') || (*p == '\n'))
+ {
+ assert(*p != '\r');
+ assert(*p != '\n');
+ *p = '\0';
+ }
+ } while (*p++);
+ result = enlist_unique(the_list, header, bytes_to_compare);
+ free(header);
+ assert(list_is_valid(the_list));
+ }
return result;
* adding an empty line at the end. NULL entries are ignored.
* This function does not change the_list.
*
+ * XXX: Should probably be renamed as it's only
+ * useful (and used) to flatten header lists.
+ *
* Parameters :
* 1 : the_list = pointer to list
*
char *list_to_text(const struct list *the_list)
{
struct list_entry *cur_entry;
- char *ret = NULL;
- char *s;
- size_t size = 2;
+ char *text;
+ size_t text_length;
+ char *cursor;
+ size_t bytes_left;
assert(the_list);
assert(list_is_valid(the_list));
- for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
+ /*
+ * Calculate the length of the final text.
+ * '2' because of the '\r\n' at the end of
+ * each string and at the end of the text.
+ */
+ text_length = 2;
+ for (cur_entry = the_list->first; cur_entry; cur_entry = cur_entry->next)
{
if (cur_entry->str)
{
- size += strlen(cur_entry->str) + 2;
+ text_length += strlen(cur_entry->str) + 2;
}
}
- if ((ret = (char *)malloc(size + 1)) == NULL)
+ bytes_left = text_length + 1;
+
+ text = (char *)malloc(bytes_left);
+ if (NULL == text)
{
return NULL;
}
- ret[size] = '\0';
-
- s = ret;
+ cursor = text;
- for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
+ for (cur_entry = the_list->first; cur_entry; cur_entry = cur_entry->next)
{
if (cur_entry->str)
{
- strcpy(s, cur_entry->str);
- s += strlen(s);
- *s++ = '\r'; *s++ = '\n';
+ const int written = snprintf(cursor, bytes_left, "%s\r\n", cur_entry->str);
+
+ assert(written > 0);
+ assert(written < bytes_left);
+
+ bytes_left -= (size_t)written;
+ cursor += (size_t)written;
}
}
- *s++ = '\r'; *s++ = '\n';
- return ret;
+ assert(bytes_left == 3);
+
+ *cursor++ = '\r';
+ *cursor++ = '\n';
+ *cursor = '\0';
+
+ assert(text_length == cursor - text);
+ assert(text[text_length] == '\0');
+
+ return text;
}
* Parameters :
* 1 : the_list = pointer to list to test.
*
- * Returns : Nonzero iff the list contains no entries.
+ * Returns : Nonzero if the list contains no entries.
*
*********************************************************************/
int list_is_empty(const struct list *the_list)
}
+/*********************************************************************
+ *
+ * Function : list_contains_item
+ *
+ * Description : Tests whether a list item is already set.
+ * Does not change the list.
+ *
+ * Parameters :
+ * 1 : the_list = list to search in
+ * 2 : str = string to search for
+ *
+ * Returns : TRUE if the item was found,
+ * FALSE otherwise.
+ *
+ *********************************************************************/
+int list_contains_item(const struct list *the_list, const char *str)
+{
+ struct list_entry *entry;
+
+ assert(the_list);
+ assert(list_is_valid(the_list));
+ assert(str);
+
+ for (entry = the_list->first; entry != NULL; entry = entry->next)
+ {
+ if (entry->str == NULL)
+ {
+ /*
+ * NULL pointers are allowed in some lists.
+ * For example for csp->headers in case a
+ * header was removed.
+ */
+ continue;
+ }
+
+ if (0 == strcmp(str, entry->str))
+ {
+ /* Item found */
+ return TRUE;
+ }
+ }
+
+ return FALSE;
+}
+
+
/*********************************************************************
*
* Function : new_map
*
* Description : Create a new, empty map.
+ * Causes program exit if the memory allocation fails.
*
* Parameters : N/A
*
- * Returns : A new, empty map, or NULL if out of memory.
+ * Returns : A new, empty map
*
*********************************************************************/
struct map *new_map(void)
{
- return (struct map *) zalloc(sizeof(struct map));
+ struct map *empty_map = zalloc(sizeof(struct map));
+
+ if (NULL == empty_map)
+ {
+ exit(1);
+ }
+
+ return empty_map;
+
}
* Function : free_map
*
* Description : Free the memory occupied by a map and its
- * depandant strings
+ * dependent strings
*
* Parameters :
* 1 : the_map = map to be freed. May be NULL.
*
* Note: Since all strings will be free()d in free_map()
* later, set the copy flags for constants or
- * strings that will be independantly free()d.
+ * strings that will be independently free()d.
*
* Note2: This function allows NULL parameters - it
* returns JB_ERR_MEMORY in that case.
if ( (NULL == value)
|| (NULL == name)
- || (NULL == (new_entry = zalloc(sizeof(*new_entry)))) )
+ || (NULL == (new_entry = zalloc(sizeof(*new_entry)))))
{
if ((name != NULL) && (!name_needs_copying))
{
assert(the_map);
assert(name);
-
- last_entry = the_map->first;
+
+ last_entry = NULL;
for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
{
}
/*
- * Update the map's last pointer
+ * Update the map's last pointer
*/
if (cur_entry == the_map->last)
{
the_map->last = last_entry;
}
-
+
/*
* Free the map_entry
*/
freez(cur_entry->name);
freez(cur_entry->value);
freez(cur_entry);
-
+ if (last_entry == NULL)
+ {
+ /* The map only had a single entry which has just been removed. */
+ break;
+ }
cur_entry = last_entry;
}
else