isam/physical.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: physical.c,v $
   7  * Revision 1.12  1996-03-20 16:17:11  quinn
   8  * Bug hunting
   9  *
  10  * Revision 1.11  1996/03/20  13:29:17  quinn
  11  * Bug-fix
  12  *
  13  * Revision 1.10  1996/03/19  19:22:44  quinn
  14  * Fixed update-bug
  15  *
  16  * Revision 1.9  1996/02/06  10:19:57  quinn
  17  * Attempt at fixing bug. Not all blocks were read before they were unlinked
  18  * prior to a remap operation.
  19  *
  20  * Revision 1.8  1996/01/29  09:47:11  quinn
  21  * Fixed mean little bug in the read-table code.
  22  *
  23  * Revision 1.7  1995/12/06  14:48:27  quinn
  24  * Fixed some strange bugs.
  25  *
  26  * Revision 1.6  1995/09/04  12:33:47  adam
  27  * Various cleanup. YAZ util used instead.
  28  *
  29  * Revision 1.5  1994/09/28  11:29:33  quinn
  30  * Added cmp parameter.
  31  *
  32  * Revision 1.4  1994/09/27  20:03:53  quinn
  33  * Seems relatively bug-free.
  34  *
  35  * Revision 1.3  1994/09/26  17:11:31  quinn
  36  * Trivial
  37  *
  38  * Revision 1.2  1994/09/26  17:06:36  quinn
  39  * Back again...
  40  *
  41  * Revision 1.1  1994/09/26  16:07:57  quinn
  42  * Most of the functionality in place.
  43  *
  44  */
  45
  46 /*
  47  * This module handles the representation of tables in the bfiles.
  48  */
  49
  50 #include <assert.h>
  51 #include <stdio.h>
  52
  53 #include <isam.h>
  54
  55 static int is_freestore_alloc(ISAM is, int type)
  56 {
  57     int tmp;
  58
  59     if (is->types[type].freelist >= 0)
  60     {
  61         tmp = is->types[type].freelist;
  62         if (bf_read(is->types[type].bf, tmp, 0, sizeof(tmp),
  63             &is->types[type].freelist) <=0)
  64         {
  65             logf (LOG_FATAL, "Failed to allocate block");
  66             exit(1);
  67         }
  68     }
  69     else
  70         tmp = is->types[type].top++;
  71
  72     logf (LOG_DEBUG, "Allocating block #%d", tmp);
  73     return tmp;
  74 }
  75
  76 static void is_freestore_free(ISAM is, int type, int block)
  77 {
  78     int tmp;
  79
  80     logf (LOG_DEBUG, "Releasing block #%d", block);
  81     tmp = is->types[type].freelist;
  82     is->types[type].freelist = block;
  83     if (bf_write(is->types[type].bf, block, 0, sizeof(tmp), &tmp) < 0)
  84     {
  85         logf (LOG_FATAL, "Failed to deallocate block.");
  86         exit(1);
  87     }
  88 }
  89
  90 /* this code must be modified to handle an index */
  91 int is_p_read_partial(is_mtable *tab, is_mblock *block)
  92 {
  93     int toread;
  94     is_mbuf *buf;
  95
  96     assert(block->state == IS_MBSTATE_UNREAD);
  97     block->data = buf = xmalloc_mbuf(IS_MBUF_TYPE_LARGE);
  98     toread = tab->is->types[tab->pos_type].blocksize;
  99     if (toread > is_mbuf_size[buf->type])
 100     {
 101         toread = is_mbuf_size[buf->type];
 102         block->state = IS_MBSTATE_PARTIAL;
 103     }
 104     else
 105         block->state = IS_MBSTATE_CLEAN;
 106     if (bf_read(tab->is->types[tab->pos_type].bf, block->diskpos, 0, toread,
 107         buf->data) < 0)
 108     {
 109         logf (LOG_FATAL, "bfread failed.");
 110         return -1;
 111     }
 112     /* extract header info */
 113     buf->offset = 0;
 114     memcpy(&block->num_records, buf->data, sizeof(block->num_records));
 115     assert(block->num_records > 0);
 116     buf->offset += sizeof(block->num_records);
 117     memcpy(&block->nextpos, buf->data + buf->offset,
 118         sizeof(block->nextpos));
 119     buf->offset += sizeof(block->nextpos);
 120     if (block == tab->data) /* first block */
 121     {
 122         memcpy(&tab->num_records, buf->data + buf->offset,
 123             sizeof(tab->num_records));
 124         buf->offset +=sizeof(tab->num_records);
 125     }
 126     logf(LOG_DEBUG, "R: Block #%d: num %d nextpos %d total %d",
 127         block->diskpos, block->num_records, block->nextpos,
 128         block == tab->data ? tab->num_records : -1);
 129     buf->num = (toread - buf->offset) / is_keysize(tab->is);
 130     if (buf->num >= block->num_records)
 131     {
 132         buf->num = block->num_records;
 133         block->state = IS_MBSTATE_CLEAN;
 134     }
 135     else
 136         block->bread = buf->offset + buf->num * is_keysize(tab->is);
 137     return 0;
 138 }
 139
 140 int is_p_read_full(is_mtable *tab, is_mblock *block)
 141 {
 142     is_mbuf *buf;
 143     int dread, toread;
 144
 145     if (block->state == IS_MBSTATE_UNREAD && is_p_read_partial(tab, block) < 0)
 146     {
 147         logf (LOG_FATAL, "partial read failed.");
 148         return -1;
 149     }
 150     if (block->state == IS_MBSTATE_PARTIAL)
 151     {
 152         buf = block->data;
 153         dread = block->data->num;
 154         while (dread < block->num_records)
 155         {
 156             buf->next = xmalloc_mbuf(IS_MBUF_TYPE_LARGE);
 157             buf = buf->next;
 158
 159             toread = is_mbuf_size[buf->type] / is_keysize(tab->is);
 160             if (toread > block->num_records - dread)
 161                 toread = block->num_records - dread;
 162
 163             if (bf_read(tab->is->types[tab->pos_type].bf, block->diskpos, block->bread, toread *
 164                 is_keysize(tab->is), buf->data) < 0)
 165             {
 166                 logf (LOG_FATAL, "bfread failed.");
 167                 return -1;
 168             }
 169             buf->offset = 0;
 170             buf->num = toread;
 171             dread += toread;
 172             block->bread += toread * is_keysize(tab->is);
 173         }
 174         block->state = IS_MBSTATE_CLEAN;
 175     }
 176     logf (LOG_DEBUG, "R: Block #%d contains %d records.", block->diskpos, block->num_records);
 177     return 0;
 178 }
 179
 180 /*
 181  * write dirty blocks to bfile.
 182  * Allocate blocks as necessary.
 183  */
 184 void is_p_sync(is_mtable *tab)
 185 {
 186     is_mblock *p;
 187     is_mbuf *b;
 188     int sum, v;
 189     isam_blocktype *type;
 190
 191     type = &tab->is->types[tab->pos_type];
 192     for (p = tab->data; p; p = p->next)
 193     {
 194         if (p->state < IS_MBSTATE_DIRTY)
 195             continue;
 196         /* make sure that blocks are allocated. */
 197         if (p->diskpos < 0)
 198             p->diskpos = is_freestore_alloc(tab->is, tab->pos_type);
 199         if (p->next)
 200         {
 201             if (p->next->diskpos < 0)
 202                 p->nextpos = p->next->diskpos = is_freestore_alloc(tab->is,
 203                     tab->pos_type);
 204             else
 205                 p->nextpos = p->next->diskpos;
 206         }
 207         else
 208             p->nextpos = 0;
 209         sum = 0;
 210         memcpy(type->dbuf, &p->num_records, sizeof(p->num_records));
 211         sum += sizeof(p->num_records);
 212         memcpy(type->dbuf + sum, &p->nextpos, sizeof(p->nextpos));
 213         sum += sizeof(p->nextpos);
 214         if (p == tab->data)  /* first block */
 215         {
 216             memcpy(type->dbuf + sum, &tab->num_records,
 217                 sizeof(tab->num_records));
 218             sum += sizeof(tab->num_records);
 219         }
 220         logf (LOG_DEBUG, "W: Block #%d contains %d records.", p->diskpos,
 221             p->num_records);
 222         assert(p->num_records > 0);
 223         for (b = p->data; b; b = b->next)
 224         {
 225             logf(LOG_DEBUG, "   buf: offset %d, keys %d, type %d, ref %d",
 226                 b->offset, b->num, b->type, b->refcount);
 227             if ((v = b->num * is_keysize(tab->is)) > 0)
 228                 memcpy(type->dbuf + sum, b->data + b->offset, v);
 229
 230             sum += v;
 231             assert(sum <= type->blocksize);
 232         }
 233         if (bf_write(type->bf, p->diskpos, 0, sum, type->dbuf) < 0)
 234         {
 235             logf (LOG_FATAL, "Failed to write block.");
 236             exit(1);
 237         }
 238     }
 239 }
 240
 241 /*
 242  * Free all disk blocks associated with table.
 243  */
 244 void is_p_unmap(is_mtable *tab)
 245 {
 246     is_mblock *p;
 247
 248     for (p = tab->data; p; p = p->next)
 249     {
 250         if (p->diskpos >= 0)
 251         {
 252             is_freestore_free(tab->is, tab->pos_type, p->diskpos);
 253             p->diskpos = -1;
 254         }
 255     }
 256 }
 257
 258 static is_mbuf *mbuf_takehead(is_mbuf **mb, int *num, int keysize)
 259 {
 260     is_mbuf *p = 0, **pp = &p, *new;
 261     int toget = *num;
 262
 263     if (!toget)
 264         return 0;
 265     while (*mb && toget >= (*mb)->num)
 266     {
 267         toget -= (*mb)->num;
 268         *pp = *mb;
 269         *mb = (*mb)->next;
 270         (*pp)->next = 0;
 271         pp = &(*pp)->next;
 272     }
 273     if (toget > 0 && *mb)
 274     {
 275         new = xmalloc_mbuf(IS_MBUF_TYPE_SMALL);
 276         new->next = (*mb)->next;
 277         (*mb)->next = new;
 278         new->data = (*mb)->data;
 279         (*mb)->refcount++;
 280         new->offset = (*mb)->offset + toget * keysize;
 281         new->num = (*mb)->num - toget;
 282         (*mb)->num = toget;
 283         *pp = *mb;
 284         *mb = (*mb)->next;
 285         (*pp)->next = 0;
 286         toget = 0;
 287     }
 288     *num -= toget;
 289     return p;
 290 }
 291
 292 /*
 293  * Split up individual blocks which have grown too large.
 294  * is_p_align and is_p_remap are alternative functions which trade off
 295  * speed in updating versus optimum usage of disk blocks.
 296  */
 297 void is_p_align(is_mtable *tab)
 298 {
 299     is_mblock *mblock, *new, *last = 0, *next;
 300     is_mbuf *mbufs, *mbp;
 301     int blocks, recsblock;
 302
 303     logf (LOG_DEBUG, "Realigning table.");
 304     for (mblock = tab->data; mblock; mblock = next)
 305     {
 306         next = mblock->next;
 307         if (mblock->state == IS_MBSTATE_DIRTY && mblock->num_records == 0)
 308         {
 309             if (last)
 310             {
 311                 last->next = mblock->next;
 312                 last->state = IS_MBSTATE_DIRTY;
 313                 next = mblock->next;
 314             }
 315             else
 316             {
 317                 next = tab->data->next;
 318                 if (next)
 319                 {
 320                     if (next->state < IS_MBSTATE_CLEAN)
 321                     {
 322                         if (is_p_read_full(tab, next) < 0)
 323                         {
 324                             logf(LOG_FATAL, "Error during re-alignment");
 325                             abort();
 326                         }
 327                         if (next->nextpos && !next->next)
 328                         {
 329                             next->next = xmalloc_mblock();
 330                             next->next->diskpos = next->nextpos;
 331                             next->next->state = IS_MBSTATE_UNREAD;
 332                             next->next->data = 0;
 333                         }
 334                     }
 335                     next->state = IS_MBSTATE_DIRTY; /* force re-process */
 336                     tab->data = next;
 337                 }
 338             }
 339             if (mblock->diskpos >= 0)
 340                 is_freestore_free(tab->is, tab->pos_type, mblock->diskpos);
 341             xrelease_mblock(mblock);
 342         }
 343         else if (mblock->state == IS_MBSTATE_DIRTY && mblock->num_records >
 344             (mblock == tab->data ?
 345             tab->is->types[tab->pos_type].max_keys_block0 :
 346             tab->is->types[tab->pos_type].max_keys_block))
 347         {
 348             blocks = tab->num_records /
 349             tab->is->types[tab->pos_type].nice_keys_block;
 350             if (tab->num_records %
 351                 tab->is->types[tab->pos_type].nice_keys_block)
 352                 blocks++;
 353             recsblock = tab->num_records / blocks;
 354             if (recsblock < 1)
 355                 recsblock = 1;
 356             mbufs = mblock->data;
 357             while ((mbp = mbuf_takehead(&mbufs, &recsblock,
 358                 is_keysize(tab->is))) && recsblock)
 359             {
 360                 if (mbufs)
 361                 {
 362                     new = xmalloc_mblock();
 363                     new->diskpos = -1;
 364                     new->state = IS_MBSTATE_DIRTY;
 365                     new->next = mblock->next;
 366                     mblock->next = new;
 367                 }
 368                 mblock->data = mbp;
 369                 mblock->num_records = recsblock;
 370                 last = mblock;
 371                 mblock = mblock->next;
 372             }
 373             next = mblock;
 374         }
 375         else
 376             last = mblock;
 377     }
 378 }
 379
 380 /*
 381  * Reorganize data in blocks for minimum block usage and quick access.
 382  * Free surplus blocks.
 383  * is_p_align and is_p_remap are alternative functions which trade off
 384  * speed in updating versus optimum usage of disk blocks.
 385  */
 386 void is_p_remap(is_mtable *tab)
 387 {
 388     is_mbuf *mbufs, **bufpp, *mbp;
 389     is_mblock *blockp, **blockpp;
 390     int recsblock, blocks;
 391
 392     logf (LOG_DEBUG, "Remapping table.");
 393     /* collect all data */
 394     bufpp = &mbufs;
 395     for (blockp = tab->data; blockp; blockp = blockp->next)
 396     {
 397         if (blockp->state < IS_MBSTATE_CLEAN && is_m_read_full(tab, blockp) < 0)
 398         {
 399             logf (LOG_FATAL, "Read-full failed in remap.");
 400             exit(1);
 401         }
 402         *bufpp = blockp->data;
 403         while (*bufpp)
 404             bufpp = &(*bufpp)->next;
 405         blockp->data = 0;
 406     }
 407     blocks = tab->num_records / tab->is->types[tab->pos_type].nice_keys_block;
 408     if (tab->num_records % tab->is->types[tab->pos_type].nice_keys_block)
 409         blocks++;
 410     if (blocks == 0)
 411         blocks = 1;
 412     recsblock = tab->num_records / blocks + 1;
 413     if (recsblock > tab->is->types[tab->pos_type].nice_keys_block)
 414         recsblock--;
 415     blockpp = &tab->data;
 416     while ((mbp = mbuf_takehead(&mbufs, &recsblock, is_keysize(tab->is))) &&
 417         recsblock)
 418     {
 419         if (!*blockpp)
 420         {
 421             *blockpp = xmalloc_mblock();
 422             (*blockpp)->diskpos = -1;
 423         }
 424         (*blockpp)->data = mbp;
 425         (*blockpp)->num_records = recsblock;
 426         (*blockpp)->state = IS_MBSTATE_DIRTY;
 427         blockpp = &(*blockpp)->next;
 428     }
 429     if (mbp)
 430         xfree_mbufs(mbp);
 431     if (*blockpp)
 432     {
 433         for (blockp = *blockpp; blockp; blockp = blockp->next)
 434             if (blockp->diskpos >= 0)
 435                 is_freestore_free(tab->is, tab->pos_type, blockp->diskpos);
 436         xfree_mblocks(*blockpp);
 437         *blockpp = 0;
 438     }
 439 }