xref: /aosp_15_r20/external/cronet/third_party/apache-portable-runtime/src/tables/apr_tables.c (revision 6777b5387eb2ff775bb5750e3f5d96f37fb7352b)
1  /* Licensed to the Apache Software Foundation (ASF) under one or more
2   * contributor license agreements.  See the NOTICE file distributed with
3   * this work for additional information regarding copyright ownership.
4   * The ASF licenses this file to You under the Apache License, Version 2.0
5   * (the "License"); you may not use this file except in compliance with
6   * the License.  You may obtain a copy of the License at
7   *
8   *     http://www.apache.org/licenses/LICENSE-2.0
9   *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  /*
18   * Resource allocation code... the code here is responsible for making
19   * sure that nothing leaks.
20   *
21   * rst --- 4/95 --- 6/95
22   */
23  
24  #include "apr_private.h"
25  
26  #include "apr_general.h"
27  #include "apr_pools.h"
28  #include "apr_tables.h"
29  #include "apr_strings.h"
30  #include "apr_lib.h"
31  #if APR_HAVE_STDLIB_H
32  #include <stdlib.h>
33  #endif
34  #if APR_HAVE_STRING_H
35  #include <string.h>
36  #endif
37  #if APR_HAVE_STRINGS_H
38  #include <strings.h>
39  #endif
40  
41  #if (APR_POOL_DEBUG || defined(MAKE_TABLE_PROFILE)) && APR_HAVE_STDIO_H
42  #include <stdio.h>
43  #endif
44  
45  /*****************************************************************
46   * This file contains array and apr_table_t functions only.
47   */
48  
49  /*****************************************************************
50   *
51   * The 'array' functions...
52   */
53  
make_array_core(apr_array_header_t * res,apr_pool_t * p,int nelts,int elt_size,int clear)54  static void make_array_core(apr_array_header_t *res, apr_pool_t *p,
55  			    int nelts, int elt_size, int clear)
56  {
57      /*
58       * Assure sanity if someone asks for
59       * array of zero elts.
60       */
61      if (nelts < 1) {
62          nelts = 1;
63      }
64  
65      if (clear) {
66          res->elts = apr_pcalloc(p, nelts * elt_size);
67      }
68      else {
69          res->elts = apr_palloc(p, nelts * elt_size);
70      }
71  
72      res->pool = p;
73      res->elt_size = elt_size;
74      res->nelts = 0;		/* No active elements yet... */
75      res->nalloc = nelts;	/* ...but this many allocated */
76  }
77  
apr_is_empty_array(const apr_array_header_t * a)78  APR_DECLARE(int) apr_is_empty_array(const apr_array_header_t *a)
79  {
80      return ((a == NULL) || (a->nelts == 0));
81  }
82  
apr_array_make(apr_pool_t * p,int nelts,int elt_size)83  APR_DECLARE(apr_array_header_t *) apr_array_make(apr_pool_t *p,
84  						int nelts, int elt_size)
85  {
86      apr_array_header_t *res;
87  
88      res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
89      make_array_core(res, p, nelts, elt_size, 1);
90      return res;
91  }
92  
apr_array_clear(apr_array_header_t * arr)93  APR_DECLARE(void) apr_array_clear(apr_array_header_t *arr)
94  {
95      arr->nelts = 0;
96  }
97  
apr_array_pop(apr_array_header_t * arr)98  APR_DECLARE(void *) apr_array_pop(apr_array_header_t *arr)
99  {
100      if (apr_is_empty_array(arr)) {
101          return NULL;
102      }
103  
104      return arr->elts + (arr->elt_size * (--arr->nelts));
105  }
106  
apr_array_push(apr_array_header_t * arr)107  APR_DECLARE(void *) apr_array_push(apr_array_header_t *arr)
108  {
109      if (arr->nelts == arr->nalloc) {
110          int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
111          char *new_data;
112  
113          new_data = apr_palloc(arr->pool, arr->elt_size * new_size);
114  
115          memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size);
116          memset(new_data + arr->nalloc * arr->elt_size, 0,
117                 arr->elt_size * (new_size - arr->nalloc));
118          arr->elts = new_data;
119          arr->nalloc = new_size;
120      }
121  
122      ++arr->nelts;
123      return arr->elts + (arr->elt_size * (arr->nelts - 1));
124  }
125  
apr_array_push_noclear(apr_array_header_t * arr)126  static void *apr_array_push_noclear(apr_array_header_t *arr)
127  {
128      if (arr->nelts == arr->nalloc) {
129          int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
130          char *new_data;
131  
132          new_data = apr_palloc(arr->pool, arr->elt_size * new_size);
133  
134          memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size);
135          arr->elts = new_data;
136          arr->nalloc = new_size;
137      }
138  
139      ++arr->nelts;
140      return arr->elts + (arr->elt_size * (arr->nelts - 1));
141  }
142  
apr_array_cat(apr_array_header_t * dst,const apr_array_header_t * src)143  APR_DECLARE(void) apr_array_cat(apr_array_header_t *dst,
144  			       const apr_array_header_t *src)
145  {
146      int elt_size = dst->elt_size;
147  
148      if (dst->nelts + src->nelts > dst->nalloc) {
149  	int new_size = (dst->nalloc <= 0) ? 1 : dst->nalloc * 2;
150  	char *new_data;
151  
152  	while (dst->nelts + src->nelts > new_size) {
153  	    new_size *= 2;
154  	}
155  
156  	new_data = apr_pcalloc(dst->pool, elt_size * new_size);
157  	memcpy(new_data, dst->elts, dst->nalloc * elt_size);
158  
159  	dst->elts = new_data;
160  	dst->nalloc = new_size;
161      }
162  
163      memcpy(dst->elts + dst->nelts * elt_size, src->elts,
164  	   elt_size * src->nelts);
165      dst->nelts += src->nelts;
166  }
167  
apr_array_copy(apr_pool_t * p,const apr_array_header_t * arr)168  APR_DECLARE(apr_array_header_t *) apr_array_copy(apr_pool_t *p,
169  						const apr_array_header_t *arr)
170  {
171      apr_array_header_t *res =
172          (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
173      make_array_core(res, p, arr->nalloc, arr->elt_size, 0);
174  
175      memcpy(res->elts, arr->elts, arr->elt_size * arr->nelts);
176      res->nelts = arr->nelts;
177      memset(res->elts + res->elt_size * res->nelts, 0,
178             res->elt_size * (res->nalloc - res->nelts));
179      return res;
180  }
181  
182  /* This cute function copies the array header *only*, but arranges
183   * for the data section to be copied on the first push or arraycat.
184   * It's useful when the elements of the array being copied are
185   * read only, but new stuff *might* get added on the end; we have the
186   * overhead of the full copy only where it is really needed.
187   */
188  
copy_array_hdr_core(apr_array_header_t * res,const apr_array_header_t * arr)189  static APR_INLINE void copy_array_hdr_core(apr_array_header_t *res,
190  					   const apr_array_header_t *arr)
191  {
192      res->elts = arr->elts;
193      res->elt_size = arr->elt_size;
194      res->nelts = arr->nelts;
195      res->nalloc = arr->nelts;	/* Force overflow on push */
196  }
197  
198  APR_DECLARE(apr_array_header_t *)
apr_array_copy_hdr(apr_pool_t * p,const apr_array_header_t * arr)199      apr_array_copy_hdr(apr_pool_t *p,
200  		       const apr_array_header_t *arr)
201  {
202      apr_array_header_t *res;
203  
204      res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
205      res->pool = p;
206      copy_array_hdr_core(res, arr);
207      return res;
208  }
209  
210  /* The above is used here to avoid consing multiple new array bodies... */
211  
212  APR_DECLARE(apr_array_header_t *)
apr_array_append(apr_pool_t * p,const apr_array_header_t * first,const apr_array_header_t * second)213      apr_array_append(apr_pool_t *p,
214  		      const apr_array_header_t *first,
215  		      const apr_array_header_t *second)
216  {
217      apr_array_header_t *res = apr_array_copy_hdr(p, first);
218  
219      apr_array_cat(res, second);
220      return res;
221  }
222  
223  /* apr_array_pstrcat generates a new string from the apr_pool_t containing
224   * the concatenated sequence of substrings referenced as elements within
225   * the array.  The string will be empty if all substrings are empty or null,
226   * or if there are no elements in the array.
227   * If sep is non-NUL, it will be inserted between elements as a separator.
228   */
apr_array_pstrcat(apr_pool_t * p,const apr_array_header_t * arr,const char sep)229  APR_DECLARE(char *) apr_array_pstrcat(apr_pool_t *p,
230  				     const apr_array_header_t *arr,
231  				     const char sep)
232  {
233      char *cp, *res, **strpp;
234      apr_size_t len;
235      int i;
236  
237      if (arr->nelts <= 0 || arr->elts == NULL) {    /* Empty table? */
238          return (char *) apr_pcalloc(p, 1);
239      }
240  
241      /* Pass one --- find length of required string */
242  
243      len = 0;
244      for (i = 0, strpp = (char **) arr->elts; ; ++strpp) {
245          if (strpp && *strpp != NULL) {
246              len += strlen(*strpp);
247          }
248          if (++i >= arr->nelts) {
249              break;
250  	}
251          if (sep) {
252              ++len;
253  	}
254      }
255  
256      /* Allocate the required string */
257  
258      res = (char *) apr_palloc(p, len + 1);
259      cp = res;
260  
261      /* Pass two --- copy the argument strings into the result space */
262  
263      for (i = 0, strpp = (char **) arr->elts; ; ++strpp) {
264          if (strpp && *strpp != NULL) {
265              len = strlen(*strpp);
266              memcpy(cp, *strpp, len);
267              cp += len;
268          }
269          if (++i >= arr->nelts) {
270              break;
271  	}
272          if (sep) {
273              *cp++ = sep;
274  	}
275      }
276  
277      *cp = '\0';
278  
279      /* Return the result string */
280  
281      return res;
282  }
283  
284  
285  /*****************************************************************
286   *
287   * The "table" functions.
288   */
289  
290  #if APR_CHARSET_EBCDIC
291  #define CASE_MASK 0xbfbfbfbf
292  #else
293  #define CASE_MASK 0xdfdfdfdf
294  #endif
295  
296  #define TABLE_HASH_SIZE 32
297  #define TABLE_INDEX_MASK 0x1f
298  #define TABLE_HASH(key)  (TABLE_INDEX_MASK & *(unsigned char *)(key))
299  #define TABLE_INDEX_IS_INITIALIZED(t, i) ((t)->index_initialized & (1 << (i)))
300  #define TABLE_SET_INDEX_INITIALIZED(t, i) ((t)->index_initialized |= (1 << (i)))
301  
302  /* Compute the "checksum" for a key, consisting of the first
303   * 4 bytes, normalized for case-insensitivity and packed into
304   * an int...this checksum allows us to do a single integer
305   * comparison as a fast check to determine whether we can
306   * skip a strcasecmp
307   */
308  #define COMPUTE_KEY_CHECKSUM(key, checksum)    \
309  {                                              \
310      const char *k = (key);                     \
311      apr_uint32_t c = (apr_uint32_t)*k;         \
312      (checksum) = c;                            \
313      (checksum) <<= 8;                          \
314      if (c) {                                   \
315          c = (apr_uint32_t)*++k;                \
316          checksum |= c;                         \
317      }                                          \
318      (checksum) <<= 8;                          \
319      if (c) {                                   \
320          c = (apr_uint32_t)*++k;                \
321          checksum |= c;                         \
322      }                                          \
323      (checksum) <<= 8;                          \
324      if (c) {                                   \
325          c = (apr_uint32_t)*++k;                \
326          checksum |= c;                         \
327      }                                          \
328      checksum &= CASE_MASK;                     \
329  }
330  
331  /** The opaque string-content table type */
332  struct apr_table_t {
333      /* This has to be first to promote backwards compatibility with
334       * older modules which cast a apr_table_t * to an apr_array_header_t *...
335       * they should use the apr_table_elts() function for most of the
336       * cases they do this for.
337       */
338      /** The underlying array for the table */
339      apr_array_header_t a;
340  #ifdef MAKE_TABLE_PROFILE
341      /** Who created the array. */
342      void *creator;
343  #endif
344      /* An index to speed up table lookups.  The way this works is:
345       *   - Hash the key into the index:
346       *     - index_first[TABLE_HASH(key)] is the offset within
347       *       the table of the first entry with that key
348       *     - index_last[TABLE_HASH(key)] is the offset within
349       *       the table of the last entry with that key
350       *   - If (and only if) there is no entry in the table whose
351       *     key hashes to index element i, then the i'th bit
352       *     of index_initialized will be zero.  (Check this before
353       *     trying to use index_first[i] or index_last[i]!)
354       */
355      apr_uint32_t index_initialized;
356      int index_first[TABLE_HASH_SIZE];
357      int index_last[TABLE_HASH_SIZE];
358  };
359  
360  /* keep state for apr_table_getm() */
361  typedef struct
362  {
363      apr_pool_t *p;
364      const char *first;
365      apr_array_header_t *merged;
366  } table_getm_t;
367  
368  /*
369   * NOTICE: if you tweak this you should look at is_empty_table()
370   * and table_elts() in alloc.h
371   */
372  #ifdef MAKE_TABLE_PROFILE
do_table_push(const char * func,apr_table_t * t)373  static apr_table_entry_t *do_table_push(const char *func, apr_table_t *t)
374  {
375      if (t->a.nelts == t->a.nalloc) {
376          fprintf(stderr, "%s: table created by %p hit limit of %u\n",
377                  func ? func : "table_push", t->creator, t->a.nalloc);
378      }
379      return (apr_table_entry_t *) apr_array_push_noclear(&t->a);
380  }
381  #if defined(__GNUC__) && __GNUC__ >= 2
382  #define table_push(t) do_table_push(__FUNCTION__, t)
383  #else
384  #define table_push(t) do_table_push(NULL, t)
385  #endif
386  #else /* MAKE_TABLE_PROFILE */
387  #define table_push(t)	((apr_table_entry_t *) apr_array_push_noclear(&(t)->a))
388  #endif /* MAKE_TABLE_PROFILE */
389  
apr_table_elts(const apr_table_t * t)390  APR_DECLARE(const apr_array_header_t *) apr_table_elts(const apr_table_t *t)
391  {
392      return (const apr_array_header_t *)t;
393  }
394  
apr_is_empty_table(const apr_table_t * t)395  APR_DECLARE(int) apr_is_empty_table(const apr_table_t *t)
396  {
397      return ((t == NULL) || (t->a.nelts == 0));
398  }
399  
apr_table_make(apr_pool_t * p,int nelts)400  APR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts)
401  {
402      apr_table_t *t = apr_palloc(p, sizeof(apr_table_t));
403  
404      make_array_core(&t->a, p, nelts, sizeof(apr_table_entry_t), 0);
405  #ifdef MAKE_TABLE_PROFILE
406      t->creator = __builtin_return_address(0);
407  #endif
408      t->index_initialized = 0;
409      return t;
410  }
411  
apr_table_copy(apr_pool_t * p,const apr_table_t * t)412  APR_DECLARE(apr_table_t *) apr_table_copy(apr_pool_t *p, const apr_table_t *t)
413  {
414      apr_table_t *new = apr_palloc(p, sizeof(apr_table_t));
415  
416  #if APR_POOL_DEBUG
417      /* we don't copy keys and values, so it's necessary that t->a.pool
418       * have a life span at least as long as p
419       */
420      if (!apr_pool_is_ancestor(t->a.pool, p)) {
421  	fprintf(stderr, "apr_table_copy: t's pool is not an ancestor of p\n");
422  	abort();
423      }
424  #endif
425      make_array_core(&new->a, p, t->a.nalloc, sizeof(apr_table_entry_t), 0);
426      memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t));
427      new->a.nelts = t->a.nelts;
428      memcpy(new->index_first, t->index_first, sizeof(int) * TABLE_HASH_SIZE);
429      memcpy(new->index_last, t->index_last, sizeof(int) * TABLE_HASH_SIZE);
430      new->index_initialized = t->index_initialized;
431      return new;
432  }
433  
apr_table_clone(apr_pool_t * p,const apr_table_t * t)434  APR_DECLARE(apr_table_t *) apr_table_clone(apr_pool_t *p, const apr_table_t *t)
435  {
436      const apr_array_header_t *array = apr_table_elts(t);
437      apr_table_entry_t *elts = (apr_table_entry_t *) array->elts;
438      apr_table_t *new = apr_table_make(p, array->nelts);
439      int i;
440  
441      for (i = 0; i < array->nelts; i++) {
442          apr_table_add(new, elts[i].key, elts[i].val);
443      }
444  
445      return new;
446  }
447  
table_reindex(apr_table_t * t)448  static void table_reindex(apr_table_t *t)
449  {
450      int i;
451      int hash;
452      apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
453  
454      t->index_initialized = 0;
455      for (i = 0; i < t->a.nelts; i++, next_elt++) {
456          hash = TABLE_HASH(next_elt->key);
457          t->index_last[hash] = i;
458          if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
459              t->index_first[hash] = i;
460              TABLE_SET_INDEX_INITIALIZED(t, hash);
461          }
462      }
463  }
464  
apr_table_clear(apr_table_t * t)465  APR_DECLARE(void) apr_table_clear(apr_table_t *t)
466  {
467      t->a.nelts = 0;
468      t->index_initialized = 0;
469  }
470  
apr_table_get(const apr_table_t * t,const char * key)471  APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)
472  {
473      apr_table_entry_t *next_elt;
474      apr_table_entry_t *end_elt;
475      apr_uint32_t checksum;
476      int hash;
477  
478      if (key == NULL) {
479  	return NULL;
480      }
481  
482      hash = TABLE_HASH(key);
483      if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
484          return NULL;
485      }
486      COMPUTE_KEY_CHECKSUM(key, checksum);
487      next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
488      end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
489  
490      for (; next_elt <= end_elt; next_elt++) {
491  	if ((checksum == next_elt->key_checksum) &&
492              !strcasecmp(next_elt->key, key)) {
493  	    return next_elt->val;
494  	}
495      }
496  
497      return NULL;
498  }
499  
apr_table_set(apr_table_t * t,const char * key,const char * val)500  APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,
501                                  const char *val)
502  {
503      apr_table_entry_t *next_elt;
504      apr_table_entry_t *end_elt;
505      apr_table_entry_t *table_end;
506      apr_uint32_t checksum;
507      int hash;
508  
509      COMPUTE_KEY_CHECKSUM(key, checksum);
510      hash = TABLE_HASH(key);
511      if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
512          t->index_first[hash] = t->a.nelts;
513          TABLE_SET_INDEX_INITIALIZED(t, hash);
514          goto add_new_elt;
515      }
516      next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
517      end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
518      table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts;
519  
520      for (; next_elt <= end_elt; next_elt++) {
521  	if ((checksum == next_elt->key_checksum) &&
522              !strcasecmp(next_elt->key, key)) {
523  
524              /* Found an existing entry with the same key, so overwrite it */
525  
526              int must_reindex = 0;
527              apr_table_entry_t *dst_elt = NULL;
528  
529              next_elt->val = apr_pstrdup(t->a.pool, val);
530  
531              /* Remove any other instances of this key */
532              for (next_elt++; next_elt <= end_elt; next_elt++) {
533                  if ((checksum == next_elt->key_checksum) &&
534                      !strcasecmp(next_elt->key, key)) {
535                      t->a.nelts--;
536                      if (!dst_elt) {
537                          dst_elt = next_elt;
538                      }
539                  }
540                  else if (dst_elt) {
541                      *dst_elt++ = *next_elt;
542                      must_reindex = 1;
543                  }
544              }
545  
546              /* If we've removed anything, shift over the remainder
547               * of the table (note that the previous loop didn't
548               * run to the end of the table, just to the last match
549               * for the index)
550               */
551              if (dst_elt) {
552                  for (; next_elt < table_end; next_elt++) {
553                      *dst_elt++ = *next_elt;
554                  }
555                  must_reindex = 1;
556              }
557              if (must_reindex) {
558                  table_reindex(t);
559              }
560              return;
561          }
562      }
563  
564  add_new_elt:
565      t->index_last[hash] = t->a.nelts;
566      next_elt = (apr_table_entry_t *) table_push(t);
567      next_elt->key = apr_pstrdup(t->a.pool, key);
568      next_elt->val = apr_pstrdup(t->a.pool, val);
569      next_elt->key_checksum = checksum;
570  }
571  
apr_table_setn(apr_table_t * t,const char * key,const char * val)572  APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key,
573                                   const char *val)
574  {
575      apr_table_entry_t *next_elt;
576      apr_table_entry_t *end_elt;
577      apr_table_entry_t *table_end;
578      apr_uint32_t checksum;
579      int hash;
580  
581      COMPUTE_KEY_CHECKSUM(key, checksum);
582      hash = TABLE_HASH(key);
583      if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
584          t->index_first[hash] = t->a.nelts;
585          TABLE_SET_INDEX_INITIALIZED(t, hash);
586          goto add_new_elt;
587      }
588      next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
589      end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
590      table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts;
591  
592      for (; next_elt <= end_elt; next_elt++) {
593  	if ((checksum == next_elt->key_checksum) &&
594              !strcasecmp(next_elt->key, key)) {
595  
596              /* Found an existing entry with the same key, so overwrite it */
597  
598              int must_reindex = 0;
599              apr_table_entry_t *dst_elt = NULL;
600  
601              next_elt->val = (char *)val;
602  
603              /* Remove any other instances of this key */
604              for (next_elt++; next_elt <= end_elt; next_elt++) {
605                  if ((checksum == next_elt->key_checksum) &&
606                      !strcasecmp(next_elt->key, key)) {
607                      t->a.nelts--;
608                      if (!dst_elt) {
609                          dst_elt = next_elt;
610                      }
611                  }
612                  else if (dst_elt) {
613                      *dst_elt++ = *next_elt;
614                      must_reindex = 1;
615                  }
616              }
617  
618              /* If we've removed anything, shift over the remainder
619               * of the table (note that the previous loop didn't
620               * run to the end of the table, just to the last match
621               * for the index)
622               */
623              if (dst_elt) {
624                  for (; next_elt < table_end; next_elt++) {
625                      *dst_elt++ = *next_elt;
626                  }
627                  must_reindex = 1;
628              }
629              if (must_reindex) {
630                  table_reindex(t);
631              }
632              return;
633          }
634      }
635  
636  add_new_elt:
637      t->index_last[hash] = t->a.nelts;
638      next_elt = (apr_table_entry_t *) table_push(t);
639      next_elt->key = (char *)key;
640      next_elt->val = (char *)val;
641      next_elt->key_checksum = checksum;
642  }
643  
apr_table_unset(apr_table_t * t,const char * key)644  APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key)
645  {
646      apr_table_entry_t *next_elt;
647      apr_table_entry_t *end_elt;
648      apr_table_entry_t *dst_elt;
649      apr_uint32_t checksum;
650      int hash;
651      int must_reindex;
652  
653      hash = TABLE_HASH(key);
654      if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
655          return;
656      }
657      COMPUTE_KEY_CHECKSUM(key, checksum);
658      next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
659      end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
660      must_reindex = 0;
661      for (; next_elt <= end_elt; next_elt++) {
662  	if ((checksum == next_elt->key_checksum) &&
663              !strcasecmp(next_elt->key, key)) {
664  
665              /* Found a match: remove this entry, plus any additional
666               * matches for the same key that might follow
667               */
668              apr_table_entry_t *table_end = ((apr_table_entry_t *) t->a.elts) +
669                  t->a.nelts;
670              t->a.nelts--;
671              dst_elt = next_elt;
672              for (next_elt++; next_elt <= end_elt; next_elt++) {
673                  if ((checksum == next_elt->key_checksum) &&
674                      !strcasecmp(next_elt->key, key)) {
675                      t->a.nelts--;
676                  }
677                  else {
678                      *dst_elt++ = *next_elt;
679                  }
680              }
681  
682              /* Shift over the remainder of the table (note that
683               * the previous loop didn't run to the end of the table,
684               * just to the last match for the index)
685               */
686              for (; next_elt < table_end; next_elt++) {
687                  *dst_elt++ = *next_elt;
688              }
689              must_reindex = 1;
690              break;
691          }
692      }
693      if (must_reindex) {
694          table_reindex(t);
695      }
696  }
697  
apr_table_merge(apr_table_t * t,const char * key,const char * val)698  APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key,
699  				 const char *val)
700  {
701      apr_table_entry_t *next_elt;
702      apr_table_entry_t *end_elt;
703      apr_uint32_t checksum;
704      int hash;
705  
706      COMPUTE_KEY_CHECKSUM(key, checksum);
707      hash = TABLE_HASH(key);
708      if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
709          t->index_first[hash] = t->a.nelts;
710          TABLE_SET_INDEX_INITIALIZED(t, hash);
711          goto add_new_elt;
712      }
713      next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
714      end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
715  
716      for (; next_elt <= end_elt; next_elt++) {
717  	if ((checksum == next_elt->key_checksum) &&
718              !strcasecmp(next_elt->key, key)) {
719  
720              /* Found an existing entry with the same key, so merge with it */
721  	    next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
722                                          val, NULL);
723              return;
724          }
725      }
726  
727  add_new_elt:
728      t->index_last[hash] = t->a.nelts;
729      next_elt = (apr_table_entry_t *) table_push(t);
730      next_elt->key = apr_pstrdup(t->a.pool, key);
731      next_elt->val = apr_pstrdup(t->a.pool, val);
732      next_elt->key_checksum = checksum;
733  }
734  
apr_table_mergen(apr_table_t * t,const char * key,const char * val)735  APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key,
736  				  const char *val)
737  {
738      apr_table_entry_t *next_elt;
739      apr_table_entry_t *end_elt;
740      apr_uint32_t checksum;
741      int hash;
742  
743  #if APR_POOL_DEBUG
744      {
745  	apr_pool_t *pool;
746  	pool = apr_pool_find(key);
747  	if ((pool != (apr_pool_t *)key)
748              && (!apr_pool_is_ancestor(pool, t->a.pool))) {
749  	    fprintf(stderr, "apr_table_mergen: key not in ancestor pool of t\n");
750  	    abort();
751  	}
752  	pool = apr_pool_find(val);
753  	if ((pool != (apr_pool_t *)val)
754              && (!apr_pool_is_ancestor(pool, t->a.pool))) {
755  	    fprintf(stderr, "apr_table_mergen: val not in ancestor pool of t\n");
756  	    abort();
757  	}
758      }
759  #endif
760  
761      COMPUTE_KEY_CHECKSUM(key, checksum);
762      hash = TABLE_HASH(key);
763      if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
764          t->index_first[hash] = t->a.nelts;
765          TABLE_SET_INDEX_INITIALIZED(t, hash);
766          goto add_new_elt;
767      }
768      next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
769      end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
770  
771      for (; next_elt <= end_elt; next_elt++) {
772  	if ((checksum == next_elt->key_checksum) &&
773              !strcasecmp(next_elt->key, key)) {
774  
775              /* Found an existing entry with the same key, so merge with it */
776  	    next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
777                                          val, NULL);
778              return;
779          }
780      }
781  
782  add_new_elt:
783      t->index_last[hash] = t->a.nelts;
784      next_elt = (apr_table_entry_t *) table_push(t);
785      next_elt->key = (char *)key;
786      next_elt->val = (char *)val;
787      next_elt->key_checksum = checksum;
788  }
789  
apr_table_add(apr_table_t * t,const char * key,const char * val)790  APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key,
791  			       const char *val)
792  {
793      apr_table_entry_t *elts;
794      apr_uint32_t checksum;
795      int hash;
796  
797      hash = TABLE_HASH(key);
798      t->index_last[hash] = t->a.nelts;
799      if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
800          t->index_first[hash] = t->a.nelts;
801          TABLE_SET_INDEX_INITIALIZED(t, hash);
802      }
803      COMPUTE_KEY_CHECKSUM(key, checksum);
804      elts = (apr_table_entry_t *) table_push(t);
805      elts->key = apr_pstrdup(t->a.pool, key);
806      elts->val = apr_pstrdup(t->a.pool, val);
807      elts->key_checksum = checksum;
808  }
809  
apr_table_addn(apr_table_t * t,const char * key,const char * val)810  APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key,
811  				const char *val)
812  {
813      apr_table_entry_t *elts;
814      apr_uint32_t checksum;
815      int hash;
816  
817  #if APR_POOL_DEBUG
818      {
819  	if (!apr_pool_is_ancestor(apr_pool_find(key), t->a.pool)) {
820  	    fprintf(stderr, "apr_table_addn: key not in ancestor pool of t\n");
821  	    abort();
822  	}
823  	if (!apr_pool_is_ancestor(apr_pool_find(val), t->a.pool)) {
824  	    fprintf(stderr, "apr_table_addn: val not in ancestor pool of t\n");
825  	    abort();
826  	}
827      }
828  #endif
829  
830      hash = TABLE_HASH(key);
831      t->index_last[hash] = t->a.nelts;
832      if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
833          t->index_first[hash] = t->a.nelts;
834          TABLE_SET_INDEX_INITIALIZED(t, hash);
835      }
836      COMPUTE_KEY_CHECKSUM(key, checksum);
837      elts = (apr_table_entry_t *) table_push(t);
838      elts->key = (char *)key;
839      elts->val = (char *)val;
840      elts->key_checksum = checksum;
841  }
842  
apr_table_overlay(apr_pool_t * p,const apr_table_t * overlay,const apr_table_t * base)843  APR_DECLARE(apr_table_t *) apr_table_overlay(apr_pool_t *p,
844  					     const apr_table_t *overlay,
845  					     const apr_table_t *base)
846  {
847      apr_table_t *res;
848  
849  #if APR_POOL_DEBUG
850      /* we don't copy keys and values, so it's necessary that
851       * overlay->a.pool and base->a.pool have a life span at least
852       * as long as p
853       */
854      if (!apr_pool_is_ancestor(overlay->a.pool, p)) {
855  	fprintf(stderr,
856  		"apr_table_overlay: overlay's pool is not an ancestor of p\n");
857  	abort();
858      }
859      if (!apr_pool_is_ancestor(base->a.pool, p)) {
860  	fprintf(stderr,
861  		"apr_table_overlay: base's pool is not an ancestor of p\n");
862  	abort();
863      }
864  #endif
865  
866      res = apr_palloc(p, sizeof(apr_table_t));
867      /* behave like append_arrays */
868      res->a.pool = p;
869      copy_array_hdr_core(&res->a, &overlay->a);
870      apr_array_cat(&res->a, &base->a);
871      table_reindex(res);
872      return res;
873  }
874  
875  /* And now for something completely abstract ...
876  
877   * For each key value given as a vararg:
878   *   run the function pointed to as
879   *     int comp(void *r, char *key, char *value);
880   *   on each valid key-value pair in the apr_table_t t that matches the vararg key,
881   *   or once for every valid key-value pair if the vararg list is empty,
882   *   until the function returns false (0) or we finish the table.
883   *
884   * Note that we restart the traversal for each vararg, which means that
885   * duplicate varargs will result in multiple executions of the function
886   * for each matching key.  Note also that if the vararg list is empty,
887   * only one traversal will be made and will cut short if comp returns 0.
888   *
889   * Note that the table_get and table_merge functions assume that each key in
890   * the apr_table_t is unique (i.e., no multiple entries with the same key).  This
891   * function does not make that assumption, since it (unfortunately) isn't
892   * true for some of Apache's tables.
893   *
894   * Note that rec is simply passed-on to the comp function, so that the
895   * caller can pass additional info for the task.
896   *
897   * ADDENDUM for apr_table_vdo():
898   *
899   * The caching api will allow a user to walk the header values:
900   *
901   * apr_status_t apr_cache_el_header_walk(apr_cache_el *el,
902   *    int (*comp)(void *, const char *, const char *), void *rec, ...);
903   *
904   * So it can be ..., however from there I use a  callback that use a va_list:
905   *
906   * apr_status_t (*cache_el_header_walk)(apr_cache_el *el,
907   *    int (*comp)(void *, const char *, const char *), void *rec, va_list);
908   *
909   * To pass those ...'s on down to the actual module that will handle walking
910   * their headers, in the file case this is actually just an apr_table - and
911   * rather than reimplementing apr_table_do (which IMHO would be bad) I just
912   * called it with the va_list. For mod_shmem_cache I don't need it since I
913   * can't use apr_table's, but mod_file_cache should (though a good hash would
914   * be better, but that's a different issue :).
915   *
916   * So to make mod_file_cache easier to maintain, it's a good thing
917   */
apr_table_do(apr_table_do_callback_fn_t * comp,void * rec,const apr_table_t * t,...)918  APR_DECLARE_NONSTD(int) apr_table_do(apr_table_do_callback_fn_t *comp,
919                                       void *rec, const apr_table_t *t, ...)
920  {
921      int rv;
922  
923      va_list vp;
924      va_start(vp, t);
925      rv = apr_table_vdo(comp, rec, t, vp);
926      va_end(vp);
927  
928      return rv;
929  }
930  
931  /* XXX: do the semantics of this routine make any sense?  Right now,
932   * if the caller passed in a non-empty va_list of keys to search for,
933   * the "early termination" facility only terminates on *that* key; other
934   * keys will continue to process.  Note that this only has any effect
935   * at all if there are multiple entries in the table with the same key,
936   * otherwise the called function can never effectively early-terminate
937   * this function, as the zero return value is effectively ignored.
938   *
939   * Note also that this behavior is at odds with the behavior seen if an
940   * empty va_list is passed in -- in that case, a zero return value terminates
941   * the entire apr_table_vdo (which is what I think should happen in
942   * both cases).
943   *
944   * If nobody objects soon, I'm going to change the order of the nested
945   * loops in this function so that any zero return value from the (*comp)
946   * function will cause a full termination of apr_table_vdo.  I'm hesitant
947   * at the moment because these (funky) semantics have been around for a
948   * very long time, and although Apache doesn't seem to use them at all,
949   * some third-party vendor might.  I can only think of one possible reason
950   * the existing semantics would make any sense, and it's very Apache-centric,
951   * which is this: if (*comp) is looking for matches of a particular
952   * substring in request headers (let's say it's looking for a particular
953   * cookie name in the Set-Cookie headers), then maybe it wants to be
954   * able to stop searching early as soon as it finds that one and move
955   * on to the next key.  That's only an optimization of course, but changing
956   * the behavior of this function would mean that any code that tried
957   * to do that would stop working right.
958   *
959   * Sigh.  --JCW, 06/28/02
960   */
apr_table_vdo(apr_table_do_callback_fn_t * comp,void * rec,const apr_table_t * t,va_list vp)961  APR_DECLARE(int) apr_table_vdo(apr_table_do_callback_fn_t *comp,
962                                 void *rec, const apr_table_t *t, va_list vp)
963  {
964      char *argp;
965      apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
966      int vdorv = 1;
967  
968      argp = va_arg(vp, char *);
969      do {
970          int rv = 1, i;
971          if (argp) {
972              /* Scan for entries that match the next key */
973              int hash = TABLE_HASH(argp);
974              if (TABLE_INDEX_IS_INITIALIZED(t, hash)) {
975                  apr_uint32_t checksum;
976                  COMPUTE_KEY_CHECKSUM(argp, checksum);
977                  for (i = t->index_first[hash];
978                       rv && (i <= t->index_last[hash]); ++i) {
979                      if (elts[i].key && (checksum == elts[i].key_checksum) &&
980                                          !strcasecmp(elts[i].key, argp)) {
981                          rv = (*comp) (rec, elts[i].key, elts[i].val);
982                      }
983                  }
984              }
985          }
986          else {
987              /* Scan the entire table */
988              for (i = 0; rv && (i < t->a.nelts); ++i) {
989                  if (elts[i].key) {
990                      rv = (*comp) (rec, elts[i].key, elts[i].val);
991                  }
992              }
993          }
994          if (rv == 0) {
995              vdorv = 0;
996          }
997      } while (argp && ((argp = va_arg(vp, char *)) != NULL));
998  
999      return vdorv;
1000  }
1001  
table_mergesort(apr_pool_t * pool,apr_table_entry_t ** values,apr_size_t n)1002  static apr_table_entry_t **table_mergesort(apr_pool_t *pool,
1003                                             apr_table_entry_t **values,
1004                                             apr_size_t n)
1005  {
1006      /* Bottom-up mergesort, based on design in Sedgewick's "Algorithms
1007       * in C," chapter 8
1008       */
1009      apr_table_entry_t **values_tmp =
1010          (apr_table_entry_t **)apr_palloc(pool, n * sizeof(apr_table_entry_t*));
1011      apr_size_t i;
1012      apr_size_t blocksize;
1013  
1014      /* First pass: sort pairs of elements (blocksize=1) */
1015      for (i = 0; i + 1 < n; i += 2) {
1016          if (strcasecmp(values[i]->key, values[i + 1]->key) > 0) {
1017              apr_table_entry_t *swap = values[i];
1018              values[i] = values[i + 1];
1019              values[i + 1] = swap;
1020          }
1021      }
1022  
1023      /* Merge successively larger blocks */
1024      blocksize = 2;
1025      while (blocksize < n) {
1026          apr_table_entry_t **dst = values_tmp;
1027          apr_size_t next_start;
1028          apr_table_entry_t **swap;
1029  
1030          /* Merge consecutive pairs blocks of the next blocksize.
1031           * Within a block, elements are in sorted order due to
1032           * the previous iteration.
1033           */
1034          for (next_start = 0; next_start + blocksize < n;
1035               next_start += (blocksize + blocksize)) {
1036  
1037              apr_size_t block1_start = next_start;
1038              apr_size_t block2_start = block1_start + blocksize;
1039              apr_size_t block1_end = block2_start;
1040              apr_size_t block2_end = block2_start + blocksize;
1041              if (block2_end > n) {
1042                  /* The last block may be smaller than blocksize */
1043                  block2_end = n;
1044              }
1045              for (;;) {
1046  
1047                  /* Merge the next two blocks:
1048                   * Pick the smaller of the next element from
1049                   * block 1 and the next element from block 2.
1050                   * Once either of the blocks is emptied, copy
1051                   * over all the remaining elements from the
1052                   * other block
1053                   */
1054                  if (block1_start == block1_end) {
1055                      for (; block2_start < block2_end; block2_start++) {
1056                          *dst++ = values[block2_start];
1057                      }
1058                      break;
1059                  }
1060                  else if (block2_start == block2_end) {
1061                      for (; block1_start < block1_end; block1_start++) {
1062                          *dst++ = values[block1_start];
1063                      }
1064                      break;
1065                  }
1066                  if (strcasecmp(values[block1_start]->key,
1067                                 values[block2_start]->key) > 0) {
1068                      *dst++ = values[block2_start++];
1069                  }
1070                  else {
1071                      *dst++ = values[block1_start++];
1072                  }
1073              }
1074          }
1075  
1076          /* If n is not a multiple of 2*blocksize, some elements
1077           * will be left over at the end of the array.
1078           */
1079          for (i = dst - values_tmp; i < n; i++) {
1080              values_tmp[i] = values[i];
1081          }
1082  
1083          /* The output array of this pass becomes the input
1084           * array of the next pass, and vice versa
1085           */
1086          swap = values_tmp;
1087          values_tmp = values;
1088          values = swap;
1089  
1090          blocksize += blocksize;
1091      }
1092  
1093      return values;
1094  }
1095  
apr_table_compress(apr_table_t * t,unsigned flags)1096  APR_DECLARE(void) apr_table_compress(apr_table_t *t, unsigned flags)
1097  {
1098      apr_table_entry_t **sort_array;
1099      apr_table_entry_t **sort_next;
1100      apr_table_entry_t **sort_end;
1101      apr_table_entry_t *table_next;
1102      apr_table_entry_t **last;
1103      int i;
1104      int dups_found;
1105  
1106      if (t->a.nelts <= 1) {
1107          return;
1108      }
1109  
1110      /* Copy pointers to all the table elements into an
1111       * array and sort to allow for easy detection of
1112       * duplicate keys
1113       */
1114      sort_array = (apr_table_entry_t **)
1115          apr_palloc(t->a.pool, t->a.nelts * sizeof(apr_table_entry_t*));
1116      sort_next = sort_array;
1117      table_next = (apr_table_entry_t *)t->a.elts;
1118      i = t->a.nelts;
1119      do {
1120          *sort_next++ = table_next++;
1121      } while (--i);
1122  
1123      /* Note: the merge is done with mergesort instead of quicksort
1124       * because mergesort is a stable sort and runs in n*log(n)
1125       * time regardless of its inputs (quicksort is quadratic in
1126       * the worst case)
1127       */
1128      sort_array = table_mergesort(t->a.pool, sort_array, t->a.nelts);
1129  
1130      /* Process any duplicate keys */
1131      dups_found = 0;
1132      sort_next = sort_array;
1133      sort_end = sort_array + t->a.nelts;
1134      last = sort_next++;
1135      while (sort_next < sort_end) {
1136          if (((*sort_next)->key_checksum == (*last)->key_checksum) &&
1137              !strcasecmp((*sort_next)->key, (*last)->key)) {
1138              apr_table_entry_t **dup_last = sort_next + 1;
1139              dups_found = 1;
1140              while ((dup_last < sort_end) &&
1141                     ((*dup_last)->key_checksum == (*last)->key_checksum) &&
1142                     !strcasecmp((*dup_last)->key, (*last)->key)) {
1143                  dup_last++;
1144              }
1145              dup_last--; /* Elements from last through dup_last, inclusive,
1146                           * all have the same key
1147                           */
1148              if (flags == APR_OVERLAP_TABLES_MERGE) {
1149                  apr_size_t len = 0;
1150                  apr_table_entry_t **next = last;
1151                  char *new_val;
1152                  char *val_dst;
1153                  do {
1154                      len += strlen((*next)->val);
1155                      len += 2; /* for ", " or trailing null */
1156                  } while (++next <= dup_last);
1157                  new_val = (char *)apr_palloc(t->a.pool, len);
1158                  val_dst = new_val;
1159                  next = last;
1160                  for (;;) {
1161                      strcpy(val_dst, (*next)->val);
1162                      val_dst += strlen((*next)->val);
1163                      next++;
1164                      if (next > dup_last) {
1165                          *val_dst = 0;
1166                          break;
1167                      }
1168                      else {
1169                          *val_dst++ = ',';
1170                          *val_dst++ = ' ';
1171                      }
1172                  }
1173                  (*last)->val = new_val;
1174              }
1175              else { /* overwrite */
1176                  (*last)->val = (*dup_last)->val;
1177              }
1178              do {
1179                  (*sort_next)->key = NULL;
1180              } while (++sort_next <= dup_last);
1181          }
1182          else {
1183              last = sort_next++;
1184          }
1185      }
1186  
1187      /* Shift elements to the left to fill holes left by removing duplicates */
1188      if (dups_found) {
1189          apr_table_entry_t *src = (apr_table_entry_t *)t->a.elts;
1190          apr_table_entry_t *dst = (apr_table_entry_t *)t->a.elts;
1191          apr_table_entry_t *last_elt = src + t->a.nelts;
1192          do {
1193              if (src->key) {
1194                  *dst++ = *src;
1195              }
1196          } while (++src < last_elt);
1197          t->a.nelts -= (int)(last_elt - dst);
1198      }
1199  
1200      table_reindex(t);
1201  }
1202  
apr_table_cat(apr_table_t * t,const apr_table_t * s)1203  static void apr_table_cat(apr_table_t *t, const apr_table_t *s)
1204  {
1205      const int n = t->a.nelts;
1206      register int idx;
1207  
1208      apr_array_cat(&t->a,&s->a);
1209  
1210      if (n == 0) {
1211          memcpy(t->index_first,s->index_first,sizeof(int) * TABLE_HASH_SIZE);
1212          memcpy(t->index_last, s->index_last, sizeof(int) * TABLE_HASH_SIZE);
1213          t->index_initialized = s->index_initialized;
1214          return;
1215      }
1216  
1217      for (idx = 0; idx < TABLE_HASH_SIZE; ++idx) {
1218          if (TABLE_INDEX_IS_INITIALIZED(s, idx)) {
1219              t->index_last[idx] = s->index_last[idx] + n;
1220              if (!TABLE_INDEX_IS_INITIALIZED(t, idx)) {
1221                  t->index_first[idx] = s->index_first[idx] + n;
1222              }
1223          }
1224      }
1225  
1226      t->index_initialized |= s->index_initialized;
1227  }
1228  
apr_table_overlap(apr_table_t * a,const apr_table_t * b,unsigned flags)1229  APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b,
1230  				    unsigned flags)
1231  {
1232      if (a->a.nelts + b->a.nelts == 0) {
1233          return;
1234      }
1235  
1236  #if APR_POOL_DEBUG
1237      /* Since the keys and values are not copied, it's required that
1238       * b->a.pool has a lifetime at least as long as a->a.pool. */
1239      if (!apr_pool_is_ancestor(b->a.pool, a->a.pool)) {
1240          fprintf(stderr, "apr_table_overlap: b's pool is not an ancestor of a's\n");
1241          abort();
1242      }
1243  #endif
1244  
1245      apr_table_cat(a, b);
1246  
1247      apr_table_compress(a, flags);
1248  }
1249  
table_getm_do(void * v,const char * key,const char * val)1250  static int table_getm_do(void *v, const char *key, const char *val)
1251  {
1252      table_getm_t *state = (table_getm_t *) v;
1253  
1254      if (!state->first) {
1255          /**
1256           * The most common case is a single header, and this is covered by
1257           * a fast path that doesn't allocate any memory. On the second and
1258           * subsequent header, an array is created and the array concatenated
1259           * together to form the final value.
1260           */
1261          state->first = val;
1262      }
1263      else {
1264          const char **elt;
1265          if (!state->merged) {
1266              state->merged = apr_array_make(state->p, 10, sizeof(const char *));
1267              elt = apr_array_push(state->merged);
1268              *elt = state->first;
1269          }
1270          elt = apr_array_push(state->merged);
1271          *elt = val;
1272      }
1273      return 1;
1274  }
1275  
apr_table_getm(apr_pool_t * p,const apr_table_t * t,const char * key)1276  APR_DECLARE(const char *) apr_table_getm(apr_pool_t *p, const apr_table_t *t,
1277          const char *key)
1278  {
1279      table_getm_t state;
1280  
1281      state.p = p;
1282      state.first = NULL;
1283      state.merged = NULL;
1284  
1285      apr_table_do(table_getm_do, &state, t, key, NULL);
1286  
1287      if (!state.first) {
1288          return NULL;
1289      }
1290      else if (!state.merged) {
1291          return state.first;
1292      }
1293      else {
1294          return apr_array_pstrcat(p, state.merged, ',');
1295      }
1296  }
1297