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