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