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