-const char list_rcs[] = "$Id: list.c,v 1.3 2001/06/03 19:12:24 oes Exp $";
+const char list_rcs[] = "$Id: list.c,v 1.31 2014/10/21 12:01:59 fabiankeil Exp $";
/*********************************************************************
*
* 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
- * IJBSWA team. http://ijbswa.sourceforge.net
+ * Copyright : Written by and Copyright (C) 2001-2007 the SourceForge
+ * Privoxy team. http://www.privoxy.org/
*
* Based on the Internet Junkbuster originally written
- * by and Copyright (C) 1997 Anonymous Coders and
+ * by and Copyright (C) 1997 Anonymous Coders and
* Junkbusters Corporation. http://www.junkbusters.com
*
- * This program is free software; you can redistribute it
+ * This program is free software; you can redistribute it
* and/or modify it under the terms of the GNU General
* Public License as published by the Free Software
* Foundation; either version 2 of the License, or (at
* 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.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"
+#ifndef _WIN32
+/* FIXME: The following headers are not needed for Win32. Are they
+ * needed on other platforms?
+ */
#include <stdio.h>
#include <sys/types.h>
#include <stdlib.h>
#include <ctype.h>
+#endif
#include <string.h>
-#ifndef _WIN32
+#if !defined(_WIN32) && !defined(__OS2__)
#include <unistd.h>
#endif
+#include <assert.h>
+
#include "project.h"
-#include "jcc.h"
#include "list.h"
#include "miscutil.h"
const char list_h_rcs[] = LIST_H_VERSION;
+
+static int list_is_valid (const struct list *the_list);
+
+
+/*********************************************************************
+ *
+ * Function : init_list
+ *
+ * Description : Create a new, empty list in user-allocated memory.
+ * Caller should allocate a "struct list" variable,
+ * then pass it to this function.
+ * (Implementation note: Rather than calling this
+ * function, you can also just memset the memory to
+ * zero, e.g. if you have a larger structure you
+ * want to initialize quickly. However, that isn't
+ * really good design.)
+ *
+ * Parameters :
+ * 1 : the_list = pointer to list
+ *
+ * Returns : N/A
+ *
+ *********************************************************************/
+void init_list(struct list *the_list)
+{
+ memset(the_list, '\0', sizeof(*the_list));
+}
+
+
+/*********************************************************************
+ *
+ * Function : destroy_list
+ *
+ * Description : Destroy a string list (opposite of list_init).
+ * On return, the memory used by the list entries has
+ * been freed, but not the memory used by the_list
+ * itself. You should not re-use the_list without
+ * calling list_init().
+ *
+ * (Implementation note: You *can* reuse the_list
+ * without calling list_init(), but please don't.
+ * If you want to remove all entries from a list
+ * and still have a usable list, then use
+ * list_remove_all().)
+ *
+ * Parameters :
+ * 1 : the_list = pointer to list
+ *
+ * Returns : N/A
+ *
+ *********************************************************************/
+void destroy_list (struct list *the_list)
+{
+ struct list_entry *cur_entry, *next_entry;
+
+ assert(the_list);
+
+ for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
+ {
+ next_entry = cur_entry->next;
+ freez(cur_entry->str);
+ free(cur_entry);
+ }
+
+ the_list->first = NULL;
+ the_list->last = NULL;
+}
+
+
+/*********************************************************************
+ *
+ * Function : list_is_valid
+ *
+ * Description : Check that a string list is valid. The intended
+ * usage is "assert(list_is_valid(the_list))".
+ * Currently this checks that "the_list->last"
+ * is correct, and that the list dosn't contain
+ * circular references. It is likely to crash if
+ * it's passed complete garbage.
+ *
+ * Parameters :
+ * 1 : the_list = pointer to list. Must be non-null.
+ *
+ * Returns : 1 if list is valid, 0 otherwise.
+ *
+ *********************************************************************/
+static int list_is_valid (const struct list *the_list)
+{
+ /*
+ * If you don't want this check, just change the line below
+ * from "#if 1" to "#if 0".
+ */
+#if 1
+ const struct list_entry *cur_entry;
+ const struct list_entry *last_entry = NULL;
+ int entry = 0;
+
+ assert(the_list);
+
+ for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
+ {
+ last_entry = cur_entry;
+
+ if (cur_entry->str)
+ {
+ /*
+ * Just check that this string can be accessed - i.e. it's a valid
+ * pointer.
+ */
+ (void)strlen(cur_entry->str);
+ }
+
+ /*
+ * Check for looping back to first
+ */
+ if ((entry++ != 0) && (cur_entry == the_list->first))
+ {
+ return 0;
+ }
+
+ /*
+ * 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. Real circular references should eventually
+ * be caught by the check above, anyway.
+ */
+ /*
+ if (entry > 1000)
+ {
+ return 0;
+ }
+ */
+
+ /*
+ * Check this isn't marked as the last entry, unless of course it's
+ * *really* the last entry.
+ */
+ if ((the_list->last == cur_entry) && (cur_entry->next != NULL))
+ {
+ /* This is the last entry, but there's data after it !!?? */
+ return 0;
+ }
+ }
+
+ return (the_list->last == last_entry);
+#else
+ return 1;
+#endif
+}
+
/*********************************************************************
*
* Function : enlist
* Description : Append a string into a specified string list.
*
* Parameters :
- * 1 : header = pointer to list 'dummy' header
+ * 1 : the_list = pointer to list
* 2 : str = string to add to the list (maybe NULL)
*
- * Returns : N/A
+ * Returns : JB_ERR_OK on success
+ * JB_ERR_MEMORY on out-of-memory error.
+ * On error, the_list will be unchanged.
*
*********************************************************************/
-void enlist(struct list *header, const char *str)
+jb_err enlist(struct list *the_list, const char *str)
{
- struct list *cur = (struct list *)malloc(sizeof(*cur));
- struct list *last;
+ struct list_entry *cur;
- if (cur)
+ assert(the_list);
+ assert(list_is_valid(the_list));
+
+ if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
{
- cur->str = (str ? strdup(str) : NULL);
- cur->next = NULL;
+ return JB_ERR_MEMORY;
+ }
- last = header->last;
- if (last == NULL)
+ if (str)
+ {
+ if (NULL == (cur->str = strdup(str)))
{
- last = header;
+ free(cur);
+ return JB_ERR_MEMORY;
}
+ }
+ /* else { cur->str = NULL; } - implied by zalloc */
+
+ /* cur->next = NULL; - implied by zalloc */
- last->next = cur;
- header->last = cur;
+ if (the_list->last)
+ {
+ the_list->last->next = cur;
+ the_list->last = cur;
+ }
+ else
+ {
+ the_list->first = cur;
+ the_list->last = cur;
}
+ assert(list_is_valid(the_list));
+ return JB_ERR_OK;
}
* string list.
*
* Parameters :
- * 1 : header = pointer to list 'dummy' header
+ * 1 : the_list = pointer to list
* 2 : str = string to add to the list (maybe NULL)
*
- * Returns : N/A
+ * Returns : JB_ERR_OK on success
+ * JB_ERR_MEMORY on out-of-memory error.
+ * On error, the_list will be unchanged.
*
*********************************************************************/
-void enlist_first(struct list *header, const char *str)
+jb_err enlist_first(struct list *the_list, const char *str)
{
- struct list *cur = (struct list *)malloc(sizeof(*cur));
+ struct list_entry *cur;
- if (cur)
+ assert(the_list);
+ assert(list_is_valid(the_list));
+
+ if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
{
- cur->str = (str ? strdup(str) : NULL);
- cur->next = header->next;
+ return JB_ERR_MEMORY;
+ }
- header->next = cur;
- if (header->last == NULL)
+ if (str)
+ {
+ if (NULL == (cur->str = strdup(str)))
{
- header->last = cur;
+ free(cur);
+ return JB_ERR_MEMORY;
}
}
+ /* else { cur->str = NULL; } - implied by zalloc */
+
+ cur->next = the_list->first;
+
+ the_list->first = cur;
+ if (the_list->last == NULL)
+ {
+ the_list->last = cur;
+ }
+ assert(list_is_valid(the_list));
+ return JB_ERR_OK;
}
*
* Description : Append a string into a specified string list,
* if & only if it's not there already.
- * If the n argument is nonzero, only compare up to
- * the nth character.
+ * If the num_significant_chars argument is nonzero,
+ * only compare up to the nth character.
*
* Parameters :
- * 1 : header = pointer to list 'dummy' header
- * 2 : str = string to add to the list (maybe NULL)
- * 3 : n = number of chars to use for uniqueness test
+ * 1 : the_list = pointer to list
+ * 2 : str = string to add to the list
+ * 3 : num_significant_chars = number of chars to use
+ * for uniqueness test, or 0 to require an exact match.
*
- * Returns : N/A
+ * Returns : JB_ERR_OK on success
+ * JB_ERR_MEMORY on out-of-memory error.
+ * On error, the_list will be unchanged.
+ * "Success" does not indicate whether or not the
+ * item was already in the list.
*
*********************************************************************/
-void enlist_unique(struct list *header, const char *str, int n)
+jb_err enlist_unique(struct list *the_list, const char *str,
+ size_t num_significant_chars)
{
- struct list *last;
- struct list *cur = header->next;
+ struct list_entry *cur_entry;
- while (cur != NULL)
+ assert(the_list);
+ assert(list_is_valid(the_list));
+ assert(str);
+ assert(num_significant_chars >= 0);
+ assert(num_significant_chars <= strlen(str));
+
+ if (num_significant_chars > 0)
{
- if ((cur->str != NULL) && (
- (n && (0 == strncmp(str, cur->str, n))) ||
- (!n && (0 == strcmp(str, cur->str)))))
+ for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
{
- /* Already there */
- return;
+ if ((cur_entry->str != NULL)
+ && (0 == strncmp(str, cur_entry->str, num_significant_chars)))
+ {
+ /* Already there */
+ return JB_ERR_OK;
+ }
}
- cur = cur->next;
}
-
- cur = (struct list *)malloc(sizeof(*cur));
-
- if (cur != NULL)
+ else
{
- cur->str = (str ? strdup(str) : NULL); /* FIXME check retval */
- cur->next = NULL;
-
- last = header->last;
- if (last == NULL)
+ /* Test whole string */
+ for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
{
- last = header;
+ if ((cur_entry->str != NULL) && (0 == strcmp(str, cur_entry->str)))
+ {
+ /* Already there */
+ return JB_ERR_OK;
+ }
}
- last->next = cur;
- header->last = cur;
}
+
+ return enlist(the_list, str);
}
* if & only if there isn't already a header with that name.
*
* Parameters :
- * 1 : header = pointer to list 'dummy' header
- * 2 : first = first string to add to the list (maybe NULL)
- * 3 : second = number of chars to use for uniqueness test
+ * 1 : the_list = pointer to list
+ * 2 : name = HTTP header name (e.g. "Content-type")
+ * 3 : value = HTTP header value (e.g. "text/html")
*
- * Returns : N/A
+ * Returns : JB_ERR_OK on success
+ * JB_ERR_MEMORY on out-of-memory error.
+ * On error, the_list will be unchanged.
+ * "Success" does not indicate whether or not the
+ * header was already in the list.
*
*********************************************************************/
-void enlist_unique_header(struct list *header, const char *name, const char *value)
+jb_err enlist_unique_header(struct list *the_list, const char *name,
+ const char *value)
{
- struct list *last;
- struct list *cur = header->next;
- int length;
- char *dummy;
+ jb_err result = JB_ERR_MEMORY;
+ char *header;
+ size_t header_size;
- if (name == NULL || value == NULL) return;
+ assert(the_list);
+ assert(list_is_valid(the_list));
+ assert(name);
+ assert(value);
- dummy = strdup(name);
- dummy = strsav(dummy, ": ");
- length = strlen(dummy);
+ /* + 2 for the ': ', + 1 for the \0 */
+ header_size = strlen(name) + 2 + strlen(value) + 1;
+ header = (char *)malloc(header_size);
- while (cur != NULL)
+ if (NULL != header)
{
- if ((cur->str != NULL) &&
- (0 == strncmp(dummy, cur->str, length)))
+ const size_t bytes_to_compare = strlen(name) + 2;
+ char *p = header;
+
+ 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
{
- /* Already there */
- return;
- }
- cur = cur->next;
+ 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));
}
- cur = (struct list *)malloc(sizeof(*cur));
-
- if (cur != NULL)
- {
- cur->str = strsav(dummy, value);
- cur->next = NULL;
+ return result;
- last = header->last;
- if (last == NULL)
- {
- last = header;
- }
- last->next = cur;
- header->last = cur;
- }
}
/*********************************************************************
*
- * Function : destroy_list
+ * Function : list_remove_all
*
- * Description : Destroy a string list (opposite of enlist)
+ * Description : Remove all entries from a list. On return, the_list
+ * is a valid, empty list. Note that this is similar
+ * to destroy_list(), but the difference is that this
+ * function guarantees that the list structure is still
+ * valid after the call.
*
* Parameters :
- * 1 : header = pointer to list 'dummy' header
+ * 1 : the_list = pointer to list
*
* Returns : N/A
*
*********************************************************************/
-void destroy_list(struct list *header)
+void list_remove_all(struct list *the_list)
{
- struct list *p, *n;
+ struct list_entry *cur_entry;
+ struct list_entry *next_entry;
+
+ assert(the_list);
+ assert(list_is_valid(the_list));
- for (p = header->next; p ; p = n)
+ for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
{
- n = p->next;
- freez(p->str);
- free(p);
+ next_entry = cur_entry->next;
+ freez(cur_entry->str);
+ free(cur_entry);
}
- memset(header, '\0', sizeof(*header));
+ the_list->first = the_list->last = NULL;
+ assert(list_is_valid(the_list));
}
*
* Function : list_to_text
*
- * Description : "Flaten" a string list into 1 long \r\n delimited string.
+ * Description : "Flatten" a string list into 1 long \r\n delimited string,
+ * 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 : h = pointer to list 'dummy' header
+ * 1 : the_list = pointer to list
*
* Returns : NULL on malloc error, else new long string.
+ * Caller must free() it.
*
*********************************************************************/
-char *list_to_text(struct list *h)
+char *list_to_text(const struct list *the_list)
{
- struct list *p;
- char *ret = NULL;
- char *s;
- int size;
-
- size = 0;
-
- for (p = h->next; p ; p = p->next)
+ struct list_entry *cur_entry;
+ char *text;
+ size_t text_length;
+ char *cursor;
+ size_t bytes_left;
+
+ assert(the_list);
+ assert(list_is_valid(the_list));
+
+ /*
+ * 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 (p->str)
+ if (cur_entry->str)
{
- size += strlen(p->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);
+ return NULL;
}
- ret[size] = '\0';
+ cursor = text;
- s = ret;
-
- for (p = h->next; p ; p = p->next)
+ for (cur_entry = the_list->first; cur_entry; cur_entry = cur_entry->next)
{
- if (p->str)
+ if (cur_entry->str)
{
- strcpy(s, p->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;
}
}
- return(ret);
+ assert(bytes_left == 3);
+
+ *cursor++ = '\r';
+ *cursor++ = '\n';
+ *cursor = '\0';
+ assert(text_length == cursor - text);
+ assert(text[text_length] == '\0');
+
+ return text;
}
* Description : Remove a string from a specified string list.
*
* Parameters :
- * 1 : header = pointer to list 'dummy' header
- * 2 : str = string to remove from the list
+ * 1 : the_list = pointer to list
+ * 2 : str = string to remove from the list - non-NULL
*
* Returns : Number of times it was removed.
*
*********************************************************************/
-int list_remove_item(struct list *header, const char *str)
+int list_remove_item(struct list *the_list, const char *str)
{
- struct list *prev = header;
- struct list *cur = prev->next;
+ struct list_entry *prev = NULL;
+ struct list_entry *cur;
+ struct list_entry *next;
int count = 0;
+ assert(the_list);
+ assert(list_is_valid(the_list));
+ assert(str);
+
+ cur = the_list->first;
+
while (cur != NULL)
{
+ next = cur->next;
+
if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
{
count++;
- prev->next = cur->next;
- free(cur->str);
+ if (prev != NULL)
+ {
+ prev->next = next;
+ }
+ else
+ {
+ the_list->first = next;
+ }
+ free((char *)cur->str);
free(cur);
}
else
{
prev = cur;
}
- cur = prev->next;
+ cur = next;
}
- header->last = prev;
+ the_list->last = prev;
+
+ assert(list_is_valid(the_list));
return count;
}
*********************************************************************/
int list_remove_list(struct list *dest, const struct list *src)
{
- struct list *cur = src->next;
+ struct list_entry *cur;
int count = 0;
- while (cur != NULL)
+ assert(src);
+ assert(dest);
+ assert(list_is_valid(src));
+ assert(list_is_valid(dest));
+
+ for (cur = src->first; cur != NULL; cur = cur->next)
{
if (cur->str != NULL)
{
count += list_remove_item(dest, cur->str);
}
- cur = cur->next;
}
+ assert(list_is_valid(src));
+ assert(list_is_valid(dest));
+
return count;
}
*
* Function : list_duplicate
*
- * Description : Duplicate a string list
+ * Description : Copy a string list
*
* Parameters :
- * 1 : dest = pointer to destination for copy. Caller allocs.
- * 2 : src = pointer to source for copy.
+ * 1 : dest = Destination list. Must be a valid list.
+ * All existing entries will be removed.
+ * 1 : src = pointer to source list for copy.
*
- * Returns : N/A
+ * Returns : JB_ERR_OK on success
+ * JB_ERR_MEMORY on out-of-memory error.
+ * On error, dest will be empty.
*
*********************************************************************/
-void list_duplicate(struct list *dest, const struct list *src)
+jb_err list_duplicate(struct list *dest, const struct list *src)
{
- struct list * cur_src = src->next;
- struct list * cur_dest = dest;
+ struct list_entry * cur_src;
+ struct list_entry * cur_dest;
+
+ assert(src);
+ assert(dest);
+ assert(list_is_valid(src));
+ assert(list_is_valid(dest));
- memset(dest, '\0', sizeof(*dest));
+ list_remove_all(dest);
- while (cur_src)
+ /* Need to process first entry specially so we can set dest->first */
+ cur_src = src->first;
+ if (cur_src)
{
- cur_dest = cur_dest->next = (struct list *)zalloc(sizeof(*cur_dest));
+ cur_dest = dest->first = (struct list_entry *)zalloc(sizeof(*cur_dest));
if (cur_dest == NULL)
{
- return;
+ destroy_list(dest);
+
+ assert(list_is_valid(src));
+ assert(list_is_valid(dest));
+
+ return JB_ERR_MEMORY;
}
- cur_dest->str = strdup(cur_src->str);
- cur_src = cur_src->next;
+
+ if (cur_src->str)
+ {
+ cur_dest->str = strdup(cur_src->str);
+ if (cur_dest->str == NULL)
+ {
+ destroy_list(dest);
+
+ assert(list_is_valid(src));
+ assert(list_is_valid(dest));
+
+ return JB_ERR_MEMORY;
+ }
+ }
+ /* else { cur_dest->str = NULL; } - implied by zalloc */
+
+ /* Now process the rest */
+ for (cur_src = cur_src->next; cur_src; cur_src = cur_src->next)
+ {
+ cur_dest = cur_dest->next = (struct list_entry *)zalloc(sizeof(*cur_dest));
+ if (cur_dest == NULL)
+ {
+ destroy_list(dest);
+
+ assert(list_is_valid(src));
+ assert(list_is_valid(dest));
+
+ return JB_ERR_MEMORY;
+ }
+ if (cur_src->str)
+ {
+ cur_dest->str = strdup(cur_src->str);
+ if (cur_dest->str == NULL)
+ {
+ destroy_list(dest);
+
+ assert(list_is_valid(src));
+ assert(list_is_valid(dest));
+
+ return JB_ERR_MEMORY;
+ }
+ }
+ /* else { cur_dest->str = NULL; } - implied by zalloc */
+ }
+
+ dest->last = cur_dest;
}
- dest->last = cur_dest;
+ assert(list_is_valid(src));
+ assert(list_is_valid(dest));
+ return JB_ERR_OK;
}
* Duplicate items are not added.
*
* Parameters :
- * 1 : dest = pointer to destination for merge. Caller allocs.
+ * 1 : dest = pointer to destination list for merge.
* 2 : src = pointer to source for merge.
*
+ * Returns : JB_ERR_OK on success
+ * JB_ERR_MEMORY on out-of-memory error.
+ * On error, some (but not all) of src might have
+ * been copied into dest.
+ *
+ *********************************************************************/
+jb_err list_append_list_unique(struct list *dest, const struct list *src)
+{
+ struct list_entry * cur;
+
+ assert(src);
+ assert(dest);
+ assert(list_is_valid(src));
+ assert(list_is_valid(dest));
+
+ for (cur = src->first; cur; cur = cur->next)
+ {
+ if (cur->str)
+ {
+ if (enlist_unique(dest, cur->str, 0))
+ {
+ assert(list_is_valid(src));
+ assert(list_is_valid(dest));
+
+ return JB_ERR_MEMORY;
+ }
+ }
+ }
+
+ assert(list_is_valid(src));
+ assert(list_is_valid(dest));
+
+ return JB_ERR_OK;
+}
+
+
+/*********************************************************************
+ *
+ * Function : list_is_empty
+ *
+ * Description : Test whether a list is empty. Does not change the list.
+ *
+ * Parameters :
+ * 1 : the_list = pointer to list to test.
+ *
+ * Returns : Nonzero if the list contains no entries.
+ *
+ *********************************************************************/
+int list_is_empty(const struct list *the_list)
+{
+ assert(the_list);
+ assert(list_is_valid(the_list));
+
+ return (the_list->first == NULL);
+}
+
+
+/*********************************************************************
+ *
+ * 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
+ *
+ *********************************************************************/
+struct map *new_map(void)
+{
+ 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
+ * dependent strings
+ *
+ * Parameters :
+ * 1 : the_map = map to be freed. May be NULL.
+ *
* Returns : N/A
*
*********************************************************************/
-void list_append_list_unique(struct list *dest, const struct list *src)
+void free_map(struct map *the_map)
{
- struct list * cur = src->next;
+ struct map_entry *cur_entry;
+ struct map_entry *next_entry;
- while (cur)
+ if (the_map == NULL)
{
- enlist_unique(dest, cur->str, 0);
- cur = cur->next;
+ return;
}
+
+ for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = next_entry)
+ {
+ freez(cur_entry->name);
+ freez(cur_entry->value);
+
+ next_entry = cur_entry->next;
+ free(cur_entry);
+ }
+
+ the_map->first = the_map->last = NULL;
+
+ free(the_map);
}
* given map.
*
* Note: Since all strings will be free()d in free_map()
- * later, use the copy flags for constants or
- * strings that will be independantly free()d.
+ * later, set the copy flags for constants or
+ * strings that will be independently free()d.
+ *
+ * Note2: This function allows NULL parameters - it
+ * returns JB_ERR_MEMORY in that case.
+ *
+ * Note3: If this function returns JB_ERR_MEMORY,
+ * it will free(name) unless you specify
+ * name_needs_copying, and similarly it will
+ * free(value) unless you specify
+ * value_needs_copying.
+ *
+ * Due to Note2 and Note3 above, the following code
+ * is legal, and will never crash or leak memory even
+ * if the system runs out of memory:
+ *
+ * err = map(mymap, "xyz", 1, html_encode(somestring), 0);
+ *
+ * err will be set to JB_ERR_MEMORY if either call runs
+ * out-of-memory. Without these features, you would
+ * need to check the return value of html_encode in the
+ * above example for NULL, which (at least) doubles the
+ * amount of error-checking code needed.
*
* Parameters :
- * 1 : map = map to add to
+ * 1 : the_map = map to add to
* 2 : name = name to add
- * 3 : nc = flag set if a copy of name should be used
+ * 3 : name_needs_copying = flag set if a copy of name should be used
* 4 : value = value to add
- * 5 : vc = flag set if a copy of value should be used
+ * 5 : value_needs_copying = flag set if a copy of value should be used
*
- * Returns : pointer to extended map, or NULL if failiure
+ * Returns : JB_ERR_OK on success
+ * JB_ERR_MEMORY on out-of-memory error.
*
*********************************************************************/
-struct map *map(struct map *map, char *name, int nc, char *value, int vc)
+jb_err map(struct map *the_map,
+ const char *name, int name_needs_copying,
+ const char *value, int value_needs_copying)
{
- struct map *cur;
+ struct map_entry *new_entry;
- if (NULL == (cur = zalloc(sizeof(*cur))))
+ assert(the_map);
+
+ if ( (NULL == value)
+ || (NULL == name)
+ || (NULL == (new_entry = zalloc(sizeof(*new_entry)))))
{
- return(NULL);
+ if ((name != NULL) && (!name_needs_copying))
+ {
+ free((char *)name);
+ }
+ if ((value != NULL) && (!value_needs_copying))
+ {
+ free((char *)value);
+ }
+ return JB_ERR_MEMORY;
}
- cur->name = nc ? strdup(name) : name;
- cur->value = vc ? strdup(value) : value;
- cur->next = map;
+ if (name_needs_copying)
+ {
+ if (NULL == (name = strdup(name)))
+ {
+ free(new_entry);
+ if (!value_needs_copying)
+ {
+ free((char *)value);
+ }
+ return JB_ERR_MEMORY;
+ }
+ }
+
+ if (value_needs_copying)
+ {
+ if (NULL == (value = strdup(value)))
+ {
+ free((char *)name);
+ free(new_entry);
+ return JB_ERR_MEMORY;
+ }
+ }
- return(cur);
+ new_entry->name = name;
+ new_entry->value = value;
+ /* new_entry->next = NULL; - implied by zalloc */
+
+ if (the_map->last)
+ {
+ the_map->last->next = new_entry;
+ the_map->last = new_entry;
+ }
+ else
+ {
+ the_map->first = new_entry;
+ the_map->last = new_entry;
+ }
+ return JB_ERR_OK;
}
/*********************************************************************
*
- * Function : lookup
+ * Function : unmap
*
- * Description : Look up an item with a given name in a map, and
- * return its value
+ * Description : Remove all map_entry structs with a given name from
+ * a given map.
*
* Parameters :
- * 1 : name = name parameter to look for
+ * 1 : the_map = map to look in
+ * 2 : name = name to unmap
*
- * Returns : the value if found, else the empty string
+ * Returns : JB_ERR_OK
*
*********************************************************************/
-char *lookup(struct map *map, char *name)
+jb_err unmap(struct map *the_map, const char *name)
{
- struct map *p = map;
+ struct map_entry *cur_entry, *last_entry;
+
+ assert(the_map);
+ assert(name);
+
+ last_entry = NULL;
- while (p)
+ for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
{
- if (!strcmp(name, p->name))
+ if (!strcmp(name, cur_entry->name))
{
- return p->value;
+ /*
+ * Update the incoming pointer
+ */
+ if (cur_entry == the_map->first)
+ {
+ the_map->first = cur_entry->next;
+ }
+ else
+ {
+ last_entry->next = cur_entry->next;
+ }
+
+ /*
+ * 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
+ {
+ last_entry = cur_entry;
}
- p = p->next;
}
- return "";
+ return JB_ERR_OK;
}
/*********************************************************************
*
- * Function : free_map
+ * Function : lookup
*
- * Description : Free the memory occupied by a map and its
- * depandant strings
+ * Description : Look up an item with a given name in a map, and
+ * return its value
*
* Parameters :
- * 1 : list = list to bee freed
+ * 1 : the_map = map to look in
+ * 2 : name = name parameter to look for
*
- * Returns : N/A
+ * Returns : the value if found, else the empty string.
+ * Return value is alloced as part of the map, so
+ * it is freed when the map is destroyed. Caller
+ * must not free or modify it.
*
*********************************************************************/
-void free_map(struct map *map)
+const char *lookup(const struct map *the_map, const char *name)
{
- struct map *p = map;
+ const struct map_entry *cur_entry;
- while (p)
- {
- free(p->name);
- free(p->value);
+ assert(the_map);
+ assert(name);
- map = p->next;
- free(p);
- p = map;
+ for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
+ {
+ if (!strcmp(name, cur_entry->name))
+ {
+ return cur_entry->value;
+ }
}
-
+ return "";
}