Index: srclib/apr/include/apr_tables.h =================================================================== RCS file: /home/cvspublic/apr/include/apr_tables.h,v retrieving revision 1.23 diff -u -r1.23 apr_tables.h --- srclib/apr/include/apr_tables.h 2001/08/24 17:55:45 1.23 +++ srclib/apr/include/apr_tables.h 2001/09/07 21:16:17 @@ -83,9 +83,6 @@ * published. * @{ */ -/** the table abstract data type */ -typedef struct apr_table_t apr_table_t; - /** An opaque array type */ typedef struct apr_array_header_t apr_array_header_t; @@ -102,52 +99,7 @@ char *elts; }; -/** The opaque string-content table type */ -struct apr_table_t { - /* This has to be first to promote backwards compatibility with - * older modules which cast a apr_table_t * to an apr_array_header_t *... - * they should use the table_elts() function for most of the - * cases they do this for. - */ - /** The underlying array for the table */ - apr_array_header_t a; -#ifdef MAKE_TABLE_PROFILE - /** Who created the array. */ - void *creator; -#endif -}; - -/** - * The (opaque) structure for string-content tables. - */ -typedef struct apr_table_entry_t apr_table_entry_t; - -/** The type for each entry in a string-content table */ -struct apr_table_entry_t { - /** The key for the current table entry */ - char *key; /* maybe NULL in future; - * check when iterating thru table_elts - */ - /** The value for the current table entry */ - char *val; -}; - -/** - * Get the elements from a table - * @param t The table - * @return An array containing the contents of the table - */ -#define apr_table_elts(t) ((apr_array_header_t *)(t)) - /** - * Determine if the table is empty - * @param t The table to check - * @return True if empty, Falso otherwise - */ -#define apr_is_empty_table(t) (((t) == NULL) \ - || (((apr_array_header_t *)(t))->nelts == 0)) - -/** * Create an array * @param p The pool to allocate the memory out of * @param nelts the number of elements in the initial array @@ -223,7 +175,24 @@ const apr_array_header_t *arr, const char sep); +/** the table abstract data type */ +typedef struct apr_table_t apr_table_t; + +/** + * Determine if the table is empty + * @param t The table to check + * @return True if empty, False otherwise + */ +APR_DECLARE(int) apr_is_empty_table(const apr_table_t *t); + /** + * Determine the number of elements in the table + * @param t The table + * @return number of elements in the table + */ +APR_DECLARE(apr_size_t) apr_table_size(const apr_table_t *t); + +/** * Make a new table * @param p The pool to allocate the pool out of * @param nelts The number of elements in the initial table. @@ -421,6 +390,36 @@ APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b, unsigned flags); + +/** + * Create an iterator that can be used to do a read-only scan + * through the elements of a table + * @note Multiple iterators can be created on the same table + * @note After an iterator is created, it must be advanced with + * apr_table_iter_next() in order to reference the first element. + * @note If the pool is modified after creation of an iterator, + * the iterator can no longer be safely used + * @note Replaces the apr_table_elts macro + * @param p Pool from which to create the iterator + * @param t The table + * @return A const iterator + */ +typedef struct apr_table_iter_t apr_table_iter_t; +APR_DECLARE(apr_table_iter_t *) apr_table_iter_make(apr_pool_t *p, + const apr_table_t *t); + +/** + * Advance an iterator to the next element, and return the element'sn + * key and value + * @param iterator The iterator + * @param key Pointer in which to return the key + * @param value Pointer in which to return the value + * @return APR_SUCCESS if and only if the iterator now points to + * a valid element. + */ +APR_DECLARE(apr_status_t) apr_table_iter_next(apr_table_iter_t *iterator, + const char **key, + const char **value); /** @} */ #ifdef __cplusplus Index: srclib/apr/tables/apr_tables.c =================================================================== RCS file: /home/cvspublic/apr/tables/apr_tables.c,v retrieving revision 1.17 diff -u -r1.17 apr_tables.c --- srclib/apr/tables/apr_tables.c 2001/08/02 03:18:44 1.17 +++ srclib/apr/tables/apr_tables.c 2001/09/07 21:16:18 @@ -277,294 +277,583 @@ * The "table" functions. */ -/* - * XXX: if you tweak this you should look at is_empty_table() and table_elts() - * in alloc.h +/* Data structures: + * An apr_table_t is a hash table. Each bucket in the hash table + * holds a chain of table_element structures for the keys that hash + * into that bucket. The elements in each chain are kept sorted + * (strcasecmp determines the sort order). If there is more than + * one value for a key (e.g., as a result of a caller invoking + * apr_table_addn()), then the extra_values array in the table_element + * contains all the values after the first, in the order of insertion. */ -#ifdef MAKE_TABLE_PROFILE -static apr_table_entry_t *table_push(apr_table_t *t) + +#define EXTRA_VALUES_SIZE 4 + +typedef struct table_element { + const char *key; + const char *value; + apr_array_header_t *extra_values; + struct table_element *next; +} table_element; + +struct apr_table_t { + apr_pool_t *pool; + int size; + apr_size_t nelts; + table_element *elts[1]; +}; + +static unsigned int table_hash(const char *s) { - if (t->a.nelts == t->a.nalloc) { - return NULL; + unsigned int hash = 0; + unsigned int c; + while ((c = (unsigned int)*s++)) { +#if APR_CHARSET_EBCDIC + hash = hash * 33 + apr_tolower(c); +#else + hash = hash * 33 + (c & 0xdf); +#endif /* APR_CHARSET_EBCDIC */ } - return (apr_table_entry_t *) apr_array_push(&t->a); + return hash; } -#else /* MAKE_TABLE_PROFILE */ -#define table_push(t) ((apr_table_entry_t *) apr_array_push(&(t)->a)) -#endif /* MAKE_TABLE_PROFILE */ +APR_DECLARE(int) apr_is_empty_table(const apr_table_t *t) +{ + return ((t == NULL) || (t->nelts == 0)); +} -APR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts) +APR_DECLARE(apr_size_t) apr_table_size(const apr_table_t *t) { - apr_table_t *t = apr_palloc(p, sizeof(apr_table_t)); + return ((t == NULL) ? 0 : t->nelts); +} - make_array_core(&t->a, p, nelts, sizeof(apr_table_entry_t)); -#ifdef MAKE_TABLE_PROFILE - t->creator = __builtin_return_address(0); -#endif +APR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts) +{ + apr_table_t *t = apr_pcalloc(p, sizeof(apr_table_t) + + (nelts - 1) * sizeof(table_element *)); + t->pool = p; + t->size = nelts; return t; } APR_DECLARE(apr_table_t *) apr_table_copy(apr_pool_t *p, const apr_table_t *t) { - apr_table_t *new = apr_palloc(p, sizeof(apr_table_t)); + int i; + apr_table_t *new_tbl; #ifdef POOL_DEBUG - /* we don't copy keys and values, so it's necessary that t->a.pool + /* we don't copy keys and values, so it's necessary that t->pool * have a life span at least as long as p */ - if (!apr_pool_is_ancestor(t->a.pool, p)) { + if (!apr_pool_is_ancestor(t->pool, p)) { fprintf(stderr, "copy_table: t's pool is not an ancestor of p\n"); abort(); } #endif - make_array_core(&new->a, p, t->a.nalloc, sizeof(apr_table_entry_t)); - memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t)); - new->a.nelts = t->a.nelts; - return new; + + new_tbl = (apr_table_t *)apr_palloc(p, sizeof(apr_table_t) + + (t->size - 1) * sizeof(table_element *)); + new_tbl->pool = p; + new_tbl->size = t->size; + new_tbl->nelts = t->nelts; + for (i = 0; i < t->size; i++) { + table_element **dst = &(new_tbl->elts[i]); + const table_element *src = t->elts[i]; + while (src) { + *dst = (table_element *)apr_palloc(p, sizeof(table_element)); + (*dst)->key = src->key; + (*dst)->value = src->value; + if (src->extra_values) { + (*dst)->extra_values = apr_array_copy(p, src->extra_values); + } + else { + (*dst)->extra_values = NULL; + } + dst = &((*dst)->next); + src = src->next; + } + *dst = NULL; + } + + return new_tbl; } APR_DECLARE(void) apr_table_clear(apr_table_t *t) { - t->a.nelts = 0; + memset(&(t->elts[0]), 0, t->size * sizeof(table_element *)); + t->nelts = 0; } APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key) { - apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; - int i; + const table_element *elt; if (key == NULL) { - return NULL; + return NULL; } - for (i = 0; i < t->a.nelts; ++i) { - if (!strcasecmp(elts[i].key, key)) { - return elts[i].val; - } + /* Scan through the hash chain, taking advantage of + * the fact that the elements in the chain are in + * sorted order + */ + elt = t->elts[table_hash(key) % t->size]; + while (elt) { + int r = strcasecmp(key, elt->key); + if (r == 0) { + return elt->value; + } + if (r < 0) { + return NULL; + } + elt = elt->next; } return NULL; } APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key, - const char *val) + const char *val) { - register int i, j, k; - apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; - int done = 0; - - for (i = 0; i < t->a.nelts; ) { - if (!strcasecmp(elts[i].key, key)) { - if (!done) { - elts[i].val = apr_pstrdup(t->a.pool, val); - done = 1; - ++i; - } - else { /* delete an extraneous element */ - for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) { - elts[j].key = elts[k].key; - elts[j].val = elts[k].val; - } - --t->a.nelts; - } - } - else { - ++i; - } - } + table_element **elt; + table_element *new_node; - if (!done) { - elts = (apr_table_entry_t *) table_push(t); - elts->key = apr_pstrdup(t->a.pool, key); - elts->val = apr_pstrdup(t->a.pool, val); - } + /* Scan through the hash chain, and find the right place + * to insert the new value (note: the hash chain is in + * sorted order) + */ + elt = &(t->elts[table_hash(key) % t->size]); + while (*elt) { + int r = strcasecmp(key, (*elt)->key); + if (r == 0) { + /* Overwrite the existing value(s) for this key */ + (*elt)->value = apr_pstrdup(t->pool, val); + if ((*elt)->extra_values) { + t->nelts -= (*elt)->extra_values->nelts; + (*elt)->extra_values = NULL; + } + return; + } + if (r < 0) { + /* We need to add a new node in front of this one */ + break; + } + elt = &((*elt)->next); + } + + /* The key isn't in the hash table yet, so add a new node for it */ + t->nelts++; + new_node = (table_element *)apr_palloc(t->pool, sizeof(table_element)); + new_node->key = apr_pstrdup(t->pool, key); + new_node->value = apr_pstrdup(t->pool, val); + new_node->extra_values = NULL; + new_node->next = *elt; + *elt = new_node; } APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key, - const char *val) + const char *val) { - register int i, j, k; - apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; - int done = 0; + table_element **elt; + table_element *new_node; #ifdef POOL_DEBUG { - if (!apr_pool_is_ancestor(apr_find_pool(key), t->a.pool)) { + if (!apr_pool_is_ancestor(apr_find_pool(key), t->pool)) { fprintf(stderr, "table_set: key not in ancestor pool of t\n"); abort(); } - if (!apr_pool_is_ancestor(apr_find_pool(val), t->a.pool)) { + if (!apr_pool_is_ancestor(apr_find_pool(val), t->pool)) { fprintf(stderr, "table_set: val not in ancestor pool of t\n"); abort(); } } #endif - - for (i = 0; i < t->a.nelts; ) { - if (!strcasecmp(elts[i].key, key)) { - if (!done) { - elts[i].val = (char *)val; - done = 1; - ++i; - } - else { /* delete an extraneous element */ - for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) { - elts[j].key = elts[k].key; - elts[j].val = elts[k].val; - } - --t->a.nelts; - } - } - else { - ++i; - } - } - if (!done) { - elts = (apr_table_entry_t *) table_push(t); - elts->key = (char *)key; - elts->val = (char *)val; - } + /* Scan through the hash chain, and find the right place + * to insert the new value (note: the hash chain is in + * sorted order) + */ + elt = &(t->elts[table_hash(key) % t->size]); + while (*elt) { + int r = strcasecmp(key, (*elt)->key); + if (r == 0) { + /* Overwrite the existing value(s) for this key */ + (*elt)->value = val; + if ((*elt)->extra_values) { + t->nelts -= (*elt)->extra_values->nelts; + (*elt)->extra_values = NULL; + } + return; + } + if (r < 0) { + /* We need to add a new node in front of this one */ + break; + } + elt = &((*elt)->next); + } + + /* The key isn't in the hash table yet, so add a new node for it */ + t->nelts++; + new_node = (table_element *)apr_palloc(t->pool, sizeof(table_element)); + new_node->key = key; + new_node->value = val; + new_node->extra_values = NULL; + new_node->next = *elt; + *elt = new_node; } APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key) { - register int i, j, k; - apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; - - for (i = 0; i < t->a.nelts; ) { - if (!strcasecmp(elts[i].key, key)) { + table_element **elt; - /* found an element to skip over - * there are any number of ways to remove an element from - * a contiguous block of memory. I've chosen one that - * doesn't do a memcpy/bcopy/array_delete, *shrug*... - */ - for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) { - elts[j].key = elts[k].key; - elts[j].val = elts[k].val; - } - --t->a.nelts; - } - else { - ++i; - } + elt = &(t->elts[table_hash(key) % t->size]); + while (*elt) { + int r = strcasecmp(key, (*elt)->key); + if (r == 0) { + t->nelts--; + if ((*elt)->extra_values) { + t->nelts -= (*elt)->extra_values->nelts; + } + *elt = (*elt)->next; + return; + } + if (r < 0) { + /* If the key were in the hash table, it would have been + * before this node; thus we can stop scanning now + */ + return; + } + elt = &((*elt)->next); } } -APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key, - const char *val) +/* Merge the values for an element into a single comma-separated string */ +static void merge_element(apr_table_t *t, table_element *elt, + const char *new_value, int num_extra_values, + const char **extra_values) { - apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; + char *merged_value; + char *dst; int i; + int tmp_length; - for (i = 0; i < t->a.nelts; ++i) { - if (!strcasecmp(elts[i].key, key)) { - elts[i].val = apr_pstrcat(t->a.pool, elts[i].val, ", ", val, NULL); - return; - } - } + /* First pass: compute total length */ + apr_size_t length = strlen(elt->value); + if (elt->extra_values) { + const char **vals = (const char**)elt->extra_values->elts; + for (i = 0; i < elt->extra_values->nelts; i++) { + length += 2; /* for ", " */ + length += strlen(vals[i]); + } + + t->nelts -= elt->extra_values->nelts; + } + if (new_value) { + length += 2; + length += strlen(new_value); + } + if (num_extra_values) { + for (i = 0; i < num_extra_values; i++) { + length += 2; + length += strlen(extra_values[i]); + } + } + + /* Second pass: concatenate */ + merged_value = (char *)apr_palloc(t->pool, length + 1); + dst = merged_value; + + tmp_length = strlen(elt->value); + memcpy(dst, elt->value, tmp_length); + dst += tmp_length; + + if (elt->extra_values) { + const char **vals = (const char**)elt->extra_values->elts; + for (i = 0; i < elt->extra_values->nelts; i++) { + *dst++ = ','; + *dst++ = ' '; + tmp_length = strlen(vals[i]); + memcpy(dst, vals[i], tmp_length); + dst += tmp_length; + } + } + + if (new_value) { + *dst++ = ','; + *dst++ = ' '; + tmp_length = strlen(new_value); + memcpy(dst, new_value, tmp_length); + dst += tmp_length; + } + + if (num_extra_values) { + for (i = 0; i < num_extra_values; i++) { + *dst++ = ','; + *dst++ = ' '; + tmp_length = strlen(extra_values[i]); + memcpy(dst, extra_values[i], tmp_length); + dst += tmp_length; + } + } + + *dst = tmp_length; + elt->value = merged_value; + elt->extra_values = NULL; +} - elts = (apr_table_entry_t *) table_push(t); - elts->key = apr_pstrdup(t->a.pool, key); - elts->val = apr_pstrdup(t->a.pool, val); +APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key, + const char *val) +{ + table_element **elt; + table_element *new_node; + + /* Scan through the hash chain, and find the right place + * to insert the new value (note: the hash chain is in + * sorted order) + */ + elt = &(t->elts[table_hash(key) % t->size]); + while (*elt) { + int r = strcasecmp(key, (*elt)->key); + if (r == 0) { + /* Overwrite the existing value(s) for this key */ + merge_element(t, (*elt), val, 0, NULL); + return; + } + if (r < 0) { + /* We need to add a new node in front of this one */ + break; + } + elt = &((*elt)->next); + } + + /* The key isn't in the hash table yet, so add a new node for it */ + t->nelts++; + new_node = (table_element *)apr_palloc(t->pool, sizeof(table_element)); + new_node->key = apr_pstrdup(t->pool, key); + new_node->value = apr_pstrdup(t->pool, val); + new_node->extra_values = NULL; + new_node->next = *elt; + *elt = new_node; } APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key, - const char *val) + const char *val) { - apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; - int i; + table_element **elt; + table_element *new_node; #ifdef POOL_DEBUG { - if (!apr_pool_is_ancestor(apr_find_pool(key), t->a.pool)) { + if (!apr_pool_is_ancestor(apr_find_pool(key), t->pool)) { fprintf(stderr, "table_set: key not in ancestor pool of t\n"); abort(); } - if (!apr_pool_is_ancestor(apr_find_pool(val), t->a.pool)) { + if (!apr_pool_is_ancestor(apr_find_pool(val), t->pool)) { fprintf(stderr, "table_set: key not in ancestor pool of t\n"); abort(); } } #endif - - for (i = 0; i < t->a.nelts; ++i) { - if (!strcasecmp(elts[i].key, key)) { - elts[i].val = apr_pstrcat(t->a.pool, elts[i].val, ", ", val, NULL); - return; - } - } - elts = (apr_table_entry_t *) table_push(t); - elts->key = (char *)key; - elts->val = (char *)val; + /* Scan through the hash chain, and find the right place + * to insert the new value (note: the hash chain is in + * sorted order) + */ + elt = &(t->elts[table_hash(key) % t->size]); + while (*elt) { + int r = strcasecmp(key, (*elt)->key); + if (r == 0) { + /* Overwrite the existing value(s) for this key */ + merge_element(t, (*elt), val, 0, NULL); + return; + } + if (r < 0) { + /* We need to add a new node in front of this one */ + break; + } + elt = &((*elt)->next); + } + + /* The key isn't in the hash table yet, so add a new node for it */ + t->nelts++; + new_node = (table_element *)apr_palloc(t->pool, sizeof(table_element)); + new_node->key = key; + new_node->value = val; + new_node->extra_values = NULL; + new_node->next = *elt; + *elt = new_node; } APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key, const char *val) { - apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; + table_element **elt; + table_element *new_node; - elts = (apr_table_entry_t *) table_push(t); - elts->key = apr_pstrdup(t->a.pool, key); - elts->val = apr_pstrdup(t->a.pool, val); + /* Scan through the hash chain, and find the right place + * to insert the new value (note: the hash chain is in + * sorted order) + */ + elt = &(t->elts[table_hash(key) % t->size]); + while (*elt) { + int r = strcasecmp(key, (*elt)->key); + if (r == 0) { + if (!(*elt)->extra_values) { + (*elt)->extra_values = + apr_array_make(t->pool, EXTRA_VALUES_SIZE, sizeof(char *)); + } + *(char **)apr_array_push((*elt)->extra_values) = + apr_pstrdup(t->pool, val); + t->nelts++; + return; + } + if (r < 0) { + /* We need to add a new node in front of this one */ + break; + } + elt = &((*elt)->next); + } + + /* The key isn't in the hash table yet, so add a new node for it */ + t->nelts++; + new_node = (table_element *)apr_palloc(t->pool, sizeof(table_element)); + new_node->key = apr_pstrdup(t->pool, key); + new_node->value = apr_pstrdup(t->pool, val); + new_node->extra_values = NULL; + new_node->next = *elt; + *elt = new_node; } APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key, const char *val) { - apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; + table_element **elt; + table_element *new_node; #ifdef POOL_DEBUG { - if (!apr_pool_is_ancestor(apr_find_pool(key), t->a.pool)) { + if (!apr_pool_is_ancestor(apr_find_pool(key), t->pool)) { fprintf(stderr, "table_set: key not in ancestor pool of t\n"); abort(); } - if (!apr_pool_is_ancestor(apr_find_pool(val), t->a.pool)) { + if (!apr_pool_is_ancestor(apr_find_pool(val), t->pool)) { fprintf(stderr, "table_set: key not in ancestor pool of t\n"); abort(); } } #endif - elts = (apr_table_entry_t *) table_push(t); - elts->key = (char *)key; - elts->val = (char *)val; + /* Scan through the hash chain, and find the right place + * to insert the new value (note: the hash chain is in + * sorted order) + */ + elt = &(t->elts[table_hash(key) % t->size]); + while (*elt) { + int r = strcasecmp(key, (*elt)->key); + if (r == 0) { + if (!(*elt)->extra_values) { + (*elt)->extra_values = + apr_array_make(t->pool, EXTRA_VALUES_SIZE, sizeof(char *)); + } + *(const char **)apr_array_push((*elt)->extra_values) = val; + t->nelts++; + return; + } + if (r < 0) { + /* We need to add a new node in front of this one */ + break; + } + elt = &((*elt)->next); + } + + /* The key isn't in the hash table yet, so add a new node for it */ + t->nelts++; + new_node = (table_element *)apr_palloc(t->pool, sizeof(table_element)); + new_node->key = key; + new_node->value = val; + new_node->extra_values = NULL; + new_node->next = *elt; + *elt = new_node; } APR_DECLARE(apr_table_t *) apr_table_overlay(apr_pool_t *p, const apr_table_t *overlay, const apr_table_t *base) { - apr_table_t *res; + apr_table_t *new_tbl; + int i; #ifdef POOL_DEBUG /* we don't copy keys and values, so it's necessary that - * overlay->a.pool and base->a.pool have a life span at least + * overlay->pool and base->pool have a life span at least * as long as p */ - if (!apr_pool_is_ancestor(overlay->a.pool, p)) { + if (!apr_pool_is_ancestor(overlay->pool, p)) { fprintf(stderr, "overlay_tables: overlay's pool is not an ancestor of p\n"); abort(); } - if (!apr_pool_is_ancestor(base->a.pool, p)) { + if (!apr_pool_is_ancestor(base->pool, p)) { fprintf(stderr, "overlay_tables: base's pool is not an ancestor of p\n"); abort(); } #endif - res = apr_palloc(p, sizeof(apr_table_t)); - /* behave like append_arrays */ - res->a.pool = p; - copy_array_hdr_core(&res->a, &overlay->a); - apr_array_cat(&res->a, &base->a); + new_tbl = apr_table_copy(p, overlay); + for (i = 0; i < new_tbl->size; i++) { + const table_element *base_elt = base->elts[i]; + while (base_elt) { + const char *key = base_elt->key; + table_element **elt = &(new_tbl->elts[table_hash(key) % new_tbl->size]); + for (;;) { + int r = ((*elt) ? strcasecmp(key, (*elt)->key) : -1); + if (r == 0) { + /* This key exists in the target table, so append + * to its list of values + */ + if (!(*elt)->extra_values) { + (*elt)->extra_values = apr_array_make(p, + EXTRA_VALUES_SIZE, sizeof(char *)); + } + *(const char **)apr_array_push((*elt)->extra_values) = + base_elt->value; + new_tbl->nelts++; + if (base_elt->extra_values) { + apr_array_cat((*elt)->extra_values, + base_elt->extra_values); + new_tbl->nelts += base_elt->extra_values->nelts; + } + break; + } + else if (r < 0) { + /* This key does not yet exist in the target table */ + table_element *new_elt = + apr_palloc(p, sizeof(table_element)); + new_elt->key = base_elt->key; + new_elt->value = base_elt->value; + new_tbl->nelts++; + if (base_elt->extra_values) { + new_elt->extra_values = + apr_array_copy(p, base_elt->extra_values); + new_tbl->nelts += base_elt->extra_values->nelts; + } + else { + new_elt->extra_values = NULL; + } + new_elt->next = *elt; + *elt = new_elt; + break; + } + else { + elt = &((*elt)->next); + } + } + base_elt = base_elt->next; + } + } - return res; + return new_tbl; } /* And now for something completely abstract ... @@ -622,175 +911,160 @@ void *rec, const apr_table_t *t, va_list vp) { char *argp; - apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts; - int rv, i; + int done, i; + argp = va_arg(vp, char *); do { - for (rv = 1, i = 0; rv && (i < t->a.nelts); ++i) { - if (elts[i].key && (!argp || !strcasecmp(elts[i].key, argp))) { - rv = (*comp) (rec, elts[i].key, elts[i].val); - } - } + for (i = 0, done=0; !done && (i < t->size); i++) { + table_element *elt = t->elts[i]; + while (elt) { + if (!(*comp)(rec, elt->key, elt->value)) { + done = 1; + break; + } + if (elt->extra_values) { + int j; + for (j = 0; j < elt->extra_values->nelts; j++) { + if (!(*comp)(rec, elt->key, + ((char**)(elt->extra_values->elts))[j])) { + done = 1; + break; + } + } + } + elt = elt->next; + } + } } while (argp && ((argp = va_arg(vp, char *)) != NULL)); } - -/* Curse libc and the fact that it doesn't guarantee a stable sort. We - * have to enforce stability ourselves by using the order field. If it - * provided a stable sort then we wouldn't even need temporary storage to - * do the work below. -djg - * - * ("stable sort" means that equal keys retain their original relative - * ordering in the output.) - */ -typedef struct { - char *key; - char *val; - int order; -} overlap_key; -static int sort_overlap(const void *va, const void *vb) +APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b, + unsigned flags) { - const overlap_key *a = va; - const overlap_key *b = vb; - int r; + int i; + for (i = 0; i < b->size; i++) { + const table_element *b_elt = b->elts[i]; + while (b_elt) { + const char *key = b_elt->key; + table_element **a_elt = &(a->elts[table_hash(key) % a->size]); + for (;;) { + int r = ((*a_elt) ? strcasecmp(key, (*a_elt)->key) : -1); + if (r == 0) { + /* The key exists in table a; append or overwrite, + * depending on the flag status + */ + if (flags & APR_OVERLAP_TABLES_MERGE) { + if (b_elt->extra_values) { + merge_element(a, (*a_elt), b_elt->value, + b_elt->extra_values->nelts, + (const char **)b_elt->extra_values->elts); + } + else { + merge_element(a, (*a_elt), b_elt->value, 0, NULL); + } + } + else { + (*a_elt)->key = b_elt->key; + (*a_elt)->value = b_elt->value; + if ((*a_elt)->extra_values) { + a->nelts -= (*a_elt)->extra_values->nelts; + } + if (b_elt->extra_values) { + (*a_elt)->extra_values = + apr_array_copy(a->pool, b_elt->extra_values); + a->nelts += b_elt->extra_values->nelts; + } + else { + (*a_elt)->extra_values = NULL; + } + } + break; + } + else if (r < 0) { + /* This key does not yet exist in table a */ + table_element *new_elt = + apr_palloc(a->pool, sizeof(table_element)); + new_elt->key = key; + new_elt->value = b_elt->value; + if (b_elt->extra_values) { + new_elt->extra_values = + apr_array_copy(a->pool, b_elt->extra_values); + } + else { + new_elt->extra_values = NULL; + } + new_elt->next = *a_elt; + *a_elt = new_elt; + a->nelts++; + break; + } + else { + a_elt = &((*a_elt)->next); + } + } - r = strcasecmp(a->key, b->key); - if (r) { - return r; + b_elt = b_elt->next; + } } - return a->order - b->order; } -/* prefer to use the stack for temp storage for overlaps smaller than this */ -#ifndef APR_OVERLAP_TABLES_ON_STACK -#define APR_OVERLAP_TABLES_ON_STACK (512) -#endif -APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b, - unsigned flags) -{ - overlap_key cat_keys_buf[APR_OVERLAP_TABLES_ON_STACK]; - overlap_key *cat_keys; - int nkeys; - apr_table_entry_t *e; - apr_table_entry_t *last_e; - overlap_key *left; - overlap_key *right; - overlap_key *last; - - nkeys = a->a.nelts + b->a.nelts; - if (nkeys < APR_OVERLAP_TABLES_ON_STACK) { - cat_keys = cat_keys_buf; - } - else { - /* XXX: could use scratch free space in a or b's pool instead... - * which could save an allocation in b's pool. - */ - cat_keys = apr_palloc(b->a.pool, sizeof(overlap_key) * nkeys); - } +/***************************************************************** + * + * The "table iterator" functions. + */ - nkeys = 0; +struct apr_table_iter_t { + const apr_table_t* table; + int bucket_num; + table_element *elt; + int val_index; /* Index of value within elt, 0 means elt->value, + 1-n reference elt->extra_values */ +}; - /* Create a list of the entries from a concatenated with the entries - * from b. - */ - e = (apr_table_entry_t *)a->a.elts; - last_e = e + a->a.nelts; - while (e < last_e) { - cat_keys[nkeys].key = e->key; - cat_keys[nkeys].val = e->val; - cat_keys[nkeys].order = nkeys; - ++nkeys; - ++e; - } - - e = (apr_table_entry_t *)b->a.elts; - last_e = e + b->a.nelts; - while (e < last_e) { - cat_keys[nkeys].key = e->key; - cat_keys[nkeys].val = e->val; - cat_keys[nkeys].order = nkeys; - ++nkeys; - ++e; - } - qsort(cat_keys, nkeys, sizeof(overlap_key), sort_overlap); +APR_DECLARE(apr_table_iter_t *) apr_table_iter_make(apr_pool_t *p, + const apr_table_t *t) +{ + apr_table_iter_t *iter = apr_palloc(p, sizeof(apr_table_iter_t)); + iter->table = t; + iter->bucket_num = -1; /* new iter points to spot before the first elem */ + iter->elt = NULL; + return iter; +} - /* Now iterate over the sorted list and rebuild a. - * Start by making sure it has enough space. - */ - a->a.nelts = 0; - if (a->a.nalloc < nkeys) { - a->a.elts = apr_palloc(a->a.pool, a->a.elt_size * nkeys * 2); - a->a.nalloc = nkeys * 2; - } - /* - * In both the merge and set cases we retain the invariant: - * - * left->key, (left+1)->key, (left+2)->key, ..., (right-1)->key - * are all equal keys. (i.e. strcasecmp returns 0) - * - * We essentially need to find the maximal - * right for each key, then we can do a quick merge or set as - * appropriate. +APR_DECLARE(apr_status_t) apr_table_iter_next(apr_table_iter_t *iter, + const char **key, + const char **value) +{ + /* If currently pointing at a table element, iterate within + * that element if it has multiple values; otherwise advance + * to the next element */ - - if (flags & APR_OVERLAP_TABLES_MERGE) { - left = cat_keys; - last = left + nkeys; - while (left < last) { - right = left + 1; - if (right == last - || strcasecmp(left->key, right->key)) { - apr_table_addn(a, left->key, left->val); - left = right; - } - else { - char *strp; - char *value; - size_t len; - - /* Have to merge some headers. Let's re-use the order field, - * since it's handy... we'll store the length of val there. - */ - left->order = strlen(left->val); - len = left->order; - do { - right->order = strlen(right->val); - len += 2 + right->order; - ++right; - } while (right < last - && !strcasecmp(left->key, right->key)); - /* right points one past the last header to merge */ - value = apr_palloc(a->a.pool, len + 1); - strp = value; - for (;;) { - memcpy(strp, left->val, left->order); - strp += left->order; - ++left; - if (left == right) { - break; - } - *strp++ = ','; - *strp++ = ' '; - } - *strp = 0; - apr_table_addn(a, (left-1)->key, value); - } - } - } - else { - left = cat_keys; - last = left + nkeys; - while (left < last) { - right = left + 1; - while (right < last && !strcasecmp(left->key, right->key)) { - ++right; - } - apr_table_addn(a, (right-1)->key, (right-1)->val); - left = right; - } - } + if (iter->elt) { + if (iter->elt->extra_values) { + iter->val_index++; + if (iter->val_index <= iter->elt->extra_values->nelts) { + *key = iter->elt->key; + *value = ((const char **)iter->elt->extra_values->elts)[iter->val_index - 1]; + return APR_SUCCESS; + } + } + iter->elt = iter->elt->next; + } + + /* If at the end of a hash chain, advance to the next bucket */ + while (!iter->elt) { + iter->bucket_num++; + if (iter->bucket_num >= iter->table->size) { + return APR_EGENERAL; + } + iter->elt = iter->table->elts[iter->bucket_num]; + } + + iter->val_index = 0; + *key = iter->elt->key; + *value = iter->elt->value; + return APR_SUCCESS; } -