isam/memory.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: memory.c,v $
   7  * Revision 1.15  1997-09-09 13:38:11  adam
   8  * Partial port to WIN95/NT.
   9  *
  10  * Revision 1.14  1996/10/29 13:56:56  adam
  11  * Include of zebrautl.h instead of alexutil.h.
  12  *
  13  * Revision 1.13  1996/03/20 13:29:16  quinn
  14  * Bug-fix
  15  *
  16  * Revision 1.12  1996/03/11  14:52:23  quinn
  17  * Fixed update bug. Repeated insertion in the same area sometimes caused
  18  * problems.
  19  *
  20  * Revision 1.11  1996/02/10  12:20:58  quinn
  21  * *** empty log message ***
  22  *
  23  * Revision 1.10  1995/12/12  14:12:47  quinn
  24  * *** empty log message ***
  25  *
  26  * Revision 1.9  1995/12/06  15:48:46  quinn
  27  * Fixed update-problem.
  28  *
  29  * Revision 1.8  1995/12/06  14:48:27  quinn
  30  * Fixed some strange bugs.
  31  *
  32  * Revision 1.7  1995/12/06  09:59:46  quinn
  33  * Fixed memory-consumption bug in memory.c
  34  * Added more blocksizes to the default ISAM configuration.
  35  *
  36  * Revision 1.6  1995/09/04  12:33:47  adam
  37  * Various cleanup. YAZ util used instead.
  38  *
  39  * Revision 1.5  1994/09/28  16:58:33  quinn
  40  * Small mod.
  41  *
  42  * Revision 1.4  1994/09/27  20:03:52  quinn
  43  * Seems relatively bug-free.
  44  *
  45  * Revision 1.3  1994/09/26  17:11:30  quinn
  46  * Trivial
  47  *
  48  * Revision 1.2  1994/09/26  17:06:35  quinn
  49  * Back again...
  50  *
  51  * Revision 1.1  1994/09/26  16:07:56  quinn
  52  * Most of the functionality in place.
  53  *
  54  */
  55
  56 /*
  57  * This module accesses and rearranges the records of the tables.
  58  */
  59
  60 #include <assert.h>
  61 #include <stdio.h>
  62 #include <stdlib.h>
  63 #include <string.h>
  64
  65 #include <zebrautl.h>
  66 #include <isam.h>
  67
  68 int is_mbuf_size[3] = { 0, 1024, 4096 };
  69
  70 static is_mblock *mblock_tmplist = 0, *mblock_freelist = 0;
  71 static is_mbuf *mbuf_freelist[3] = {0, 0, 0};
  72
  73 #define MALLOC_CHUNK 20
  74
  75 is_mblock *xmalloc_mblock()
  76 {
  77     is_mblock *tmp;
  78     int i;
  79
  80     if (!mblock_freelist)
  81     {
  82         mblock_freelist = xmalloc(sizeof(is_mblock) * MALLOC_CHUNK);
  83         for (i = 0; i < MALLOC_CHUNK - 1; i++)
  84             mblock_freelist[i].next = &mblock_freelist[i+1];
  85         mblock_freelist[i].next = 0;
  86     }
  87     tmp = mblock_freelist;
  88     mblock_freelist = mblock_freelist->next;
  89     tmp->next = 0;
  90     tmp->state = IS_MBSTATE_UNREAD;
  91     tmp->data = 0;
  92     return tmp;
  93 }
  94
  95 is_mbuf *xmalloc_mbuf(int type)
  96 {
  97     is_mbuf *tmp;
  98
  99     if (mbuf_freelist[type])
 100     {
 101         tmp = mbuf_freelist[type];
 102         mbuf_freelist[type] = tmp->next;
 103     }
 104     else
 105     {
 106         tmp = xmalloc(sizeof(is_mbuf) + is_mbuf_size[type]);
 107         tmp->type = type;
 108     }
 109     tmp->refcount = type ? 1 : 0;
 110     tmp->offset = tmp->num = tmp->cur_record = 0;
 111     tmp->data = (char*) tmp + sizeof(is_mbuf);
 112     tmp->next = 0;
 113     return tmp;
 114 }
 115
 116 void xfree_mbuf(is_mbuf *p)
 117 {
 118     p->next = mbuf_freelist[p->type];
 119     mbuf_freelist[p->type] = p;
 120 }
 121
 122 void xfree_mbufs(is_mbuf *l)
 123 {
 124     is_mbuf *p;
 125
 126     while (l)
 127     {
 128         p = l->next;
 129         xfree_mbuf(l);
 130         l = p;
 131     }
 132 }
 133
 134 void xfree_mblock(is_mblock *p)
 135 {
 136     xfree_mbufs(p->data);
 137     p->next = mblock_freelist;
 138     mblock_freelist = p;
 139 }
 140
 141 void xrelease_mblock(is_mblock *p)
 142 {
 143     p->next = mblock_tmplist;
 144     mblock_tmplist = p;
 145 }
 146
 147 void xfree_mblocks(is_mblock *l)
 148 {
 149     is_mblock *p;
 150
 151     while (l)
 152     {
 153         p = l->next;
 154         xfree_mblock(l);
 155         l = p;
 156     }
 157 }
 158
 159 void is_m_establish_tab(ISAM is, is_mtable *tab, ISAM_P pos)
 160 {
 161     tab->data = xmalloc_mblock();
 162     if (pos > 0)
 163     {
 164         tab->pos_type = is_type(pos);
 165         tab->num_records = -1;
 166         tab->data->num_records = -1;
 167         tab->data->diskpos = is_block(pos);
 168         tab->data->state = IS_MBSTATE_UNREAD;
 169         tab->data->data = 0;
 170         tab->cur_mblock = tab->data;
 171         tab->cur_mblock->cur_mbuf = 0;
 172         tab->last_mbuf = 0;
 173     }
 174     else /* new block */
 175     {
 176         tab->pos_type = 0;
 177         tab->num_records = 0;
 178         tab->data->num_records = 0;
 179         tab->data->diskpos = -1;
 180         tab->data->state = IS_MBSTATE_CLEAN;
 181         tab->data->data = xmalloc_mbuf(IS_MBUF_TYPE_LARGE);
 182         tab->cur_mblock = tab->data;
 183         tab->cur_mblock->cur_mbuf = tab->data->data;
 184         tab->cur_mblock->cur_mbuf->cur_record = 0;
 185         tab->last_mbuf = 0;
 186     }
 187     tab->is = is;
 188 }
 189
 190 void is_m_release_tab(is_mtable *tab)
 191 {
 192     xfree_mblocks(tab->data);
 193     xfree_mblocks(mblock_tmplist);
 194     mblock_tmplist = 0;
 195 }
 196
 197 void is_m_rewind(is_mtable *tab)
 198 {
 199     tab->cur_mblock = tab->data;
 200     if (tab->data)
 201     {
 202         tab->data->cur_mbuf = tab->data->data;
 203         if (tab->data->data)
 204             tab->data->data->cur_record = 0;
 205     }
 206 }
 207
 208 static int read_current_full(is_mtable *tab, is_mblock *mblock)
 209 {
 210     if (is_p_read_full(tab, mblock) < 0)
 211         return -1;
 212     if (mblock->nextpos && !mblock->next)
 213     {
 214         mblock->next = xmalloc_mblock();
 215         mblock->next->diskpos = mblock->nextpos;
 216         mblock->next->state = IS_MBSTATE_UNREAD;
 217         mblock->next->data = 0;
 218     }
 219     mblock->cur_mbuf = mblock->data;
 220     mblock->data->cur_record = 0;
 221     return 0;
 222 }
 223
 224 int is_m_read_full(is_mtable *tab, is_mblock *mblock)
 225 {
 226     return read_current_full(tab, mblock);
 227 }
 228
 229 /*
 230  * replace the record right behind the pointer.
 231  */
 232 void is_m_replace_record(is_mtable *tab, const void *rec)
 233 {
 234     is_mbuf *mbuf = tab->cur_mblock->cur_mbuf;
 235
 236     /* we assume that block is already in memory and that we are in the
 237      * right mbuf, and that it has space for us. */
 238     memcpy(mbuf->data + mbuf->offset + (mbuf->cur_record - 1) *
 239         is_keysize(tab->is), rec, is_keysize(tab->is));
 240     tab->cur_mblock->state = IS_MBSTATE_DIRTY;
 241 }
 242
 243 /*
 244  * Delete the record right behind the pointer.
 245  */
 246 void is_m_delete_record(is_mtable *tab)
 247 {
 248     is_mbuf *mbuf, *new;
 249
 250     mbuf = tab->cur_mblock->cur_mbuf;
 251     if (mbuf->cur_record >= mbuf->num)  /* top of mbuf */
 252     {
 253         mbuf->num--;
 254         mbuf->cur_record--;
 255     }
 256     else if (mbuf->cur_record == 1) /* beginning of mbuf */
 257     {
 258         mbuf->num--;
 259         mbuf->offset +=is_keysize(tab->is);
 260         mbuf->cur_record = 0;
 261     }
 262     else /* middle of mbuf */
 263     {
 264         /* insert block after current one */
 265         new = xmalloc_mbuf(IS_MBUF_TYPE_SMALL);
 266         new->next = mbuf->next;
 267         mbuf->next = new;
 268
 269         /* virtually transfer everything after current record to new one. */
 270         new->data = mbuf->data;
 271         mbuf->refcount++;
 272         new->offset = mbuf->offset + mbuf->cur_record * is_keysize(tab->is);
 273         new->num = mbuf->num - mbuf->cur_record;
 274
 275         /* old buf now only contains stuff before current record */
 276         mbuf->num = mbuf->cur_record -1;
 277         tab->cur_mblock->cur_mbuf = new;
 278     }
 279     tab->num_records--;
 280     tab->cur_mblock->num_records--;
 281     tab->cur_mblock->state = tab->data->state = IS_MBSTATE_DIRTY;
 282 }
 283
 284 int is_m_write_record(is_mtable *tab, const void *rec)
 285 {
 286     is_mbuf *mbuf, *oldnext, *dmbuf;
 287
 288     /* make sure block is all in memory */
 289     if (tab->cur_mblock->state <= IS_MBSTATE_PARTIAL)
 290         if (read_current_full(tab, tab->cur_mblock) < 0)
 291             return -1;
 292     mbuf = tab->cur_mblock->cur_mbuf;
 293     if (mbuf->cur_record >= mbuf->num)  /* top of mbuf */
 294     {
 295         /* mbuf is reference or full */
 296         if (mbuf->refcount != 1 || mbuf->offset + (mbuf->num + 1) *
 297             is_keysize(tab->is) > is_mbuf_size[mbuf->type])
 298         {
 299             oldnext = mbuf->next;
 300             mbuf->next = xmalloc_mbuf(IS_MBUF_TYPE_LARGE);
 301             mbuf->next->next = oldnext;
 302             mbuf = mbuf->next;
 303             tab->cur_mblock->cur_mbuf = mbuf;
 304             mbuf->cur_record = 0;
 305         }
 306     }
 307     else
 308     {
 309         oldnext = mbuf->next;
 310         mbuf->next = xmalloc_mbuf(IS_MBUF_TYPE_MEDIUM);
 311         mbuf->next->next = dmbuf = xmalloc_mbuf(IS_MBUF_TYPE_SMALL);
 312         dmbuf->data = mbuf->data;
 313         dmbuf->next = oldnext;
 314         dmbuf->offset = mbuf->offset + mbuf->cur_record * is_keysize(tab->is);
 315         dmbuf->num = mbuf->num - mbuf->cur_record;
 316         mbuf->num -= dmbuf->num;
 317         mbuf->refcount++;
 318         mbuf = tab->cur_mblock->cur_mbuf = mbuf->next;
 319         mbuf->cur_record = 0;
 320     }
 321     /*
 322     logf (LOG_DEBUG, "is_m_write_rec(rec == %d)", mbuf->cur_record);
 323     */
 324     memcpy(mbuf->data + mbuf->offset + mbuf->cur_record * is_keysize(tab->is),
 325         rec, is_keysize(tab->is));
 326     mbuf->num++;
 327     mbuf->cur_record++;
 328     tab->num_records++;
 329     tab->cur_mblock->num_records++;
 330     tab->cur_mblock->state = tab->data->state = IS_MBSTATE_DIRTY;
 331     return 0;
 332 }
 333
 334 void is_m_unread_record(is_mtable *tab)
 335 {
 336     assert(tab->cur_mblock->cur_mbuf->cur_record);
 337     if (tab->last_mbuf)
 338         tab->cur_mblock->cur_mbuf = tab->last_mbuf;
 339     else
 340         tab->cur_mblock->cur_mbuf->cur_record--;
 341 }
 342
 343 /*
 344  * non-destructive read.
 345  */
 346 int is_m_peek_record(is_mtable *tab, void *rec)
 347 {
 348     is_mbuf *mbuf;
 349     is_mblock *mblock;
 350
 351     /* make sure block is all in memory */
 352     if (tab->cur_mblock->state <= IS_MBSTATE_PARTIAL)
 353         if (read_current_full(tab, tab->cur_mblock) < 0)
 354             return -1;
 355     mblock = tab->cur_mblock;
 356     mbuf = mblock->cur_mbuf;
 357     if (mbuf->cur_record >= mbuf->num) /* are we at end of mbuf? */
 358     {
 359         if (!mbuf->next) /* end of mblock */
 360         {
 361             if (mblock->next)
 362             {
 363                 mblock = mblock->next;
 364                 if (mblock->state <= IS_MBSTATE_PARTIAL)
 365                     if (read_current_full(tab, mblock) < 0)
 366                         return -1;
 367                 mbuf = mblock->data;
 368             }
 369             else
 370                 return 0;   /* EOTable */
 371         }
 372         else
 373             mbuf = mbuf->next;
 374         mbuf->cur_record = 0;
 375     }
 376     memcpy(rec, mbuf->data + mbuf->offset + mbuf->cur_record *
 377         is_keysize(tab->is), is_keysize(tab->is));
 378     return 1;
 379 }
 380
 381 int is_m_read_record(is_mtable *tab, void *buf, int keep)
 382 {
 383     is_mbuf *mbuf;
 384
 385     /* make sure block is all in memory */
 386     if (tab->cur_mblock->state <= IS_MBSTATE_PARTIAL)
 387         if (read_current_full(tab, tab->cur_mblock) < 0)
 388             return -1;
 389     mbuf = tab->cur_mblock->cur_mbuf;
 390     if (mbuf->cur_record >= mbuf->num) /* are we at end of mbuf? */
 391     {
 392         if (!mbuf->next) /* end of mblock */
 393         {
 394             if (!keep && tab->cur_mblock->state == IS_MBSTATE_CLEAN &&
 395                 tab->cur_mblock->diskpos > 0)
 396             {
 397                 xfree_mbufs(tab->cur_mblock->data);
 398                 tab->cur_mblock->data = 0;
 399                 tab->cur_mblock->state = IS_MBSTATE_UNREAD;
 400             }
 401             if (tab->cur_mblock->next)
 402             {
 403                 tab->cur_mblock = tab->cur_mblock->next;
 404                 if (tab->cur_mblock->state <= IS_MBSTATE_PARTIAL)
 405                     if (read_current_full(tab, tab->cur_mblock) < 0)
 406                         return -1;
 407                 tab->cur_mblock->cur_mbuf = mbuf = tab->cur_mblock->data;
 408                 tab->last_mbuf = 0;
 409             }
 410             else
 411                 return 0;   /* EOTable */
 412         }
 413         else
 414         {
 415             tab->last_mbuf = mbuf;
 416             tab->cur_mblock->cur_mbuf = mbuf = mbuf->next;
 417         }
 418         mbuf->cur_record = 0;
 419     }
 420     else
 421         tab->last_mbuf = 0;
 422     memcpy(buf, mbuf->data + mbuf->offset + mbuf->cur_record *
 423         is_keysize(tab->is), is_keysize(tab->is));
 424     mbuf->cur_record++;
 425     return 1;
 426 }
 427
 428 /*
 429  * TODO: optimize this function by introducing a higher-level search.
 430  */
 431 int is_m_seek_record(is_mtable *tab, const void *rec)
 432 {
 433     char peek[IS_MAX_RECORD];
 434     int rs;
 435
 436     for (;;)
 437     {
 438         if (is_m_read_record(tab, &peek, 1) <= 0)
 439             return 1;
 440         if ((rs = (*tab->is->cmp)(peek, rec)) > 0)
 441         {
 442             is_m_unread_record(tab);
 443             return rs;
 444         }
 445         else if (rs == 0)
 446             return 0;
 447     }
 448 }
 449
 450 int is_m_num_records(is_mtable *tab)
 451 {
 452     if (tab->data->state < IS_MBSTATE_PARTIAL)
 453         if (read_current_full(tab, tab->data) < 0)
 454         {
 455             logf (LOG_FATAL, "read full failed");
 456             exit(1);
 457         }
 458     return tab->num_records;
 459 }