← Back to branch summary

~ubuntu-branches/ubuntu/edgy/libapache2-mod-perl2/edgy-updates

« back to all changes in this revision

Viewing changes to src/modules/perl/modperl_apache_compat.c

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2004-08-19 06:23:48 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20040819062348-jxl4koqbtvgm8v2t
Tags: 1.99.14-4
Remove the LFS CFLAGS, and build-dep against apache2-*-dev (>= 2.0.50-10)
as we're backing out of the apache2/apr ABI transition.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/modules/perl/modperl_apache_compat.c
 
1
/* Copyright 2003-2004 The Apache Software Foundation
 
2
 *
 
3
 * Licensed under the Apache License, Version 2.0 (the "License");
 
4
 * you may not use this file except in compliance with the License.
 
5
 * You may obtain a copy of the License at
 
6
 *
 
7
 *     http://www.apache.org/licenses/LICENSE-2.0
 
8
 *
 
9
 * Unless required by applicable law or agreed to in writing, software
 
10
 * distributed under the License is distributed on an "AS IS" BASIS,
 
11
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 
12
 * See the License for the specific language governing permissions and
 
13
 * limitations under the License.
 
14
 */
 
15
 
1
16
#include "mod_perl.h"
2
17
 
3
18
/* back compat adjustements for older Apache versions
10
25
   which is major mmn 20020903, minor mmn 4 */
11
26
#if ! AP_MODULE_MAGIC_AT_LEAST(20020903,4)
12
27
 
13
 
/* added in APACHE_2_0_47/APR_0_9_4 */
 
28
/* added in APACHE_2_0_47/APR_0_9_4 - duplicated here for 2.0.46.
 
29
 * I'd rather not duplicate it, but we use apr_table_compress
 
30
 * in the directive merge routines, so it's either duplicate it
 
31
 * here, recode the compress logic there, or drop 2.0.46 support
 
32
 */
 
33
 
 
34
#define TABLE_HASH_SIZE 32
 
35
 
 
36
struct apr_table_t {
 
37
    apr_array_header_t a;
 
38
#ifdef MAKE_TABLE_PROFILE
 
39
    /** Who created the array. */
 
40
    void *creator;
 
41
#endif
 
42
    apr_uint32_t index_initialized;
 
43
    int index_first[TABLE_HASH_SIZE];
 
44
    int index_last[TABLE_HASH_SIZE];
 
45
};
 
46
 
 
47
static apr_table_entry_t **table_mergesort(apr_pool_t *pool,
 
48
                                           apr_table_entry_t **values, int n)
 
