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