isam/physical.c

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