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