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