#include "apr_private.h"
#include "apr_general.h"
#include "apr_pools.h"
#include "apr_tables.h"
#include "apr_strings.h"
#include "apr_lib.h"
#if APR_HAVE_STDLIB_H
#include <stdlib.h>
#endif
#if APR_HAVE_STRING_H
#include <string.h>
#endif
#if APR_HAVE_STRINGS_H
#include <strings.h>
#endif
#if (APR_POOL_DEBUG || defined(MAKE_TABLE_PROFILE)) && APR_HAVE_STDIO_H
#include <stdio.h>
#endif
static void make_array_core(apr_array_header_t *res, apr_pool_t *p,
int nelts, int elt_size, int clear)
{
if (nelts < 1) {
nelts = 1;
}
if (clear) {
res->elts = apr_pcalloc(p, nelts * elt_size);
}
else {
res->elts = apr_palloc(p, nelts * elt_size);
}
res->pool = p;
res->elt_size = elt_size;
res->nelts = 0;
res->nalloc = nelts;
}
APR_DECLARE(int) apr_is_empty_array(const apr_array_header_t *a)
{
return ((a == NULL) || (a->nelts == 0));
}
APR_DECLARE(apr_array_header_t *) apr_array_make(apr_pool_t *p,
int nelts, int elt_size)
{
apr_array_header_t *res;
res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
make_array_core(res, p, nelts, elt_size, 1);
return res;
}
APR_DECLARE(void) apr_array_clear(apr_array_header_t *arr)
{
arr->nelts = 0;
}
APR_DECLARE(void *) apr_array_pop(apr_array_header_t *arr)
{
if (apr_is_empty_array(arr)) {
return NULL;
}
return arr->elts + (arr->elt_size * (--arr->nelts));
}
APR_DECLARE(void *) apr_array_push(apr_array_header_t *arr)
{
if (arr->nelts == arr->nalloc) {
int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
char *new_data;
new_data = apr_palloc(arr->pool, arr->elt_size * new_size);
memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size);
memset(new_data + arr->nalloc * arr->elt_size, 0,
arr->elt_size * (new_size - arr->nalloc));
arr->elts = new_data;
arr->nalloc = new_size;
}
++arr->nelts;
return arr->elts + (arr->elt_size * (arr->nelts - 1));
}
static void *apr_array_push_noclear(apr_array_header_t *arr)
{
if (arr->nelts == arr->nalloc) {
int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
char *new_data;
new_data = apr_palloc(arr->pool, 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));
}
APR_DECLARE(void) apr_array_cat(apr_array_header_t *dst,
const apr_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 = apr_pcalloc(dst->pool, 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;
}
APR_DECLARE(apr_array_header_t *) apr_array_copy(apr_pool_t *p,
const apr_array_header_t *arr)
{
apr_array_header_t *res =
(apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
make_array_core(res, p, arr->nalloc, arr->elt_size, 0);
memcpy(res->elts, arr->elts, arr->elt_size * arr->nelts);
res->nelts = arr->nelts;
memset(res->elts + res->elt_size * res->nelts, 0,
res->elt_size * (res->nalloc - res->nelts));
return res;
}
static APR_INLINE void copy_array_hdr_core(apr_array_header_t *res,
const apr_array_header_t *arr)
{
res->elts = arr->elts;
res->elt_size = arr->elt_size;
res->nelts = arr->nelts;
res->nalloc = arr->nelts;
}
APR_DECLARE(apr_array_header_t *)
apr_array_copy_hdr(apr_pool_t *p,
const apr_array_header_t *arr)
{
apr_array_header_t *res;
res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
res->pool = p;
copy_array_hdr_core(res, arr);
return res;
}
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)
{
apr_array_header_t *res = apr_array_copy_hdr(p, first);
apr_array_cat(res, second);
return res;
}
APR_DECLARE(char *) apr_array_pstrcat(apr_pool_t *p,
const apr_array_header_t *arr,
const char sep)
{
char *cp, *res, **strpp;
apr_size_t len;
int i;
if (arr->nelts <= 0 || arr->elts == NULL) {
return (char *) apr_pcalloc(p, 1);
}
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;
}
}
res = (char *) apr_palloc(p, len + 1);
cp = res;
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 res;
}
#if APR_CHARSET_EBCDIC
#define CASE_MASK 0xbfbfbfbf
#else
#define CASE_MASK 0xdfdfdfdf
#endif
#define TABLE_HASH_SIZE 32
#define TABLE_INDEX_MASK 0x1f
#define TABLE_HASH(key) (TABLE_INDEX_MASK & *(unsigned char *)(key))
#define TABLE_INDEX_IS_INITIALIZED(t, i) ((t)->index_initialized & (1 << (i)))
#define TABLE_SET_INDEX_INITIALIZED(t, i) ((t)->index_initialized |= (1 << (i)))
#define COMPUTE_KEY_CHECKSUM(key, checksum) \
{ \
const char *k = (key); \
apr_uint32_t c = (apr_uint32_t)*k; \
(checksum) = c; \
(checksum) <<= 8; \
if (c) { \
c = (apr_uint32_t)*++k; \
checksum |= c; \
} \
(checksum) <<= 8; \
if (c) { \
c = (apr_uint32_t)*++k; \
checksum |= c; \
} \
(checksum) <<= 8; \
if (c) { \
c = (apr_uint32_t)*++k; \
checksum |= c; \
} \
checksum &= CASE_MASK; \
}
struct apr_table_t {
apr_array_header_t a;
#ifdef MAKE_TABLE_PROFILE
void *creator;
#endif
apr_uint32_t index_initialized;
int index_first[TABLE_HASH_SIZE];
int index_last[TABLE_HASH_SIZE];
};
#ifdef MAKE_TABLE_PROFILE
static apr_table_entry_t *do_table_push(const char *func, apr_table_t *t)
{
if (t->a.nelts == t->a.nalloc) {
fprintf(stderr, "%s: table created by %p hit limit of %u\n",
func ? func : "table_push", t->creator, t->a.nalloc);
}
return (apr_table_entry_t *) apr_array_push_noclear(&t->a);
}
#if defined(__GNUC__) && __GNUC__ >= 2
#define table_push(t) do_table_push(__FUNCTION__, t)
#else
#define table_push(t) do_table_push(NULL, t)
#endif
#else
#define table_push(t) ((apr_table_entry_t *) apr_array_push_noclear(&(t)->a))
#endif
APR_DECLARE(const apr_array_header_t *) apr_table_elts(const apr_table_t *t)
{
return (const apr_array_header_t *)t;
}
APR_DECLARE(int) apr_is_empty_table(const apr_table_t *t)
{
return ((t == NULL) || (t->a.nelts == 0));
}
APR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts)
{
apr_table_t *t = apr_palloc(p, sizeof(apr_table_t));
make_array_core(&t->a, p, nelts, sizeof(apr_table_entry_t), 0);
#ifdef MAKE_TABLE_PROFILE
t->creator = __builtin_return_address(0);
#endif
t->index_initialized = 0;
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));
#if APR_POOL_DEBUG
if (!apr_pool_is_ancestor(t->a.pool, p)) {
fprintf(stderr, "apr_table_copy: 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), 0);
memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t));
new->a.nelts = t->a.nelts;
memcpy(new->index_first, t->index_first, sizeof(int) * TABLE_HASH_SIZE);
memcpy(new->index_last, t->index_last, sizeof(int) * TABLE_HASH_SIZE);
new->index_initialized = t->index_initialized;
return new;
}
APR_DECLARE(apr_table_t *) apr_table_clone(apr_pool_t *p, const apr_table_t *t)
{
const apr_array_header_t *array = apr_table_elts(t);
apr_table_entry_t *elts = (apr_table_entry_t *) array->elts;
apr_table_t *new = apr_table_make(p, array->nelts);
int i;
for (i = 0; i < array->nelts; i++) {
apr_table_add(new, elts[i].key, elts[i].val);
}
return new;
}
static void table_reindex(apr_table_t *t)
{
int i;
int hash;
apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
t->index_initialized = 0;
for (i = 0; i < t->a.nelts; i++, next_elt++) {
hash = TABLE_HASH(next_elt->key);
t->index_last[hash] = i;
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
t->index_first[hash] = i;
TABLE_SET_INDEX_INITIALIZED(t, hash);
}
}
}
APR_DECLARE(void) apr_table_clear(apr_table_t *t)
{
t->a.nelts = 0;
t->index_initialized = 0;
}
APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)
{
apr_table_entry_t *next_elt;
apr_table_entry_t *end_elt;
apr_uint32_t checksum;
int hash;
if (key == NULL) {
return NULL;
}
hash = TABLE_HASH(key);
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
return NULL;
}
COMPUTE_KEY_CHECKSUM(key, checksum);
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
for (; next_elt <= end_elt; next_elt++) {
if ((checksum == next_elt->key_checksum) &&
!strcasecmp(next_elt->key, key)) {
return next_elt->val;
}
}
return NULL;
}
APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,
const char *val)
{
apr_table_entry_t *next_elt;
apr_table_entry_t *end_elt;
apr_table_entry_t *table_end;
apr_uint32_t checksum;
int hash;
COMPUTE_KEY_CHECKSUM(key, checksum);
hash = TABLE_HASH(key);
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
t->index_first[hash] = t->a.nelts;
TABLE_SET_INDEX_INITIALIZED(t, hash);
goto add_new_elt;
}
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts;
for (; next_elt <= end_elt; next_elt++) {
if ((checksum == next_elt->key_checksum) &&
!strcasecmp(next_elt->key, key)) {
int must_reindex = 0;
apr_table_entry_t *dst_elt = NULL;
next_elt->val = apr_pstrdup(t->a.pool, val);
for (next_elt++; next_elt <= end_elt; next_elt++) {
if ((checksum == next_elt->key_checksum) &&
!strcasecmp(next_elt->key, key)) {
t->a.nelts--;
if (!dst_elt) {
dst_elt = next_elt;
}
}
else if (dst_elt) {
*dst_elt++ = *next_elt;
must_reindex = 1;
}
}
if (dst_elt) {
for (; next_elt < table_end; next_elt++) {
*dst_elt++ = *next_elt;
}
must_reindex = 1;
}
if (must_reindex) {
table_reindex(t);
}
return;
}
}
add_new_elt:
t->index_last[hash] = t->a.nelts;
next_elt = (apr_table_entry_t *) table_push(t);
next_elt->key = apr_pstrdup(t->a.pool, key);
next_elt->val = apr_pstrdup(t->a.pool, val);
next_elt->key_checksum = checksum;
}
APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key,
const char *val)
{
apr_table_entry_t *next_elt;
apr_table_entry_t *end_elt;
apr_table_entry_t *table_end;
apr_uint32_t checksum;
int hash;
COMPUTE_KEY_CHECKSUM(key, checksum);
hash = TABLE_HASH(key);
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
t->index_first[hash] = t->a.nelts;
TABLE_SET_INDEX_INITIALIZED(t, hash);
goto add_new_elt;
}
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts;
for (; next_elt <= end_elt; next_elt++) {
if ((checksum == next_elt->key_checksum) &&
!strcasecmp(next_elt->key, key)) {
int must_reindex = 0;
apr_table_entry_t *dst_elt = NULL;
next_elt->val = (char *)val;
for (next_elt++; next_elt <= end_elt; next_elt++) {
if ((checksum == next_elt->key_checksum) &&
!strcasecmp(next_elt->key, key)) {
t->a.nelts--;
if (!dst_elt) {
dst_elt = next_elt;
}
}
else if (dst_elt) {
*dst_elt++ = *next_elt;
must_reindex = 1;
}
}
if (dst_elt) {
for (; next_elt < table_end; next_elt++) {
*dst_elt++ = *next_elt;
}
must_reindex = 1;
}
if (must_reindex) {
table_reindex(t);
}
return;
}
}
add_new_elt:
t->index_last[hash] = t->a.nelts;
next_elt = (apr_table_entry_t *) table_push(t);
next_elt->key = (char *)key;
next_elt->val = (char *)val;
next_elt->key_checksum = checksum;
}
APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key)
{
apr_table_entry_t *next_elt;
apr_table_entry_t *end_elt;
apr_table_entry_t *dst_elt;
apr_uint32_t checksum;
int hash;
int must_reindex;
hash = TABLE_HASH(key);
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
return;
}
COMPUTE_KEY_CHECKSUM(key, checksum);
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
must_reindex = 0;
for (; next_elt <= end_elt; next_elt++) {
if ((checksum == next_elt->key_checksum) &&
!strcasecmp(next_elt->key, key)) {
apr_table_entry_t *table_end = ((apr_table_entry_t *) t->a.elts) +
t->a.nelts;
t->a.nelts--;
dst_elt = next_elt;
for (next_elt++; next_elt <= end_elt; next_elt++) {
if ((checksum == next_elt->key_checksum) &&
!strcasecmp(next_elt->key, key)) {
t->a.nelts--;
}
else {
*dst_elt++ = *next_elt;
}
}
for (; next_elt < table_end; next_elt++) {
*dst_elt++ = *next_elt;
}
must_reindex = 1;
break;
}
}
if (must_reindex) {
table_reindex(t);
}
}
APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key,
const char *val)
{
apr_table_entry_t *next_elt;
apr_table_entry_t *end_elt;
apr_uint32_t checksum;
int hash;
COMPUTE_KEY_CHECKSUM(key, checksum);
hash = TABLE_HASH(key);
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
t->index_first[hash] = t->a.nelts;
TABLE_SET_INDEX_INITIALIZED(t, hash);
goto add_new_elt;
}
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
for (; next_elt <= end_elt; next_elt++) {
if ((checksum == next_elt->key_checksum) &&
!strcasecmp(next_elt->key, key)) {
next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
val, NULL);
return;
}
}
add_new_elt:
t->index_last[hash] = t->a.nelts;
next_elt = (apr_table_entry_t *) table_push(t);
next_elt->key = apr_pstrdup(t->a.pool, key);
next_elt->val = apr_pstrdup(t->a.pool, val);
next_elt->key_checksum = checksum;
}
APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key,
const char *val)
{
apr_table_entry_t *next_elt;
apr_table_entry_t *end_elt;
apr_uint32_t checksum;
int hash;
#if APR_POOL_DEBUG
{
apr_pool_t *pool;
pool = apr_pool_find(key);
if ((pool != key) && (!apr_pool_is_ancestor(pool, t->a.pool))) {
fprintf(stderr, "apr_table_mergen: key not in ancestor pool of t\n");
abort();
}
pool = apr_pool_find(val);
if ((pool != val) && (!apr_pool_is_ancestor(pool, t->a.pool))) {
fprintf(stderr, "apr_table_mergen: val not in ancestor pool of t\n");
abort();
}
}
#endif
COMPUTE_KEY_CHECKSUM(key, checksum);
hash = TABLE_HASH(key);
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
t->index_first[hash] = t->a.nelts;
TABLE_SET_INDEX_INITIALIZED(t, hash);
goto add_new_elt;
}
next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
for (; next_elt <= end_elt; next_elt++) {
if ((checksum == next_elt->key_checksum) &&
!strcasecmp(next_elt->key, key)) {
next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
val, NULL);
return;
}
}
add_new_elt:
t->index_last[hash] = t->a.nelts;
next_elt = (apr_table_entry_t *) table_push(t);
next_elt->key = (char *)key;
next_elt->val = (char *)val;
next_elt->key_checksum = checksum;
}
APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key,
const char *val)
{
apr_table_entry_t *elts;
apr_uint32_t checksum;
int hash;
hash = TABLE_HASH(key);
t->index_last[hash] = t->a.nelts;
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
t->index_first[hash] = t->a.nelts;
TABLE_SET_INDEX_INITIALIZED(t, hash);
}
COMPUTE_KEY_CHECKSUM(key, checksum);
elts = (apr_table_entry_t *) table_push(t);
elts->key = apr_pstrdup(t->a.pool, key);
elts->val = apr_pstrdup(t->a.pool, val);
elts->key_checksum = checksum;
}
APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key,
const char *val)
{
apr_table_entry_t *elts;
apr_uint32_t checksum;
int hash;
#if APR_POOL_DEBUG
{
if (!apr_pool_is_ancestor(apr_pool_find(key), t->a.pool)) {
fprintf(stderr, "apr_table_addn: key not in ancestor pool of t\n");
abort();
}
if (!apr_pool_is_ancestor(apr_pool_find(val), t->a.pool)) {
fprintf(stderr, "apr_table_addn: val not in ancestor pool of t\n");
abort();
}
}
#endif
hash = TABLE_HASH(key);
t->index_last[hash] = t->a.nelts;
if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
t->index_first[hash] = t->a.nelts;
TABLE_SET_INDEX_INITIALIZED(t, hash);
}
COMPUTE_KEY_CHECKSUM(key, checksum);
elts = (apr_table_entry_t *) table_push(t);
elts->key = (char *)key;
elts->val = (char *)val;
elts->key_checksum = checksum;
}
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;
#if APR_POOL_DEBUG
if (!apr_pool_is_ancestor(overlay->a.pool, p)) {
fprintf(stderr,
"apr_table_overlay: overlay's pool is not an ancestor of p\n");
abort();
}
if (!apr_pool_is_ancestor(base->a.pool, p)) {
fprintf(stderr,
"apr_table_overlay: base's pool is not an ancestor of p\n");
abort();
}
#endif
res = apr_palloc(p, sizeof(apr_table_t));
res->a.pool = p;
copy_array_hdr_core(&res->a, &overlay->a);
apr_array_cat(&res->a, &base->a);
table_reindex(res);
return res;
}
APR_DECLARE_NONSTD(int) apr_table_do(apr_table_do_callback_fn_t *comp,
void *rec, const apr_table_t *t, ...)
{
int rv;
va_list vp;
va_start(vp, t);
rv = apr_table_vdo(comp, rec, t, vp);
va_end(vp);
return rv;
}
APR_DECLARE(int) apr_table_vdo(apr_table_do_callback_fn_t *comp,
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 vdorv = 1;
argp = va_arg(vp, char *);
do {
int rv = 1, i;
if (argp) {
int hash = TABLE_HASH(argp);
if (TABLE_INDEX_IS_INITIALIZED(t, hash)) {
apr_uint32_t checksum;
COMPUTE_KEY_CHECKSUM(argp, checksum);
for (i = t->index_first[hash];
rv && (i <= t->index_last[hash]); ++i) {
if (elts[i].key && (checksum == elts[i].key_checksum) &&
!strcasecmp(elts[i].key, argp)) {
rv = (*comp) (rec, elts[i].key, elts[i].val);
}
}
}
}
else {
for (i = 0; rv && (i < t->a.nelts); ++i) {
if (elts[i].key) {
rv = (*comp) (rec, elts[i].key, elts[i].val);
}
}
}
if (rv == 0) {
vdorv = 0;
}
} while (argp && ((argp = va_arg(vp, char *)) != NULL));
return vdorv;
}
static apr_table_entry_t **table_mergesort(apr_pool_t *pool,
apr_table_entry_t **values,
apr_size_t n)
{
apr_table_entry_t **values_tmp =
(apr_table_entry_t **)apr_palloc(pool, n * sizeof(apr_table_entry_t*));
apr_size_t i;
apr_size_t blocksize;
for (i = 0; i + 1 < n; i += 2) {
if (strcasecmp(values[i]->key, values[i + 1]->key) > 0) {
apr_table_entry_t *swap = values[i];
values[i] = values[i + 1];
values[i + 1] = swap;
}
}
blocksize = 2;
while (blocksize < n) {
apr_table_entry_t **dst = values_tmp;
apr_size_t next_start;
apr_table_entry_t **swap;
for (next_start = 0; next_start + blocksize < n;
next_start += (blocksize + blocksize)) {
apr_size_t block1_start = next_start;
apr_size_t block2_start = block1_start + blocksize;
apr_size_t block1_end = block2_start;
apr_size_t block2_end = block2_start + blocksize;
if (block2_end > n) {
block2_end = n;
}
for (;;) {
if (block1_start == block1_end) {
for (; block2_start < block2_end; block2_start++) {
*dst++ = values[block2_start];
}
break;
}
else if (block2_start == block2_end) {
for (; block1_start < block1_end; block1_start++) {
*dst++ = values[block1_start];
}
break;
}
if (strcasecmp(values[block1_start]->key,
values[block2_start]->key) > 0) {
*dst++ = values[block2_start++];
}
else {
*dst++ = values[block1_start++];
}
}
}
for (i = dst - values_tmp; i < n; i++) {
values_tmp[i] = values[i];
}
swap = values_tmp;
values_tmp = values;
values = swap;
blocksize += blocksize;
}
return values;
}
APR_DECLARE(void) apr_table_compress(apr_table_t *t, unsigned flags)
{
apr_table_entry_t **sort_array;
apr_table_entry_t **sort_next;
apr_table_entry_t **sort_end;
apr_table_entry_t *table_next;
apr_table_entry_t **last;
int i;
int dups_found;
if (t->a.nelts <= 1) {
return;
}
sort_array = (apr_table_entry_t **)
apr_palloc(t->a.pool, t->a.nelts * sizeof(apr_table_entry_t*));
sort_next = sort_array;
table_next = (apr_table_entry_t *)t->a.elts;
i = t->a.nelts;
do {
*sort_next++ = table_next++;
} while (--i);
sort_array = table_mergesort(t->a.pool, sort_array, t->a.nelts);
dups_found = 0;
sort_next = sort_array;
sort_end = sort_array + t->a.nelts;
last = sort_next++;
while (sort_next < sort_end) {
if (((*sort_next)->key_checksum == (*last)->key_checksum) &&
!strcasecmp((*sort_next)->key, (*last)->key)) {
apr_table_entry_t **dup_last = sort_next + 1;
dups_found = 1;
while ((dup_last < sort_end) &&
((*dup_last)->key_checksum == (*last)->key_checksum) &&
!strcasecmp((*dup_last)->key, (*last)->key)) {
dup_last++;
}
dup_last--;
if (flags == APR_OVERLAP_TABLES_MERGE) {
apr_size_t len = 0;
apr_table_entry_t **next = last;
char *new_val;
char *val_dst;
do {
len += strlen((*next)->val);
len += 2;
} while (++next <= dup_last);
new_val = (char *)apr_palloc(t->a.pool, len);
val_dst = new_val;
next = last;
for (;;) {
strcpy(val_dst, (*next)->val);
val_dst += strlen((*next)->val);
next++;
if (next > dup_last) {
*val_dst = 0;
break;
}
else {
*val_dst++ = ',';
*val_dst++ = ' ';
}
}
(*last)->val = new_val;
}
else {
(*last)->val = (*dup_last)->val;
}
do {
(*sort_next)->key = NULL;
} while (++sort_next <= dup_last);
}
else {
last = sort_next++;
}
}
if (dups_found) {
apr_table_entry_t *src = (apr_table_entry_t *)t->a.elts;
apr_table_entry_t *dst = (apr_table_entry_t *)t->a.elts;
apr_table_entry_t *last_elt = src + t->a.nelts;
do {
if (src->key) {
*dst++ = *src;
}
} while (++src < last_elt);
t->a.nelts -= (int)(last_elt - dst);
}
table_reindex(t);
}
static void apr_table_cat(apr_table_t *t, const apr_table_t *s)
{
const int n = t->a.nelts;
register int idx;
apr_array_cat(&t->a,&s->a);
if (n == 0) {
memcpy(t->index_first,s->index_first,sizeof(int) * TABLE_HASH_SIZE);
memcpy(t->index_last, s->index_last, sizeof(int) * TABLE_HASH_SIZE);
t->index_initialized = s->index_initialized;
return;
}
for (idx = 0; idx < TABLE_HASH_SIZE; ++idx) {
if (TABLE_INDEX_IS_INITIALIZED(s, idx)) {
t->index_last[idx] = s->index_last[idx] + n;
if (!TABLE_INDEX_IS_INITIALIZED(t, idx)) {
t->index_first[idx] = s->index_first[idx] + n;
}
}
}
t->index_initialized |= s->index_initialized;
}
APR_DECLARE(void) apr_table_overlap(apr_table_t *a, const apr_table_t *b,
unsigned flags)
{
if (a->a.nelts + b->a.nelts == 0) {
return;
}
#if APR_POOL_DEBUG
if (!apr_pool_is_ancestor(b->a.pool, a->a.pool)) {
fprintf(stderr, "apr_table_overlap: b's pool is not an ancestor of a's\n");
abort();
}
#endif
apr_table_cat(a, b);
apr_table_compress(a, flags);
}