rbb 99/07/27 11:28:00
Modified: apr/lib Makefile.in apr_pools.c Added: apr/lib apr_tables.c Log: Split the array and table functions out from the memory pool functions. This should make it easier to allow for pools vs malloc/free options at configure time. I'll be splitting out more code shortly. :) Revision Changes Path 1.12 +19 -6 apache-apr/apr/lib/Makefile.in Index: Makefile.in =================================================================== RCS file: /home/cvs/apache-apr/apr/lib/Makefile.in,v retrieving revision 1.11 retrieving revision 1.12 diff -u -r1.11 -r1.12 --- Makefile.in 1999/07/23 14:41:38 1.11 +++ Makefile.in 1999/07/27 18:27:58 1.12 @@ -24,7 +24,8 @@ apr_pools.o \ apr_signal.o \ apr_slack.o \ - apr_snprintf.o + apr_snprintf.o \ + apr_tables.o .c.o: $(CC) $(CFLAGS) -c $(INCLUDES) $< @@ -62,12 +63,24 @@ apr_cpystrn.o: apr_cpystrn.c $(INCDIR)/apr_config.h apr_execve.o: apr_execve.c $(INCDIR)/apr_config.h apr_fnmatch.o: apr_fnmatch.c $(INCDIR)/apr_config.h \ - $(INCDIR)/apr_fnmatch.h + $(INCDIR)/apr_fnmatch.h $(INCDIR)/apr_lib.h \ + ../../include/apr_general.h ../../include/apr_errno.h \ + $(INCDIR)/hsregex.h apr_md5.o: apr_md5.c $(INCDIR)/apr_config.h $(INCDIR)/apr_md5.h \ - $(INCDIR)/apr_lib.h $(INCDIR)/hsregex.h + $(INCDIR)/apr_lib.h ../../include/apr_general.h \ + ../../include/apr_errno.h $(INCDIR)/hsregex.h apr_pools.o: apr_pools.c $(INCDIR)/apr_config.h \ - $(INCDIR)/apr_pools.h $(INCDIR)/apr_lib.h $(INCDIR)/hsregex.h -apr_signal.o: apr_signal.c $(INCDIR)/apr_config.h + ../../include/apr_general.h ../../include/apr_errno.h \ + $(INCDIR)/apr_pools.h $(INCDIR)/apr_lib.h $(INCDIR)/hsregex.h \ + ../misc/unix/misc.h ../../include/apr_file_io.h +apr_signal.o: apr_signal.c $(INCDIR)/apr_config.h \ + $(INCDIR)/apr_lib.h ../../include/apr_general.h \ + ../../include/apr_errno.h $(INCDIR)/hsregex.h apr_slack.o: apr_slack.c $(INCDIR)/apr_config.h apr_snprintf.o: apr_snprintf.c $(INCDIR)/apr_config.h \ - $(INCDIR)/apr_lib.h $(INCDIR)/hsregex.h + $(INCDIR)/apr_lib.h ../../include/apr_general.h \ + ../../include/apr_errno.h $(INCDIR)/hsregex.h +apr_tables.o: apr_tables.c $(INCDIR)/apr_config.h \ + ../../include/apr_general.h ../../include/apr_errno.h \ + $(INCDIR)/apr_pools.h $(INCDIR)/apr_lib.h $(INCDIR)/hsregex.h \ + ../misc/unix/misc.h ../../include/apr_file_io.h 1.9 +0 -690 apache-apr/apr/lib/apr_pools.c Index: apr_pools.c =================================================================== RCS file: /home/cvs/apache-apr/apr/lib/apr_pools.c,v retrieving revision 1.8 retrieving revision 1.9 diff -u -r1.8 -r1.9 --- apr_pools.c 1999/07/02 19:09:16 1.8 +++ apr_pools.c 1999/07/27 18:27:59 1.9 @@ -1026,696 +1026,6 @@ /***************************************************************** * - * The 'array' functions... - */ - -static void make_array_core(ap_array_header_t *res, struct context_t *c, - int nelts, int elt_size) -{ - /* - * Assure sanity if someone asks for - * array of zero elts. - */ - if (nelts < 1) { - nelts = 1; - } - - res->elts = ap_pcalloc(c, nelts * elt_size); - - res->cont = c; - res->elt_size = elt_size; - res->nelts = 0; /* No active elements yet... */ - res->nalloc = nelts; /* ...but this many allocated */ -} - -API_EXPORT(ap_array_header_t *) ap_make_array(struct context_t *p, - int nelts, int elt_size) -{ - ap_array_header_t *res; - - res = (ap_array_header_t *) ap_palloc(p, sizeof(ap_array_header_t)); - make_array_core(res, p, nelts, elt_size); - return res; -} - -API_EXPORT(void *) ap_push_array(ap_array_header_t *arr) -{ - if (arr->nelts == arr->nalloc) { - int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2; - char *new_data; - - new_data = ap_pcalloc(arr->cont, arr->elt_size * new_size); - - memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size); - arr->elts = new_data; - arr->nalloc = new_size; - } - - ++arr->nelts; - return arr->elts + (arr->elt_size * (arr->nelts - 1)); -} - -API_EXPORT(void) ap_array_cat(ap_array_header_t *dst, - const ap_array_header_t *src) -{ - int elt_size = dst->elt_size; - - if (dst->nelts + src->nelts > dst->nalloc) { - int new_size = (dst->nalloc <= 0) ? 1 : dst->nalloc * 2; - char *new_data; - - while (dst->nelts + src->nelts > new_size) { - new_size *= 2; - } - - new_data = ap_pcalloc(dst->cont, elt_size * new_size); - memcpy(new_data, dst->elts, dst->nalloc * elt_size); - - dst->elts = new_data; - dst->nalloc = new_size; - } - - memcpy(dst->elts + dst->nelts * elt_size, src->elts, - elt_size * src->nelts); - dst->nelts += src->nelts; -} - -API_EXPORT(ap_array_header_t *) ap_copy_array(struct context_t *p, - const ap_array_header_t *arr) -{ - ap_array_header_t *res = ap_make_array(p, arr->nalloc, arr->elt_size); - - memcpy(res->elts, arr->elts, arr->elt_size * arr->nelts); - res->nelts = arr->nelts; - return res; -} - -/* This cute function copies the array header *only*, but arranges - * for the data section to be copied on the first push or arraycat. - * It's useful when the elements of the array being copied are - * read only, but new stuff *might* get added on the end; we have the - * overhead of the full copy only where it is really needed. - */ - -static APR_INLINE void copy_array_hdr_core(ap_array_header_t *res, - const ap_array_header_t *arr) -{ - res->elts = arr->elts; - res->elt_size = arr->elt_size; - res->nelts = arr->nelts; - res->nalloc = arr->nelts; /* Force overflow on push */ -} - -API_EXPORT(ap_array_header_t *) - ap_copy_array_hdr(struct context_t *p, - const ap_array_header_t *arr) -{ - ap_array_header_t *res; - - res = (ap_array_header_t *) ap_palloc(p, sizeof(ap_array_header_t)); - res->cont = p; - copy_array_hdr_core(res, arr); - return res; -} - -/* The above is used here to avoid consing multiple new array bodies... */ - -API_EXPORT(ap_array_header_t *) - ap_append_arrays(struct context_t *p, - const ap_array_header_t *first, - const ap_array_header_t *second) -{ - ap_array_header_t *res = ap_copy_array_hdr(p, first); - - ap_array_cat(res, second); - return res; -} - -/* ap_array_pstrcat generates a new string from the pool containing - * the concatenated sequence of substrings referenced as elements within - * the array. The string will be empty if all substrings are empty or null, - * or if there are no elements in the array. - * If sep is non-NUL, it will be inserted between elements as a separator. - */ -API_EXPORT(char *) ap_array_pstrcat(struct context_t *p, - const ap_array_header_t *arr, - const char sep) -{ - char *cp, *res, **strpp; - int i, len; - - if (arr->nelts <= 0 || arr->elts == NULL) { /* Empty table? */ - return (char *) ap_pcalloc(p, 1); - } - - /* Pass one --- find length of required string */ - - len = 0; - for (i = 0, strpp = (char **) arr->elts; ; ++strpp) { - if (strpp && *strpp != NULL) { - len += strlen(*strpp); - } - if (++i >= arr->nelts) { - break; - } - if (sep) { - ++len; - } - } - - /* Allocate the required string */ - - res = (char *) ap_palloc(p, len + 1); - cp = res; - - /* Pass two --- copy the argument strings into the result space */ - - for (i = 0, strpp = (char **) arr->elts; ; ++strpp) { - if (strpp && *strpp != NULL) { - len = strlen(*strpp); - memcpy(cp, *strpp, len); - cp += len; - } - if (++i >= arr->nelts) { - break; - } - if (sep) { - *cp++ = sep; - } - } - - *cp = '\0'; - - /* Return the result string */ - - return res; -} - - -/***************************************************************** - * - * The "table" functions. - */ - -/* - * XXX: if you tweak this you should look at is_empty_table() and table_elts() - * in alloc.h - */ -#ifdef MAKE_TABLE_PROFILE -static ap_table_entry_t *table_push(ap_table_t *t) -{ - if (t->a.nelts == t->a.nalloc) { - fprintf(stderr, - "table_push: table created by %p hit limit of %u\n", - t->creator, t->a.nalloc); - } - return (ap_table_entry_t *) ap_push_array(&t->a); -} -#else /* MAKE_TABLE_PROFILE */ -#define table_push(t) ((ap_table_entry_t *) ap_push_array(&(t)->a)) -#endif /* MAKE_TABLE_PROFILE */ - - -API_EXPORT(ap_table_t *) ap_make_table(struct context_t *p, int nelts) -{ - ap_table_t *t = ap_palloc(p, sizeof(ap_table_t)); - - make_array_core(&t->a, p, nelts, sizeof(ap_table_entry_t)); -#ifdef MAKE_TABLE_PROFILE - t->creator = __builtin_return_address(0); -#endif - return t; -} - -API_EXPORT(ap_table_t *) ap_copy_table(struct context_t *p, const ap_table_t *t) -{ - ap_table_t *new = ap_palloc(p, sizeof(ap_table_t)); - -#ifdef POOL_DEBUG - /* we don't copy keys and values, so it's necessary that t->a.pool - * have a life span at least as long as p - */ - if (!ap_pool_is_ancestor(t->a.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(ap_table_entry_t)); - memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(ap_table_entry_t)); - new->a.nelts = t->a.nelts; - return new; -} - -API_EXPORT(void) ap_clear_table(ap_table_t *t) -{ - t->a.nelts = 0; -} - -API_EXPORT(const char *) ap_table_get(const ap_table_t *t, const char *key) -{ - ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; - int i; - - if (key == NULL) { - return NULL; - } - - for (i = 0; i < t->a.nelts; ++i) { - if (!strcasecmp(elts[i].key, key)) { - return elts[i].val; - } - } - - return NULL; -} - -API_EXPORT(void) ap_table_set(ap_table_t *t, const char *key, - const char *val) -{ - register int i, j, k; - ap_table_entry_t *elts = (ap_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 = ap_pstrdup(t->a.cont, 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 = (ap_table_entry_t *) table_push(t); - elts->key = ap_pstrdup(t->a.cont, key); - elts->val = ap_pstrdup(t->a.cont, val); - } -} - -API_EXPORT(void) ap_table_setn(ap_table_t *t, const char *key, - const char *val) -{ - register int i, j, k; - ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; - int done = 0; - -#ifdef POOL_DEBUG - { - if (!ap_pool_is_ancestor(ap_find_pool(key), t->a.pool)) { - fprintf(stderr, "table_set: key not in ancestor pool of t\n"); - abort(); - } - if (!ap_pool_is_ancestor(ap_find_pool(val), t->a.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 = (ap_table_entry_t *) table_push(t); - elts->key = (char *)key; - elts->val = (char *)val; - } -} - -API_EXPORT(void) ap_table_unset(ap_table_t *t, const char *key) -{ - register int i, j, k; - ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; - - for (i = 0; i < t->a.nelts; ) { - if (!strcasecmp(elts[i].key, key)) { - - /* 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; - } - } -} - -API_EXPORT(void) ap_table_merge(ap_table_t *t, const char *key, - const char *val) -{ - ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; - int i; - - for (i = 0; i < t->a.nelts; ++i) { - if (!strcasecmp(elts[i].key, key)) { - elts[i].val = ap_pstrcat(t->a.cont, elts[i].val, ", ", val, NULL); - return; - } - } - - elts = (ap_table_entry_t *) table_push(t); - elts->key = ap_pstrdup(t->a.cont, key); - elts->val = ap_pstrdup(t->a.cont, val); -} - -API_EXPORT(void) ap_table_mergen(ap_table_t *t, const char *key, - const char *val) -{ - ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; - int i; - -#ifdef POOL_DEBUG - { - if (!ap_pool_is_ancestor(ap_find_pool(key), t->a.pool)) { - fprintf(stderr, "table_set: key not in ancestor pool of t\n"); - abort(); - } - if (!ap_pool_is_ancestor(ap_find_pool(val), t->a.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 = ap_pstrcat(t->a.cont, elts[i].val, ", ", val, NULL); - return; - } - } - - elts = (ap_table_entry_t *) table_push(t); - elts->key = (char *)key; - elts->val = (char *)val; -} - -API_EXPORT(void) ap_table_add(ap_table_t *t, const char *key, - const char *val) -{ - ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; - - elts = (ap_table_entry_t *) table_push(t); - elts->key = ap_pstrdup(t->a.cont, key); - elts->val = ap_pstrdup(t->a.cont, val); -} - -API_EXPORT(void) ap_table_addn(ap_table_t *t, const char *key, - const char *val) -{ - ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; - -#ifdef POOL_DEBUG - { - if (!ap_pool_is_ancestor(ap_find_pool(key), t->a.pool)) { - fprintf(stderr, "table_set: key not in ancestor pool of t\n"); - abort(); - } - if (!ap_pool_is_ancestor(ap_find_pool(val), t->a.pool)) { - fprintf(stderr, "table_set: key not in ancestor pool of t\n"); - abort(); - } - } -#endif - - elts = (ap_table_entry_t *) table_push(t); - elts->key = (char *)key; - elts->val = (char *)val; -} - -API_EXPORT(ap_table_t *) ap_overlay_tables(struct context_t *p, - const ap_table_t *overlay, - const ap_table_t *base) -{ - ap_table_t *res; - -#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 - * as long as p - */ - if (!ap_pool_is_ancestor(overlay->a.pool, p->pool)) { - fprintf(stderr, - "overlay_tables: overlay's pool is not an ancestor of p\n"); - abort(); - } - if (!ap_pool_is_ancestor(base->a.pool, p->pool)) { - fprintf(stderr, - "overlay_tables: base's pool is not an ancestor of p\n"); - abort(); - } -#endif - - res = ap_palloc(p, sizeof(ap_table_t)); - /* behave like append_arrays */ - res->a.cont = p; - copy_array_hdr_core(&res->a, &overlay->a); - ap_array_cat(&res->a, &base->a); - - return res; -} - -/* And now for something completely abstract ... - - * For each key value given as a vararg: - * run the function pointed to as - * int comp(void *r, char *key, char *value); - * on each valid key-value pair in the table t that matches the vararg key, - * or once for every valid key-value pair if the vararg list is empty, - * until the function returns false (0) or we finish the table. - * - * Note that we restart the traversal for each vararg, which means that - * duplicate varargs will result in multiple executions of the function - * for each matching key. Note also that if the vararg list is empty, - * only one traversal will be made and will cut short if comp returns 0. - * - * Note that the table_get and table_merge functions assume that each key in - * the table is unique (i.e., no multiple entries with the same key). This - * function does not make that assumption, since it (unfortunately) isn't - * true for some of Apache's tables. - * - * Note that rec is simply passed-on to the comp function, so that the - * caller can pass additional info for the task. - */ -API_EXPORT(void) ap_table_do(int (*comp) (void *, const char *, const char *), - void *rec, const ap_table_t *t, ...) -{ - va_list vp; - char *argp; - ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; - int rv, i; - - va_start(vp, t); - - 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); - } - } - } while (argp && ((argp = va_arg(vp, char *)) != NULL)); - - va_end(vp); -} - -/* 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) -{ - const overlap_key *a = va; - const overlap_key *b = vb; - int r; - - r = strcasecmp(a->key, b->key); - if (r) { - return r; - } - return a->order - b->order; -} - -/* prefer to use the stack for temp storage for overlaps smaller than this */ -#ifndef ap_OVERLAP_TABLES_ON_STACK -#define ap_OVERLAP_TABLES_ON_STACK (512) -#endif - -API_EXPORT(void) ap_overlap_tables(ap_table_t *a, const ap_table_t *b, - unsigned flags) -{ - overlap_key cat_keys_buf[ap_OVERLAP_TABLES_ON_STACK]; - overlap_key *cat_keys; - int nkeys; - ap_table_entry_t *e; - ap_table_entry_t *last_e; - overlap_key *left; - overlap_key *right; - overlap_key *last; - - nkeys = a->a.nelts + b->a.nelts; - if (nkeys < ap_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 = ap_palloc(b->a.cont, sizeof(overlap_key) * nkeys); - } - - nkeys = 0; - - /* Create a list of the entries from a concatenated with the entries - * from b. - */ - e = (ap_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 = (ap_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); - - /* 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 = ap_palloc(a->a.cont, 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. - */ - - if (flags & ap_OVERLAP_TABLES_MERGE) { - left = cat_keys; - last = left + nkeys; - while (left < last) { - right = left + 1; - if (right == last - || strcasecmp(left->key, right->key)) { - ap_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 = ap_palloc(a->a.cont, len + 1); - strp = value; - for (;;) { - memcpy(strp, left->val, left->order); - strp += left->order; - ++left; - if (left == right) { - break; - } - *strp++ = ','; - *strp++ = ' '; - } - *strp = 0; - ap_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; - } - ap_table_addn(a, (right-1)->key, (right-1)->val); - left = right; - } - } -} - -/***************************************************************** - * * Managing generic cleanups. */ 1.1 apache-apr/apr/lib/apr_tables.c Index: apr_tables.c =================================================================== /* ==================================================================== * Copyright (c) 1995-1999 The Apache Group. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. All advertising materials mentioning features or use of this * software must display the following acknowledgment: * "This product includes software developed by the Apache Group * for use in the Apache HTTP server project (http://www.apache.org/)." * * 4. The names "Apache Server" and "Apache Group" must not be used to * endorse or promote products derived from this software without * prior written permission. For written permission, please contact * [EMAIL PROTECTED] * * 5. Products derived from this software may not be called "Apache" * nor may "Apache" appear in their names without prior written * permission of the Apache Group. * * 6. Redistributions of any form whatsoever must retain the following * acknowledgment: * "This product includes software developed by the Apache Group * for use in the Apache HTTP server project (http://www.apache.org/)." * * THIS SOFTWARE IS PROVIDED BY THE APACHE GROUP ``AS IS'' AND ANY * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE APACHE GROUP OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED * OF THE POSSIBILITY OF SUCH DAMAGE. * ==================================================================== * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Group and was originally based * on public domain software written at the National Center for * Supercomputing Applications, University of Illinois, Urbana-Champaign. * For more information on the Apache Group and the Apache HTTP server * project, please see <http://www.apache.org/>. * */ /* * Resource allocation code... the code here is responsible for making * sure that nothing leaks. * * rst --- 4/95 --- 6/95 */ #ifndef WIN32 #include "apr_config.h" #else #include "apr_win.h" #endif #include "apr_general.h" #include "apr_pools.h" #include "apr_lib.h" #include "misc.h" #include <stdlib.h> #include <malloc.h> /***************************************************************** * This file contains array and table functions only. */ /***************************************************************** * * The 'array' functions... */ static void make_array_core(ap_array_header_t *res, struct context_t *c, int nelts, int elt_size) { /* * Assure sanity if someone asks for * array of zero elts. */ if (nelts < 1) { nelts = 1; } res->elts = ap_pcalloc(c, nelts * elt_size); res->cont = c; res->elt_size = elt_size; res->nelts = 0; /* No active elements yet... */ res->nalloc = nelts; /* ...but this many allocated */ } API_EXPORT(ap_array_header_t *) ap_make_array(struct context_t *p, int nelts, int elt_size) { ap_array_header_t *res; res = (ap_array_header_t *) ap_palloc(p, sizeof(ap_array_header_t)); make_array_core(res, p, nelts, elt_size); return res; } API_EXPORT(void *) ap_push_array(ap_array_header_t *arr) { if (arr->nelts == arr->nalloc) { int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2; char *new_data; new_data = ap_pcalloc(arr->cont, arr->elt_size * new_size); memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size); arr->elts = new_data; arr->nalloc = new_size; } ++arr->nelts; return arr->elts + (arr->elt_size * (arr->nelts - 1)); } API_EXPORT(void) ap_array_cat(ap_array_header_t *dst, const ap_array_header_t *src) { int elt_size = dst->elt_size; if (dst->nelts + src->nelts > dst->nalloc) { int new_size = (dst->nalloc <= 0) ? 1 : dst->nalloc * 2; char *new_data; while (dst->nelts + src->nelts > new_size) { new_size *= 2; } new_data = ap_pcalloc(dst->cont, elt_size * new_size); memcpy(new_data, dst->elts, dst->nalloc * elt_size); dst->elts = new_data; dst->nalloc = new_size; } memcpy(dst->elts + dst->nelts * elt_size, src->elts, elt_size * src->nelts); dst->nelts += src->nelts; } API_EXPORT(ap_array_header_t *) ap_copy_array(struct context_t *p, const ap_array_header_t *arr) { ap_array_header_t *res = ap_make_array(p, arr->nalloc, arr->elt_size); memcpy(res->elts, arr->elts, arr->elt_size * arr->nelts); res->nelts = arr->nelts; return res; } /* This cute function copies the array header *only*, but arranges * for the data section to be copied on the first push or arraycat. * It's useful when the elements of the array being copied are * read only, but new stuff *might* get added on the end; we have the * overhead of the full copy only where it is really needed. */ static APR_INLINE void copy_array_hdr_core(ap_array_header_t *res, const ap_array_header_t *arr) { res->elts = arr->elts; res->elt_size = arr->elt_size; res->nelts = arr->nelts; res->nalloc = arr->nelts; /* Force overflow on push */ } API_EXPORT(ap_array_header_t *) ap_copy_array_hdr(struct context_t *p, const ap_array_header_t *arr) { ap_array_header_t *res; res = (ap_array_header_t *) ap_palloc(p, sizeof(ap_array_header_t)); res->cont = p; copy_array_hdr_core(res, arr); return res; } /* The above is used here to avoid consing multiple new array bodies... */ API_EXPORT(ap_array_header_t *) ap_append_arrays(struct context_t *p, const ap_array_header_t *first, const ap_array_header_t *second) { ap_array_header_t *res = ap_copy_array_hdr(p, first); ap_array_cat(res, second); return res; } /* ap_array_pstrcat generates a new string from the pool containing * the concatenated sequence of substrings referenced as elements within * the array. The string will be empty if all substrings are empty or null, * or if there are no elements in the array. * If sep is non-NUL, it will be inserted between elements as a separator. */ API_EXPORT(char *) ap_array_pstrcat(struct context_t *p, const ap_array_header_t *arr, const char sep) { char *cp, *res, **strpp; int i, len; if (arr->nelts <= 0 || arr->elts == NULL) { /* Empty table? */ return (char *) ap_pcalloc(p, 1); } /* Pass one --- find length of required string */ len = 0; for (i = 0, strpp = (char **) arr->elts; ; ++strpp) { if (strpp && *strpp != NULL) { len += strlen(*strpp); } if (++i >= arr->nelts) { break; } if (sep) { ++len; } } /* Allocate the required string */ res = (char *) ap_palloc(p, len + 1); cp = res; /* Pass two --- copy the argument strings into the result space */ for (i = 0, strpp = (char **) arr->elts; ; ++strpp) { if (strpp && *strpp != NULL) { len = strlen(*strpp); memcpy(cp, *strpp, len); cp += len; } if (++i >= arr->nelts) { break; } if (sep) { *cp++ = sep; } } *cp = '\0'; /* Return the result string */ return res; } /***************************************************************** * * The "table" functions. */ /* * XXX: if you tweak this you should look at is_empty_table() and table_elts() * in alloc.h */ #ifdef MAKE_TABLE_PROFILE static ap_table_entry_t *table_push(ap_table_t *t) { if (t->a.nelts == t->a.nalloc) { fprintf(stderr, "table_push: table created by %p hit limit of %u\n", t->creator, t->a.nalloc); } return (ap_table_entry_t *) ap_push_array(&t->a); } #else /* MAKE_TABLE_PROFILE */ #define table_push(t) ((ap_table_entry_t *) ap_push_array(&(t)->a)) #endif /* MAKE_TABLE_PROFILE */ API_EXPORT(ap_table_t *) ap_make_table(struct context_t *p, int nelts) { ap_table_t *t = ap_palloc(p, sizeof(ap_table_t)); make_array_core(&t->a, p, nelts, sizeof(ap_table_entry_t)); #ifdef MAKE_TABLE_PROFILE t->creator = __builtin_return_address(0); #endif return t; } API_EXPORT(ap_table_t *) ap_copy_table(struct context_t *p, const ap_table_t *t) { ap_table_t *new = ap_palloc(p, sizeof(ap_table_t)); #ifdef POOL_DEBUG /* we don't copy keys and values, so it's necessary that t->a.pool * have a life span at least as long as p */ if (!ap_pool_is_ancestor(t->a.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(ap_table_entry_t)); memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(ap_table_entry_t)); new->a.nelts = t->a.nelts; return new; } API_EXPORT(void) ap_clear_table(ap_table_t *t) { t->a.nelts = 0; } API_EXPORT(const char *) ap_table_get(const ap_table_t *t, const char *key) { ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; int i; if (key == NULL) { return NULL; } for (i = 0; i < t->a.nelts; ++i) { if (!strcasecmp(elts[i].key, key)) { return elts[i].val; } } return NULL; } API_EXPORT(void) ap_table_set(ap_table_t *t, const char *key, const char *val) { register int i, j, k; ap_table_entry_t *elts = (ap_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 = ap_pstrdup(t->a.cont, 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 = (ap_table_entry_t *) table_push(t); elts->key = ap_pstrdup(t->a.cont, key); elts->val = ap_pstrdup(t->a.cont, val); } } API_EXPORT(void) ap_table_setn(ap_table_t *t, const char *key, const char *val) { register int i, j, k; ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; int done = 0; #ifdef POOL_DEBUG { if (!ap_pool_is_ancestor(ap_find_pool(key), t->a.pool)) { fprintf(stderr, "table_set: key not in ancestor pool of t\n"); abort(); } if (!ap_pool_is_ancestor(ap_find_pool(val), t->a.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 = (ap_table_entry_t *) table_push(t); elts->key = (char *)key; elts->val = (char *)val; } } API_EXPORT(void) ap_table_unset(ap_table_t *t, const char *key) { register int i, j, k; ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; for (i = 0; i < t->a.nelts; ) { if (!strcasecmp(elts[i].key, key)) { /* 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; } } } API_EXPORT(void) ap_table_merge(ap_table_t *t, const char *key, const char *val) { ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; int i; for (i = 0; i < t->a.nelts; ++i) { if (!strcasecmp(elts[i].key, key)) { elts[i].val = ap_pstrcat(t->a.cont, elts[i].val, ", ", val, NULL); return; } } elts = (ap_table_entry_t *) table_push(t); elts->key = ap_pstrdup(t->a.cont, key); elts->val = ap_pstrdup(t->a.cont, val); } API_EXPORT(void) ap_table_mergen(ap_table_t *t, const char *key, const char *val) { ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; int i; #ifdef POOL_DEBUG { if (!ap_pool_is_ancestor(ap_find_pool(key), t->a.pool)) { fprintf(stderr, "table_set: key not in ancestor pool of t\n"); abort(); } if (!ap_pool_is_ancestor(ap_find_pool(val), t->a.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 = ap_pstrcat(t->a.cont, elts[i].val, ", ", val, NULL); return; } } elts = (ap_table_entry_t *) table_push(t); elts->key = (char *)key; elts->val = (char *)val; } API_EXPORT(void) ap_table_add(ap_table_t *t, const char *key, const char *val) { ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; elts = (ap_table_entry_t *) table_push(t); elts->key = ap_pstrdup(t->a.cont, key); elts->val = ap_pstrdup(t->a.cont, val); } API_EXPORT(void) ap_table_addn(ap_table_t *t, const char *key, const char *val) { ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; #ifdef POOL_DEBUG { if (!ap_pool_is_ancestor(ap_find_pool(key), t->a.pool)) { fprintf(stderr, "table_set: key not in ancestor pool of t\n"); abort(); } if (!ap_pool_is_ancestor(ap_find_pool(val), t->a.pool)) { fprintf(stderr, "table_set: key not in ancestor pool of t\n"); abort(); } } #endif elts = (ap_table_entry_t *) table_push(t); elts->key = (char *)key; elts->val = (char *)val; } API_EXPORT(ap_table_t *) ap_overlay_tables(struct context_t *p, const ap_table_t *overlay, const ap_table_t *base) { ap_table_t *res; #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 * as long as p */ if (!ap_pool_is_ancestor(overlay->a.pool, p->pool)) { fprintf(stderr, "overlay_tables: overlay's pool is not an ancestor of p\n"); abort(); } if (!ap_pool_is_ancestor(base->a.pool, p->pool)) { fprintf(stderr, "overlay_tables: base's pool is not an ancestor of p\n"); abort(); } #endif res = ap_palloc(p, sizeof(ap_table_t)); /* behave like append_arrays */ res->a.cont = p; copy_array_hdr_core(&res->a, &overlay->a); ap_array_cat(&res->a, &base->a); return res; } /* And now for something completely abstract ... * For each key value given as a vararg: * run the function pointed to as * int comp(void *r, char *key, char *value); * on each valid key-value pair in the table t that matches the vararg key, * or once for every valid key-value pair if the vararg list is empty, * until the function returns false (0) or we finish the table. * * Note that we restart the traversal for each vararg, which means that * duplicate varargs will result in multiple executions of the function * for each matching key. Note also that if the vararg list is empty, * only one traversal will be made and will cut short if comp returns 0. * * Note that the table_get and table_merge functions assume that each key in * the table is unique (i.e., no multiple entries with the same key). This * function does not make that assumption, since it (unfortunately) isn't * true for some of Apache's tables. * * Note that rec is simply passed-on to the comp function, so that the * caller can pass additional info for the task. */ API_EXPORT(void) ap_table_do(int (*comp) (void *, const char *, const char *), void *rec, const ap_table_t *t, ...) { va_list vp; char *argp; ap_table_entry_t *elts = (ap_table_entry_t *) t->a.elts; int rv, i; va_start(vp, t); 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); } } } while (argp && ((argp = va_arg(vp, char *)) != NULL)); va_end(vp); } /* 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) { const overlap_key *a = va; const overlap_key *b = vb; int r; r = strcasecmp(a->key, b->key); if (r) { return r; } return a->order - b->order; } /* prefer to use the stack for temp storage for overlaps smaller than this */ #ifndef ap_OVERLAP_TABLES_ON_STACK #define ap_OVERLAP_TABLES_ON_STACK (512) #endif API_EXPORT(void) ap_overlap_tables(ap_table_t *a, const ap_table_t *b, unsigned flags) { overlap_key cat_keys_buf[ap_OVERLAP_TABLES_ON_STACK]; overlap_key *cat_keys; int nkeys; ap_table_entry_t *e; ap_table_entry_t *last_e; overlap_key *left; overlap_key *right; overlap_key *last; nkeys = a->a.nelts + b->a.nelts; if (nkeys < ap_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 = ap_palloc(b->a.cont, sizeof(overlap_key) * nkeys); } nkeys = 0; /* Create a list of the entries from a concatenated with the entries * from b. */ e = (ap_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 = (ap_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); /* 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 = ap_palloc(a->a.cont, 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. */ if (flags & ap_OVERLAP_TABLES_MERGE) { left = cat_keys; last = left + nkeys; while (left < last) { right = left + 1; if (right == last || strcasecmp(left->key, right->key)) { ap_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 = ap_palloc(a->a.cont, len + 1); strp = value; for (;;) { memcpy(strp, left->val, left->order); strp += left->order; ++left; if (left == right) { break; } *strp++ = ','; *strp++ = ' '; } *strp = 0; ap_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; } ap_table_addn(a, (right-1)->key, (right-1)->val); left = right; } } }