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