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