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