isam/memory.c

   1 /* $Id: memory.c,v 1.18 2002-08-02 19:26:56 adam Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
   3    Index Data Aps
   4
   5 This file is part of the Zebra server.
   6
   7 Zebra is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Zebra; see the file LICENSE.zebra.  If not, write to the
  19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.
  21 */
  22
  23
  24
  25 /*
  26  * This module accesses and rearranges the records of the tables.
  27  */
  28
  29 #include <assert.h>
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33
  34 #include <zebrautl.h>
  35 #include <isam.h>
  36
  37 int is_mbuf_size[3] = { 0, 1024, 4096 };
  38
  39 static is_mblock *mblock_tmplist = 0, *mblock_freelist = 0;
  40 static is_mbuf *mbuf_freelist[3] = {0, 0, 0};
  41
  42 #define MALLOC_CHUNK 20
  43
  44 is_mblock *xmalloc_mblock()
  45 {
  46     is_mblock *tmp;
  47     int i;
  48
  49     if (!mblock_freelist)
  50     {
  51         mblock_freelist = (is_mblock *)
  52             xmalloc(sizeof(is_mblock) * MALLOC_CHUNK);
  53         for (i = 0; i < MALLOC_CHUNK - 1; i++)
  54             mblock_freelist[i].next = &mblock_freelist[i+1];
  55         mblock_freelist[i].next = 0;
  56     }
  57     tmp = mblock_freelist;
  58     mblock_freelist = mblock_freelist->next;
  59     tmp->next = 0;
  60     tmp->state = IS_MBSTATE_UNREAD;
  61     tmp->data = 0;
  62     return tmp;
  63 }
  64
  65 is_mbuf *xmalloc_mbuf(int type)
  66 {
  67     is_mbuf *tmp;
  68
  69     if (mbuf_freelist[type])
  70     {
  71         tmp = mbuf_freelist[type];
  72         mbuf_freelist[type] = tmp->next;
  73     }
  74     else
  75     {
  76         tmp = (is_mbuf*) xmalloc(sizeof(is_mbuf) + is_mbuf_size[type]);
  77         tmp->type = type;
  78     }
  79     tmp->refcount = type ? 1 : 0;
  80     tmp->offset = tmp->num = tmp->cur_record = 0;
  81     tmp->data = (char*) tmp + sizeof(is_mbuf);
  82     tmp->next = 0;
  83     return tmp;
  84 }
  85
  86 void xfree_mbuf(is_mbuf *p)
  87 {
  88     p->next = mbuf_freelist[p->type];
  89     mbuf_freelist[p->type] = p;
  90 }
  91
  92 void xfree_mbufs(is_mbuf *l)
  93 {
  94     is_mbuf *p;
  95
  96     while (l)
  97     {
  98         p = l->next;
  99         xfree_mbuf(l);
 100         l = p;
 101     }
 102 }
 103
 104 void xfree_mblock(is_mblock *p)
 105 {
 106     xfree_mbufs(p->data);
 107     p->next = mblock_freelist;
 108     mblock_freelist = p;
 109 }
 110
 111 void xrelease_mblock(is_mblock *p)
 112 {
 113     p->next = mblock_tmplist;
 114     mblock_tmplist = p;
 115 }
 116
 117 void xfree_mblocks(is_mblock *l)
 118 {
 119     is_mblock *p;
 120
 121     while (l)
 122     {
 123         p = l->next;
 124         xfree_mblock(l);
 125         l = p;
 126     }
 127 }
 128
 129 void is_m_establish_tab(ISAM is, is_mtable *tab, ISAM_P pos)
 130 {
 131     tab->data = xmalloc_mblock();
 132     if (pos > 0)
 133     {
 134         tab->pos_type = is_type(pos);
 135         tab->num_records = -1;
 136         tab->data->num_records = -1;
 137         tab->data->diskpos = is_block(pos);
 138         tab->data->state = IS_MBSTATE_UNREAD;
 139         tab->data->data = 0;
 140         tab->cur_mblock = tab->data;
 141         tab->cur_mblock->cur_mbuf = 0;
 142         tab->last_mbuf = 0;
 143     }
 144     else /* new block */
 145     {
 146         tab->pos_type = 0;
 147         tab->num_records = 0;
 148         tab->data->num_records = 0;
 149         tab->data->diskpos = -1;
 150         tab->data->state = IS_MBSTATE_CLEAN;
 151         tab->data->data = xmalloc_mbuf(IS_MBUF_TYPE_LARGE);
 152         tab->cur_mblock = tab->data;
 153         tab->cur_mblock->cur_mbuf = tab->data->data;
 154         tab->cur_mblock->cur_mbuf->cur_record = 0;
 155         tab->last_mbuf = 0;
 156     }
 157     tab->is = is;
 158 }
 159
 160 void is_m_release_tab(is_mtable *tab)
 161 {
 162     xfree_mblocks(tab->data);
 163     xfree_mblocks(mblock_tmplist);
 164     mblock_tmplist = 0;
 165 }
 166
 167 void is_m_rewind(is_mtable *tab)
 168 {
 169     tab->cur_mblock = tab->data;
 170     if (tab->data)
 171     {
 172         tab->data->cur_mbuf = tab->data->data;
 173         if (tab->data->data)
 174             tab->data->data->cur_record = 0;
 175     }
 176 }
 177
 178 static int read_current_full(is_mtable *tab, is_mblock *mblock)
 179 {
 180     if (is_p_read_full(tab, mblock) < 0)
 181         return -1;
 182     if (mblock->nextpos && !mblock->next)
 183     {
 184         mblock->next = xmalloc_mblock();
 185         mblock->next->diskpos = mblock->nextpos;
 186         mblock->next->state = IS_MBSTATE_UNREAD;
 187         mblock->next->data = 0;
 188     }
 189     mblock->cur_mbuf = mblock->data;
 190     mblock->data->cur_record = 0;
 191     return 0;
 192 }
 193
 194 int is_m_read_full(is_mtable *tab, is_mblock *mblock)
 195 {
 196     return read_current_full(tab, mblock);
 197 }
 198
 199 /*
 200  * replace the record right behind the pointer.
 201  */
 202 void is_m_replace_record(is_mtable *tab, const void *rec)
 203 {
 204     is_mbuf *mbuf = tab->cur_mblock->cur_mbuf;
 205
 206     /* we assume that block is already in memory and that we are in the
 207      * right mbuf, and that it has space for us. */
 208     memcpy(mbuf->data + mbuf->offset + (mbuf->cur_record - 1) *
 209         is_keysize(tab->is), rec, is_keysize(tab->is));
 210     tab->cur_mblock->state = IS_MBSTATE_DIRTY;
 211 }
 212
 213 /*
 214  * Delete the record right behind the pointer.
 215  */
 216 void is_m_delete_record(is_mtable *tab)
 217 {
 218     is_mbuf *mbuf, *inew;
 219
 220     mbuf = tab->cur_mblock->cur_mbuf;
 221     if (mbuf->cur_record >= mbuf->num)  /* top of mbuf */
 222     {
 223         mbuf->num--;
 224         mbuf->cur_record--;
 225     }
 226     else if (mbuf->cur_record == 1) /* beginning of mbuf */
 227     {
 228         mbuf->num--;
 229         mbuf->offset +=is_keysize(tab->is);
 230         mbuf->cur_record = 0;
 231     }
 232     else /* middle of mbuf */
 233     {
 234         /* insert block after current one */
 235         inew = xmalloc_mbuf(IS_MBUF_TYPE_SMALL);
 236         inew->next = mbuf->next;
 237         mbuf->next = inew;
 238
 239         /* virtually transfer everything after current record to new one. */
 240         inew->data = mbuf->data;
 241         mbuf->refcount++;
 242         inew->offset = mbuf->offset + mbuf->cur_record * is_keysize(tab->is);
 243         inew->num = mbuf->num - mbuf->cur_record;
 244
 245         /* old buf now only contains stuff before current record */
 246         mbuf->num = mbuf->cur_record -1;
 247         tab->cur_mblock->cur_mbuf = inew;
 248     }
 249     tab->num_records--;
 250     tab->cur_mblock->num_records--;
 251     tab->cur_mblock->state = tab->data->state = IS_MBSTATE_DIRTY;
 252 }
 253
 254 int is_m_write_record(is_mtable *tab, const void *rec)
 255 {
 256     is_mbuf *mbuf, *oldnext, *dmbuf;
 257
 258     /* make sure block is all in memory */
 259     if (tab->cur_mblock->state <= IS_MBSTATE_PARTIAL)
 260         if (read_current_full(tab, tab->cur_mblock) < 0)
 261             return -1;
 262     mbuf = tab->cur_mblock->cur_mbuf;
 263     if (mbuf->cur_record >= mbuf->num)  /* top of mbuf */
 264     {
 265         /* mbuf is reference or full */
 266         if (mbuf->refcount != 1 || mbuf->offset + (mbuf->num + 1) *
 267             is_keysize(tab->is) > is_mbuf_size[mbuf->type])
 268         {
 269             oldnext = mbuf->next;
 270             mbuf->next = xmalloc_mbuf(IS_MBUF_TYPE_LARGE);
 271             mbuf->next->next = oldnext;
 272             mbuf = mbuf->next;
 273             tab->cur_mblock->cur_mbuf = mbuf;
 274             mbuf->cur_record = 0;
 275         }
 276     }
 277     else
 278     {
 279         oldnext = mbuf->next;
 280         mbuf->next = xmalloc_mbuf(IS_MBUF_TYPE_MEDIUM);
 281         mbuf->next->next = dmbuf = xmalloc_mbuf(IS_MBUF_TYPE_SMALL);
 282         dmbuf->data = mbuf->data;
 283         dmbuf->next = oldnext;
 284         dmbuf->offset = mbuf->offset + mbuf->cur_record * is_keysize(tab->is);
 285         dmbuf->num = mbuf->num - mbuf->cur_record;
 286         mbuf->num -= dmbuf->num;
 287         mbuf->refcount++;
 288         mbuf = tab->cur_mblock->cur_mbuf = mbuf->next;
 289         mbuf->cur_record = 0;
 290     }
 291     /*
 292     logf (LOG_DEBUG, "is_m_write_rec(rec == %d)", mbuf->cur_record);
 293     */
 294     memcpy(mbuf->data + mbuf->offset + mbuf->cur_record * is_keysize(tab->is),
 295         rec, is_keysize(tab->is));
 296     mbuf->num++;
 297     mbuf->cur_record++;
 298     tab->num_records++;
 299     tab->cur_mblock->num_records++;
 300     tab->cur_mblock->state = tab->data->state = IS_MBSTATE_DIRTY;
 301     return 0;
 302 }
 303
 304 void is_m_unread_record(is_mtable *tab)
 305 {
 306     assert(tab->cur_mblock->cur_mbuf->cur_record);
 307     if (tab->last_mbuf)
 308         tab->cur_mblock->cur_mbuf = tab->last_mbuf;
 309     else
 310         tab->cur_mblock->cur_mbuf->cur_record--;
 311 }
 312
 313 /*
 314  * non-destructive read.
 315  */
 316 int is_m_peek_record(is_mtable *tab, void *rec)
 317 {
 318     is_mbuf *mbuf;
 319     is_mblock *mblock;
 320
 321     /* make sure block is all in memory */
 322     if (tab->cur_mblock->state <= IS_MBSTATE_PARTIAL)
 323         if (read_current_full(tab, tab->cur_mblock) < 0)
 324             return -1;
 325     mblock = tab->cur_mblock;
 326     mbuf = mblock->cur_mbuf;
 327     if (mbuf->cur_record >= mbuf->num) /* are we at end of mbuf? */
 328     {
 329         if (!mbuf->next) /* end of mblock */
 330         {
 331             if (mblock->next)
 332             {
 333                 mblock = mblock->next;
 334                 if (mblock->state <= IS_MBSTATE_PARTIAL)
 335                     if (read_current_full(tab, mblock) < 0)
 336                         return -1;
 337                 mbuf = mblock->data;
 338             }
 339             else
 340                 return 0;   /* EOTable */
 341         }
 342         else
 343             mbuf = mbuf->next;
 344         mbuf->cur_record = 0;
 345     }
 346     memcpy(rec, mbuf->data + mbuf->offset + mbuf->cur_record *
 347         is_keysize(tab->is), is_keysize(tab->is));
 348     return 1;
 349 }
 350
 351 int is_m_read_record(is_mtable *tab, void *buf, int keep)
 352 {
 353     is_mbuf *mbuf;
 354
 355     /* make sure block is all in memory */
 356     if (tab->cur_mblock->state <= IS_MBSTATE_PARTIAL)
 357         if (read_current_full(tab, tab->cur_mblock) < 0)
 358             return -1;
 359     mbuf = tab->cur_mblock->cur_mbuf;
 360     if (mbuf->cur_record >= mbuf->num) /* are we at end of mbuf? */
 361     {
 362         if (!mbuf->next) /* end of mblock */
 363         {
 364             if (!keep && tab->cur_mblock->state == IS_MBSTATE_CLEAN &&
 365                 tab->cur_mblock->diskpos > 0)
 366             {
 367                 xfree_mbufs(tab->cur_mblock->data);
 368                 tab->cur_mblock->data = 0;
 369                 tab->cur_mblock->state = IS_MBSTATE_UNREAD;
 370             }
 371             if (tab->cur_mblock->next)
 372             {
 373                 tab->cur_mblock = tab->cur_mblock->next;
 374                 if (tab->cur_mblock->state <= IS_MBSTATE_PARTIAL)
 375                     if (read_current_full(tab, tab->cur_mblock) < 0)
 376                         return -1;
 377                 tab->cur_mblock->cur_mbuf = mbuf = tab->cur_mblock->data;
 378                 tab->last_mbuf = 0;
 379             }
 380             else
 381                 return 0;   /* EOTable */
 382         }
 383         else
 384         {
 385             tab->last_mbuf = mbuf;
 386             tab->cur_mblock->cur_mbuf = mbuf = mbuf->next;
 387         }
 388         mbuf->cur_record = 0;
 389     }
 390     else
 391         tab->last_mbuf = 0;
 392     memcpy(buf, mbuf->data + mbuf->offset + mbuf->cur_record *
 393         is_keysize(tab->is), is_keysize(tab->is));
 394     mbuf->cur_record++;
 395     return 1;
 396 }
 397
 398 /*
 399  * TODO: optimize this function by introducing a higher-level search.
 400  */
 401 int is_m_seek_record(is_mtable *tab, const void *rec)
 402 {
 403     char peek[IS_MAX_RECORD];
 404     int rs;
 405
 406     for (;;)
 407     {
 408         if (is_m_read_record(tab, &peek, 1) <= 0)
 409             return 1;
 410         if ((rs = (*tab->is->cmp)(peek, rec)) > 0)
 411         {
 412             is_m_unread_record(tab);
 413             return rs;
 414         }
 415         else if (rs == 0)
 416             return 0;
 417     }
 418 }
 419
 420 int is_m_num_records(is_mtable *tab)
 421 {
 422     if (tab->data->state < IS_MBSTATE_PARTIAL)
 423         if (read_current_full(tab, tab->data) < 0)
 424         {
 425             logf (LOG_FATAL, "read full failed");
 426             exit(1);
 427         }
 428     return tab->num_records;
 429 }