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