← Back to branch summary

~ubuntu-branches/ubuntu/feisty/apache2/feisty

« back to all changes in this revision

Viewing changes to srclib/apr-util/dbm/sdbm/sdbm_pair.c

  • Committer: Bazaar Package Importer
  • Author(s): Andreas Barth
  • Date: 2006-12-09 21:05:45 UTC
  • mfrom: (0.6.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20061209210545-h70s0xaqc2v8vqr2
Tags: 2.2.3-3.2
http://bugs.debian.org/396265
* Non-maintainer upload.
* 043_ajp_connection_reuse: Patch from upstream Bugzilla, fixing a critical
  issue with regard to connection reuse in mod_proxy_ajp.
  Closes: #396265

Show diffs side-by-side

added added

removed removed

Lines of Context:
srclib/apr-util/dbm/sdbm/sdbm_pair.c
 
1
/* Copyright 2000-2005 The Apache Software Foundation or its licensors, as
 
2
 * applicable.
 
3
 *
 
4
 * Licensed under the Apache License, Version 2.0 (the "License");
 
5
 * you may not use this file except in compliance with the License.
 
6
 * 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
 * sdbm - ndbm work-alike hashed database library
 
19
 * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
 
20
 * author: oz@nexus.yorku.ca
 
21
 * status: ex-public domain.
 
22
 *
 
23
 * page-level routines
 
24
 */
 
25
 
 
26
#include "apr_sdbm.h"
 
27
 
 
28
#include "sdbm_tune.h"
 
29
#include "sdbm_pair.h"
 
30
#include "sdbm_private.h"
 
31
 
 
32
#include <string.h>     /* for memset() */
 
33
 
 
34
 
 
35
#define exhash(item)    sdbm_hash((item).dptr, (item).dsize)
 
36
 
 
37
/* 
 
38
 * forward 
 
39
 */
 
40
static int seepair(char *, int, char *, int);
 
41
 
 
42
/*
 
43
 * page format:
 
44
 *      +------------------------------+
 
45
 * ino  | n | keyoff | datoff | keyoff |
 
46
 *      +------------+--------+--------+
 
47
 *      | datoff | - - - ---->         |
 
48
 *      +--------+---------------------+
 
49
 *      |        F R E E A R E A       |
 
50
 *      +--------------+---------------+
 
51
 *      |  <---- - - - | data          |
 
52
 *      +--------+-----+----+----------+
 
53
 *      |  key   | data     | key      |
 
54
 *      +--------+----------+----------+
 
55
 *
 
56
 * calculating the offsets for free area:  if the number
 
57
 * of entries (ino[0]) is zero, the offset to the END of
 
58
 * the free area is the block size. Otherwise, it is the
 
59
 * nth (ino[ino[0]]) entry's offset.
 
60
 */
 
61
 
 
62
int
 
63
fitpair(pag, need)
 
64
char *pag;
 
65
int need;
 
66
{
 
67
        register int n;
 
68
        register int off;
 
69
        register int avail;
 
70
        register short *ino = (short *) pag;
 
71
 
 
72
        off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
 
73
        avail = off - (n + 1) * sizeof(short);
 
74
        need += 2 * sizeof(short);
 
75
 
 
76
        debug(("avail %d need %d\n", avail, need));
 
77
 
 
78
        return need <= avail;
 
79
}
 
80
 
 
81
void
 
82
putpair(pag, key, val)
 
83
char *pag;
 
84
apr_sdbm_datum_t key;
 
85
apr_sdbm_datum_t val;
 
86
{
 
87
        register int n;
 
88
        register int off;
 
89
        register short *ino = (short *) pag;
 
90
 
 
91
        off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
 
92
/*
 
93
 * enter the key first
 
94
 */
 
95
        off -= key.dsize;
 
96
        (void) memcpy(pag + off, key.dptr, key.dsize);
 
97
        ino[n + 1] = off;
 
98
/*
 
99
 * now the data
 
100
 */
 
101
        off -= val.dsize;
 
102
        (void) memcpy(pag + off, val.dptr, val.dsize);
 
103
        ino[n + 2] = off;
 
104
/*
 
105
 * adjust item count
 
106
 */
 
107
        ino[0] += 2;
 
108
}
 
109
 
 
110
apr_sdbm_datum_t
 
111
getpair(pag, key)
 
112
char *pag;
 
113
apr_sdbm_datum_t key;
 
114
{
 
115
        register int i;
 
116
        register int n;
 
117
        apr_sdbm_datum_t val;
 
118
        register short *ino = (short *) pag;
 
119
 
 
120
        if ((n = ino[0]) == 0)
 
121
                return sdbm_nullitem;
 
122
 
 
123
        if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
 
124
                return sdbm_nullitem;
 
125
 
 
126
        val.dptr = pag + ino[i + 1];
 
127
        val.dsize = ino[i] - ino[i + 1];
 
128
        return val;
 
129
}
 
130
 
 
131
int
 
132
duppair(pag, key)
 
133
char *pag;
 
134
apr_sdbm_datum_t key;
 
135
{
 
136
        register short *ino = (short *) pag;
 
137
        return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
 
138
}
 
139
 
 
140
apr_sdbm_datum_t
 
141
getnkey(pag, num)
 
142
char *pag;
 
143
int num;
 
144
{
 
145
        apr_sdbm_datum_t key;
 
146
        register int off;
 
147
        register short *ino = (short *) pag;
 
148
 
 
149
        num = num * 2 - 1;
 
150
        if (ino[0] == 0 || num > ino[0])
 
151
                return sdbm_nullitem;
 
152
 
 
153
        off = (num > 1) ? ino[num - 1] : PBLKSIZ;
 
154
 
 
155
        key.dptr = pag + ino[num];
 
156
        key.dsize = off - ino[num];
 
157
 
 
158
        return key;
 
159
}
 
160
 
 
161
int
 
162
delpair(pag, key)
 
163
char *pag;
 
164
apr_sdbm_datum_t key;
 
165
{
 
166
        register int n;
 
167
        register int i;
 
168
        register short *ino = (short *) pag;
 
169
 
 
170
        if ((n = ino[0]) == 0)
 
171
                return 0;
 
172
 
 
173
        if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
 
174
                return 0;
 
175
/*
 
176
 * found the key. if it is the last entry
 
177
 * [i.e. i == n - 1] we just adjust the entry count.
 
178
 * hard case: move all data down onto the deleted pair,
 
179
 * shift offsets onto deleted offsets, and adjust them.
 
180
 * [note: 0 < i < n]
 
181
 */
 
182
        if (i < n - 1) {
 
183
                register int m;
 
184
                register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
 
185
                register char *src = pag + ino[i + 1];
 
186
                register int   zoo = dst - src;
 
187
 
 
188
                debug(("free-up %d ", zoo));
 
189
/*
 
190
 * shift data/keys down
 
191
 */
 
192
                m = ino[i + 1] - ino[n];
 
193
 
 
194
#undef DUFF     /* just use memmove. it should be plenty fast. */
 
195
#ifdef DUFF
 
196
#define MOVB    *--dst = *--src
 
197
 
 
198
                if (m > 0) {
 
199
                        register int loop = (m + 8 - 1) >> 3;
 
200
 
 
201
                        switch (m & (8 - 1)) {
 
202
                        case 0: do {
 
203
                                MOVB;   case 7: MOVB;
 
204
                        case 6: MOVB;   case 5: MOVB;
 
205
                        case 4: MOVB;   case 3: MOVB;
 
206
                        case 2: MOVB;   case 1: MOVB;
 
207
                                } while (--loop);
 
208
                        }
 
209
                }
 
210
#else
 
211
                dst -= m;
 
212
                src -= m;
 
213
                memmove(dst, src, m);
 
214
#endif
 
215
 
 
216
/*
 
217
 * adjust offset index up
 
218
 */
 
219
                while (i < n - 1) {
 
220
                        ino[i] = ino[i + 2] + zoo;
 
221
                        i++;
 
222
                }
 
223
        }
 
224
        ino[0] -= 2;
 
225
        return 1;
 
226
}
 
227
 
 
228
/*
 
229
 * search for the key in the page.
 
230
 * return offset index in the range 0 < i < n.
 
231
 * return 0 if not found.
 
232
 */
 
233
static int
 
234
seepair(pag, n, key, siz)
 
235
char *pag;
 
236
register int n;
 
237
register char *key;
 
238
register int siz;
 
239
{
 
240
        register int i;
 
241
        register int off = PBLKSIZ;
 
242
        register short *ino = (short *) pag;
 
243
 
 
244
        for (i = 1; i < n; i += 2) {
 
245
                if (siz == off - ino[i] &&
 
246
                    memcmp(key, pag + ino[i], siz) == 0)
 
247
                        return i;
 
248
                off = ino[i + 1];
 
249
        }
 
250
        return 0;
 
251
}
 
252
 
 
253
void
 
254
splpage(pag, new, sbit)
 
255
char *pag;
 
256
char *new;
 
257
long sbit;
 
258
{
 
259
        apr_sdbm_datum_t key;
 
260
        apr_sdbm_datum_t val;
 
261
 
 
262
        register int n;
 
263
        register int off = PBLKSIZ;
 
264
        char cur[PBLKSIZ];
 
265
        register short *ino = (short *) cur;
 
266
 
 
267
        (void) memcpy(cur, pag, PBLKSIZ);
 
268
        (void) memset(pag, 0, PBLKSIZ);
 
269
        (void) memset(new, 0, PBLKSIZ);
 
270
 
 
271
        n = ino[0];
 
272
        for (ino++; n > 0; ino += 2) {
 
273
                key.dptr = cur + ino[0]; 
 
274
                key.dsize = off - ino[0];
 
275
                val.dptr = cur + ino[1];
 
276
                val.dsize = ino[0] - ino[1];
 
277
/*
 
278
 * select the page pointer (by looking at sbit) and insert
 
279
 */
 
280
                (void) putpair((exhash(key) & sbit) ? new : pag, key, val);
 
281
 
 
282
                off = ino[1];
 
283
                n -= 2;
 
284
        }
 
285
 
 
286
        debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, 
 
287
               ((short *) new)[0] / 2,
 
288
               ((short *) pag)[0] / 2));
 
289
}
 
290
 
 
291
/*
 
292
 * check page sanity: 
 
293
 * number of entries should be something
 
294
 * reasonable, and all offsets in the index should be in order.
 
295
 * this could be made more rigorous.
 
296
 */
 
297
int
 
298
chkpage(pag)
 
299
char *pag;
 
300
{
 
301
        register int n;
 
302
        register int off;
 
303
        register short *ino = (short *) pag;
 
304
 
 
305
        if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short))
 
306
                return 0;
 
307
 
 
308
        if (n > 0) {
 
309
                off = PBLKSIZ;
 
310
                for (ino++; n > 0; ino += 2) {
 
311
                        if (ino[0] > off || ino[1] > off ||
 
312
                            ino[1] > ino[0])
 
313
                                return 0;
 
314
                        off = ino[1];
 
315
                        n -= 2;
 
316
                }
 
317
        }
 
318
        return 1;
 
319
}