isam/isam.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: isam.c,v $
   7  * Revision 1.7  1994-09-28 11:56:25  quinn
   8  * Added sort of input to is_merge
   9  *
  10  * Revision 1.6  1994/09/28  11:29:33  quinn
  11  * Added cmp parameter.
  12  *
  13  * Revision 1.5  1994/09/27  20:03:50  quinn
  14  * Seems relatively bug-free.
  15  *
  16  * Revision 1.4  1994/09/26  17:11:29  quinn
  17  * Trivial
  18  *
  19  * Revision 1.3  1994/09/26  17:06:35  quinn
  20  * Back again...
  21  *
  22  * Revision 1.1  1994/09/12  08:02:13  quinn
  23  * Not functional yet
  24  *
  25  */
  26
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include <ctype.h>
  30
  31 #include <util.h>
  32 #include <bfile.h>
  33 #include <isam.h>
  34 #include <common.h>
  35 #include "isutil.h"
  36 #include "rootblk.h"
  37 #include "keyops.h"
  38
  39 static int (*extcmp)(const void *p1, const void *p2);
  40
  41 static int splitargs(const char *s, char *bf[], int max)
  42 {
  43     int ct = 0;
  44     for (;;)
  45     {
  46         while (*s && isspace(*s))
  47             s++;
  48         bf[ct] = (char *) s;
  49         if (!*s)
  50                 return ct;
  51         ct++;
  52         if (ct > max)
  53         {
  54             log(LOG_WARN, "Ignoring extra args to is resource");
  55             bf[ct] = '\0';
  56             return(ct - 1);
  57         }
  58         while (*s && !isspace(*s))
  59             s++;
  60     }
  61 }
  62
  63 /*
  64  * Open isam file.
  65  * Process resources.
  66  */
  67 ISAM is_open(const char *name, int (*cmp)(const void *p1, const void *p2),
  68     int writeflag)
  69 {
  70     ISAM new;
  71     char *nm, *r, *pp[IS_MAX_BLOCKTYPES+1], m[2];
  72     int num, size, rs, tmp, i;
  73     is_type_header th;
  74
  75     log(LOG_DEBUG, "is_open(%s, %s)", name, writeflag ? "RW" : "RDONLY");
  76     new = xmalloc(sizeof(*new));
  77     new->writeflag = writeflag;
  78     for (i = 0; i < IS_MAX_BLOCKTYPES; i++)
  79         new->types[i].index = 0;                        /* dummy */
  80
  81     /* determine number and size of blocktypes */
  82     if (!(r = res_get(common_resource, nm = strconcat(name, ".",
  83         "blocktypes", 0))) || !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES)))
  84     {
  85         log(LOG_FATAL, "Failed to locate resource %s", nm);
  86         return 0;
  87     }
  88     new->num_types = num;
  89     for (i = 0; i < num; i++)
  90     {
  91         if ((rs = sscanf(pp[i], "%d%1[bBkKmM]", &size, m)) < 1)
  92         {
  93             log(LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
  94             return 0;
  95         }
  96         if (rs == 1)
  97                 *m = 'b';
  98         switch (*m)
  99         {
 100                 case 'b': case 'B':
 101                     new->types[i].blocksize = size; break;
 102                 case 'k': case 'K':
 103                     new->types[i].blocksize = size * 1024; break;
 104                 case 'm': case 'M':
 105                     new->types[i].blocksize = size * 1048576; break;
 106                 default:
 107                     log(LOG_FATAL, "Illegal size suffix: %c", *m);
 108                     return 0;
 109         }
 110         new->types[i].dbuf = xmalloc(new->types[i].blocksize);
 111         m[0] = 'A' + i;
 112         m[1] = '\0';
 113         if (!(new->types[i].bf = bf_open(strconcat(name, m, 0),
 114             new->types[i].blocksize, writeflag)))
 115         {
 116             log(LOG_FATAL, "bf_open failed");
 117             return 0;
 118         }
 119         if ((rs = is_rb_read(&new->types[i], &th)) > 0)
 120         {
 121             if (th.blocksize != new->types[i].blocksize)
 122             {
 123                 log(LOG_FATAL, "File blocksize mismatch in %s", name);
 124                 exit(1);
 125             }
 126             new->types[i].freelist = th.freelist;
 127             new->types[i].top = th.top;
 128         }
 129         else if (writeflag) /* write dummy superblock to determine top */
 130         {
 131             if ((rs = is_rb_write(&new->types[i], &th)) <=0)  /* dummy */
 132             {
 133                 log(LOG_FATAL, "Failed to write initial superblock.");
 134                 exit(1);
 135             }
 136             new->types[i].freelist = -1;
 137             new->types[i].top = rs;
 138         }
 139         /* ELSE: this is an empty file opened in read-only mode. */
 140     }
 141     if (!(r = res_get_def(common_resource, nm = strconcat(name, ".", "keysize",
 142         0), "4")))
 143     {
 144         log(LOG_FATAL, "Failed to locate resource %s", nm);
 145         return 0;
 146     }
 147     if ((new->keysize = atoi(r)) <= 0)
 148     {
 149         log(LOG_FATAL, "Must specify positive keysize.");
 150         return 0;
 151     }
 152
 153     /* determine repack percent */
 154     if (!(r = res_get_def(common_resource, nm = strconcat(name, ".", "repack",
 155         0), IS_DEF_REPACK_PERCENT)))
 156     {
 157         log(LOG_FATAL, "Failed to locate resource %s", nm);
 158         return 0;
 159     }
 160     new->repack = atoi(r);
 161
 162     /* determine max keys/blocksize */
 163     if (!(r = res_get(common_resource, nm = strconcat(name, ".",
 164         "maxkeys", 0))) || !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES)))
 165     {
 166         log(LOG_FATAL, "Failed to locate resource %s", nm);
 167         return 0;
 168     }
 169     if (num < new->num_types -1)
 170     {
 171         log(LOG_FATAL, "Not enough elements in %s", nm);
 172         return 0;
 173     }
 174     for (i = 0; i < num; i++)
 175     {
 176         if ((rs = sscanf(pp[i], "%d", &tmp)) < 1)
 177         {
 178             log(LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
 179             return 0;
 180         }
 181         new->types[i].max_keys = tmp;
 182     }
 183
 184     /* determine max keys/block */
 185     for (i = 0; i < new->num_types; i++)
 186     {
 187         if (!new->types[i].index)
 188         {
 189             new->types[i].max_keys_block = (new->types[i].blocksize - 2 *
 190                 sizeof(int)) / new->keysize;
 191             new->types[i].max_keys_block0 = (new->types[i].blocksize - 3 *
 192                 sizeof(int)) / new->keysize;
 193         }
 194         else
 195             new->types[i].max_keys_block = new->types[i].max_keys_block0 /
 196                 new->keysize;
 197         if (new->types[i].max_keys_block0 < 1)
 198         {
 199             log(LOG_FATAL, "Blocksize too small in %s", name);
 200             exit(1);
 201         }
 202     }
 203
 204     /* determine nice fill rates */
 205     if (!(r = res_get(common_resource, nm = strconcat(name, ".",
 206         "nicefill", 0))) || !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES)))
 207     {
 208         log(LOG_FATAL, "Failed to locate resource %s", nm);
 209         return 0;
 210     }
 211     if (num < new->num_types)
 212     {
 213         log(LOG_FATAL, "Not enough elements in %s", nm);
 214         return 0;
 215     }
 216     for (i = 0; i < num; i++)
 217     {
 218         if ((rs = sscanf(pp[i], "%d", &tmp)) < 1)
 219         {
 220             log(LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
 221             return 0;
 222         }
 223         new->types[i].nice_keys_block = (new->types[i].max_keys_block0 * tmp) /
 224             100;
 225         if (new->types[i].nice_keys_block < 1)
 226                 new->types[i].nice_keys_block = 1;
 227     }
 228
 229     new->cmp = cmp ? cmp : is_default_cmp;
 230     return new;
 231 }
 232
 233 /*
 234  * Close isam file.
 235  */
 236 int is_close(ISAM is)
 237 {
 238     int i;
 239     is_type_header th;
 240
 241     log(LOG_DEBUG, "is_close()");
 242     for (i = 0; i < is->num_types; i++)
 243     {
 244         if (is->types[i].bf)
 245         {
 246             if (is->writeflag)
 247             {
 248                 th.blocksize = is->types[i].blocksize;
 249                 th.keysize = is->keysize;
 250                 th.freelist = is->types[i].freelist;
 251                 th.top = is->types[i].top;
 252                 if (is_rb_write(&is->types[i], &th) < 0)
 253                 {
 254                     log(LOG_FATAL, "Failed to write headerblock");
 255                     exit(1);
 256                 }
 257             }
 258             bf_close(is->types[i].bf);
 259         }
 260     }
 261     xfree(is);
 262     return 0;
 263 }
 264
 265 static ISAM_P is_address(int type, int pos)
 266 {
 267     ISAM_P r;
 268
 269     r = pos << 2;
 270     r |= type;
 271     return r;
 272 }
 273
 274 int sort_input(const void *p1, const void *p2)
 275 {
 276     int rs;
 277
 278     if ((rs = (*extcmp)(((char *)p1) + 1, ((char *)p2) + 1)))
 279         return rs;
 280     return *((char *)p1) - *((char*)p2);
 281 }
 282
 283 ISAM_P is_merge(ISAM is, ISAM_P pos, int num, char *data)
 284 {
 285     is_mtable tab;
 286     int res;
 287     char keybuf[IS_MAX_RECORD];
 288     int oldnum, oldtype, i;
 289     char operation, *record;
 290
 291     extcmp = is->cmp;
 292     qsort(data, num, is_keysize(is) + 1, sort_input);
 293     is_m_establish_tab(is, &tab, pos);
 294     /* TODO: do something to aquire oldnum at this point */
 295     if (pos)
 296         if (is_m_read_full(&tab, tab.data) < 0)
 297         {
 298             log(LOG_FATAL, "read_full failed");
 299             exit(1);
 300         }
 301     oldnum = tab.num_records;
 302     oldtype = tab.pos_type;
 303     while (num)
 304     {
 305         operation = *(data)++;
 306         record = (char*) data;
 307         data += is_keysize(is);
 308         num--;
 309         while (num && !memcmp(record - 1, data, is_keysize(tab.is) + 1))
 310         {
 311             data += 1 + is_keysize(is);
 312             num--;
 313         }
 314         if ((res = is_m_seek_record(&tab, record)) > 0)  /* no match */
 315         {
 316             if (operation == KEYOP_INSERT)
 317             {
 318                 log(LOG_DEBUG, "XXInserting new record.");
 319                 is_m_write_record(&tab, record);
 320             }
 321             else
 322                 log(LOG_DEBUG, "XXDeletion failed to find match.");
 323         }
 324         else /* match found */
 325         {
 326             if (operation == KEYOP_INSERT)
 327             {
 328                 log(LOG_DEBUG, "XXSkipping insertion - match found.");
 329                 continue;
 330             }
 331             else if (operation == KEYOP_DELETE)
 332             {
 333                 /* try to avoid needlessly moving data */
 334                 if (num && *(data) == KEYOP_INSERT)
 335                 {
 336                     /* next key is identical insert? - NOOP - skip it */
 337                     if (!memcmp(record, data + 1, is_keysize(is)))
 338                     {
 339                         log(LOG_DEBUG, "XXNoop delete. skipping.");
 340                         data += 1 + is_keysize(is);
 341                         num--;
 342                         continue;
 343                     }
 344                     /* else check if next key can fit in this position */
 345                     is_m_peek_record(&tab, keybuf);
 346                     res = (*is->cmp)(data + 1, keybuf);
 347                     if (res < 0)
 348                     {
 349                         log(LOG_DEBUG, "XXReplacing record.");
 350                         is_m_replace_record(&tab, data + 1);
 351                         data += 1 + is_keysize(is);
 352                         num--;
 353                         continue;
 354                     }
 355                 }
 356                 log(LOG_DEBUG, "Deleting record.");
 357                 is_m_delete_record(&tab);
 358             }
 359         }
 360     }
 361     i = tab.pos_type;
 362     while (i < tab.is->num_types - 1 && tab.num_records >
 363         tab.is->types[i].max_keys)
 364         i++;
 365     if (i != tab.pos_type)
 366     {
 367         is_p_unmap(&tab);
 368         tab.pos_type = i;
 369     }
 370     if (!oldnum || tab.pos_type != oldtype || (abs(oldnum - tab.num_records) *
 371         100) / oldnum > tab.is->repack)
 372         is_p_remap(&tab);
 373     else
 374         is_p_align(&tab);
 375     if (tab.data)
 376     {
 377         is_p_sync(&tab);
 378         pos = is_address(tab.pos_type, tab.data->diskpos);
 379     }
 380     else
 381         pos = 0;
 382     is_m_release_tab(&tab);
 383     return pos;
 384 }
 385
 386 /*
 387  * Locate a table of keys in an isam file. The ISPT is an individual
 388  * position marker for that table.
 389  */
 390 ISPT is_position(ISAM is, ISAM_P pos);
 391
 392 /*
 393  * Release ISPT.
 394  */
 395 void is_pt_free(ISPT ip);