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