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