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