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