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