49
{
 
50
    /* Bottom-up mergesort, based on design in Sedgewick's "Algorithms
 
51
     * in C," chapter 8
 
52
     */
 
53
    apr_table_entry_t **values_tmp =
 
54
        (apr_table_entry_t **)apr_palloc(pool, n * sizeof(apr_table_entry_t*));
 
55
    int i;
 
56
    int blocksize;
 
57
 
 
58
    /* First pass: sort pairs of elements (blocksize=1) */
 
59
    for (i = 0; i + 1 < n; i += 2) {
 
60
        if (strcasecmp(values[i]->key, values[i + 1]->key) > 0) {
 
61
            apr_table_entry_t *swap = values[i];
 
62
            values[i] = values[i + 1];
 
63
            values[i + 1] = swap;
 
64
        }
 
65
    }
 
66
 
 
67
    /* Merge successively larger blocks */
 
68
    blocksize = 2;
 
69
    while (blocksize < n) {
 
70
        apr_table_entry_t **dst = values_tmp;
 
71
        int next_start;
 
72
        apr_table_entry_t **swap;
 
73
 
 
74
        /* Merge consecutive pairs blocks of the next blocksize.
 
75
         * Within a block, elements are in sorted order due to
 
76
         * the previous iteration.
 
77
         */
 
78
        for (next_start = 0; next_start + blocksize < n;
 
79
             next_start += (blocksize + blocksize)) {
 
80
 
 
81
            int block1_start = next_start;
 
82
            int block2_start = block1_start + blocksize;
 
83
            int block1_end = block2_start;
 
84
            int block2_end = block2_start + blocksize;
 
85
            if (block2_end > n) {
 
86
                /* The last block may be smaller than blocksize */
 
87
                block2_end = n;
 
88
            }
 
89
            for (;;) {
 
90
 
 
91
                /* Merge the next two blocks:
 
92
                 * Pick the smaller of the next element from
 
93
                 * block 1 and the next element from block 2.
 
94
                 * Once either of the blocks is emptied, copy
 
95
                 * over all the remaining elements from the
 
96
                 * other block
 
97
                 */
 
98
                if (block1_start == block1_end) {
 
99
                    for (; block2_start < block2_end; block2_start++) {
 
100
                        *dst++ = values[block2_start];
 
101
                    }
 
102
                    break;
 
103
                }
 
104
                else if (block2_start == block2_end) {
 
105
                    for (; block1_start < block1_end; block1_start++) {
 
106
                        *dst++ = values[block1_start];
 
107
                    }
 
108
                    break;
 
109
                }
 
110
                if (strcasecmp(values[block1_start]->key,
 
111
                               values[block2_start]->key) > 0) {
 
112
                    *dst++ = values[block2_start++];
 
113
                }
 
114
                else {
 
115
                    *dst++ = values[block1_start++];
 
116
                }
 
117
            }
 
118
        }
 
119
 
 
120
        /* If n is not a multiple of 2*blocksize, some elements
 
121
         * will be left over at the end of the array.
 
122
         */
 
123
        for (i = dst - values_tmp; i < n; i++) {
 
124
            values_tmp[i] = values[i];
 
125
        }
 
126
 
 
127
        /* The output array of this pass becomes the input
 
128
         * array of the next pass, and vice versa
 
129
         */
 
130
        swap = values_tmp;
 
131
        values_tmp = values;
 
132
        values = swap;
 
133
 
 
134
        blocksize += blocksize;
 
135
    }
 
136
 
 
137
    return values;
 
138
}
14
139
void apr_table_compress(apr_table_t *t, unsigned flags)
15
140
{
16
 
    modperl_apr_func_not_implemented(apr_table_compress, 2.0.47, 0.9.4);
 
141
    apr_table_entry_t **sort_array;
 
142
    apr_table_entry_t **sort_next;
 
143
    apr_table_entry_t **sort_end;
 
144
    apr_table_entry_t *table_next;
 
145
    apr_table_entry_t **last;
 
146
    int i;
 
147
    int dups_found;
 
148
 
 
149
    if (t->a.nelts <= 1) {
 
150
        return;
 
151
    }
 
152
 
 
153
    /* Copy pointers to all the table elements into an
 
154
     * array and sort to allow for easy detection of
 
155
     * duplicate keys
 
156
     */
 
157
    sort_array = (apr_table_entry_t **)
 
158
        apr_palloc(t->a.pool, t->a.nelts * sizeof(apr_table_entry_t*));
 
159
    sort_next = sort_array;
 
160
    table_next = (apr_table_entry_t *)t->a.elts;
 
161
    i = t->a.nelts;
 
162
    do {
 
163
        *sort_next++ = table_next++;
 
164
    } while (--i);
 
165
 
 
166
    /* Note: the merge is done with mergesort instead of quicksort
 
167
     * because mergesort is a stable sort and runs in n*log(n)
 
168
     * time regardless of its inputs (quicksort is quadratic in
 
169
     * the worst case)
 
170
     */
 
171
    sort_array = table_mergesort(t->a.pool, sort_array, t->a.nelts);
 
172
 
 
173
    /* Process any duplicate keys */
 
174
    dups_found = 0;
 
175
    sort_next = sort_array;
 
176
    sort_end = sort_array + t->a.nelts;
 
177
    last = sort_next++;
 
178
    while (sort_next < sort_end) {
 
179
        if (((*sort_next)->key_checksum == (*last)->key_checksum) &&
 
180
            !strcasecmp((*sort_next)->key, (*last)->key)) {
 
181
            apr_table_entry_t **dup_last = sort_next + 1;
 
182
            dups_found = 1;
 
183
            while ((dup_last < sort_end) &&
 
184
                   ((*dup_last)->key_checksum == (*last)->key_checksum) &&
 
185
                   !strcasecmp((*dup_last)->key, (*last)->key)) {
 
186
                dup_last++;
 
187
            }
 
188
            dup_last--; /* Elements from last through dup_last, inclusive,
 
189
                         * all have the same key
 
190
                         */
 
191
            if (flags == APR_OVERLAP_TABLES_MERGE) {
 
192
                apr_size_t len = 0;
 
193
                apr_table_entry_t **next = last;
 
194
                char *new_val;
 
195
                char *val_dst;
 
196
                do {
 
197
                    len += strlen((*next)->val);
 
198
                    len += 2; /* for ", " or trailing null */
 
199
                } while (++next <= dup_last);
 
200
                new_val = (char *)apr_palloc(t->a.pool, len);
 
201
                val_dst = new_val;
 
202
                next = last;
 
203
                for (;;) {
 
204
                    strcpy(val_dst, (*next)->val);
 
205
                    val_dst += strlen((*next)->val);
 
206
                    next++;
 
207
                    if (next > dup_last) {
 
208
                        *val_dst = 0;
 
209
                        break;
 
210
                    }
 
211
                    else {
 
212
                        *val_dst++ = ',';
 
213
                        *val_dst++ = ' ';
 
214
                    }
 
215
                }
 
216
                (*last)->val = new_val;
 
217
            }
 
218
            else { /* overwrite */
 
219
                (*last)->val = (*dup_last)->val;
 
220
            }
 
221
            do {
 
222
                (*sort_next)->key = NULL;
 
223
            } while (++sort_next <= dup_last);
 
224
        }
 
225
        else {
 
226
            last = sort_next++;
 
227
        }
 
228
    }
 
229
 
 
230
    /* Shift elements to the left to fill holes left by removing duplicates */
 
231
    if (dups_found) {
 
232
        apr_table_entry_t *src = (apr_table_entry_t *)t->a.elts;
 
233
        apr_table_entry_t *dst = (apr_table_entry_t *)t->a.elts;
 
234
        apr_table_entry_t *last_elt = src + t->a.nelts;
 
235
        do {
 
236
            if (src->key) {
 
237
                *dst++ = *src;
 
238
            }
 
239
        } while (++src < last_elt);
 
240
        t->a.nelts -= (last_elt - dst);
 
241
    }
 
242
 
 
243
    /* XXX mod_perl: remove to avoid more code duplication.
 
244
     * XXX makes us slower on 2.0.46
 
245
     */
 
246
    /* table_reindex(t); */
17
247
}
18
248
 
19
249
#endif /* pre-APR_0_9_5 (APACHE_2_0_47) */