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