isam/memory.c

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