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