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