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