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