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