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