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