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