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