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 * 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 */ 40static 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 62int 63fitpair(pag, need) 64char *pag; 65int 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 81void 82putpair(pag, key, val) 83char *pag; 84apr_sdbm_datum_t key; 85apr_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 110apr_sdbm_datum_t 111getpair(pag, key) 112char *pag; 113apr_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 131int 132duppair(pag, key) 133char *pag; 134apr_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 140apr_sdbm_datum_t 141getnkey(pag, num) 142char *pag; 143int 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 161int 162delpair(pag, key) 163char *pag; 164apr_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 short zoo = (short) (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 */ 233static int 234seepair(pag, n, key, siz) 235char *pag; 236register int n; 237register char *key; 238register 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 253void 254splpage(pag, new, sbit) 255char *pag; 256char *new; 257long 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 */ 297int 298chkpage(pag) 299char *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] < 0 || ino[0] > off || 312 ino[1] < 0 || ino[1] > off || 313 ino[1] > ino[0]) 314 return 0; 315 off = ino[1]; 316 n -= 2; 317 } 318 } 319 return 1; 320} 321