contrib/apr-util/dbm/sdbm/sdbm_pair.c

   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  */
  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 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  */
 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 }