dict/drdwr.c

   1 /*
   2  * Copyright (C) 1994-1999, Index Data
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: drdwr.c,v $
   7  * Revision 1.12  1999-05-18 20:00:33  adam
   8  * Minor fix.
   9  *
  10  * Revision 1.11  1999/05/15 14:36:37  adam
  11  * Updated dictionary. Implemented "compression" of dictionary.
  12  *
  13  * Revision 1.10  1999/02/02 14:50:21  adam
  14  * Updated WIN32 code specific sections. Changed header.
  15  *
  16  * Revision 1.9  1997/09/09 13:38:01  adam
  17  * Partial port to WIN95/NT.
  18  *
  19  * Revision 1.8  1995/01/24 11:25:11  adam
  20  * Removed stupid assertion.
  21  *
  22  * Revision 1.7  1994/10/05  10:47:15  adam
  23  * Function pr_lru is non-static now. No warning no more.
  24  *
  25  * Revision 1.6  1994/09/06  13:05:14  adam
  26  * Further development of insertion. Some special cases are
  27  * not properly handled yet! assert(0) are put here. The
  28  * binary search in each page definitely reduce usr CPU.
  29  *
  30  * Revision 1.5  1994/09/01  17:49:38  adam
  31  * Removed stupid line. Work on insertion in dictionary. Not finished yet.
  32  *
  33  */
  34
  35 #include <sys/types.h>
  36 #include <fcntl.h>
  37 #ifndef WIN32
  38 #include <unistd.h>
  39 #endif
  40 #include <string.h>
  41 #include <stdio.h>
  42 #include <stdlib.h>
  43 #include <assert.h>
  44
  45 #include <dict.h>
  46
  47 void dict_pr_lru (Dict_BFile bf)
  48 {
  49     struct Dict_file_block *p;
  50     for (p=bf->lru_back; p; p = p->lru_next)
  51     {
  52         printf (" %d", p->no);
  53     }
  54     printf ("\n");
  55     fflush (stdout);
  56 }
  57
  58 static struct Dict_file_block *find_block (Dict_BFile bf, int no)
  59 {
  60     struct Dict_file_block *p;
  61
  62     for (p=bf->hash_array[no% bf->hash_size]; p; p=p->h_next)
  63         if (p->no == no)
  64             break;
  65     return p;
  66 }
  67
  68 static void release_block (Dict_BFile bf, struct Dict_file_block *p)
  69 {
  70     assert (p);
  71
  72     /* remove from lru queue */
  73     if (p->lru_prev)
  74         p->lru_prev->lru_next = p->lru_next;
  75     else
  76         bf->lru_back = p->lru_next;
  77     if (p->lru_next)
  78         p->lru_next->lru_prev = p->lru_prev;
  79     else
  80         bf->lru_front = p->lru_prev;
  81
  82     /* remove from hash chain */
  83     *p->h_prev = p->h_next;
  84     if (p->h_next)
  85         p->h_next->h_prev = p->h_prev;
  86
  87     /* move to list of free blocks */
  88     p->h_next = bf->free_list;
  89     bf->free_list = p;
  90 }
  91
  92 void dict_bf_flush_blocks (Dict_BFile bf, int no_to_flush)
  93 {
  94     struct Dict_file_block *p;
  95     int i;
  96     for (i=0; i != no_to_flush && bf->lru_back; i++)
  97     {
  98         p = bf->lru_back;
  99         if (p->dirty)
 100         {
 101             if (!bf->compact_flag)
 102                 bf_write (bf->bf, p->no, 0, 0, p->data);
 103             else
 104             {
 105                 int effective_block = p->no / bf->block_size;
 106                 int effective_offset = p->no -
 107                     effective_block * bf->block_size;
 108                 int remain = bf->block_size - effective_offset;
 109
 110                 if (remain >= p->nbytes)
 111                 {
 112                     bf_write (bf->bf, effective_block, effective_offset,
 113                               p->nbytes, p->data);
 114 #if 0
 115                     logf (LOG_LOG, "bf_write no=%d offset=%d size=%d",
 116                           effective_block, effective_offset,
 117                           p->nbytes);
 118 #endif
 119
 120                 }
 121                 else
 122                 {
 123 #if 0
 124                     logf (LOG_LOG, "bf_write1 no=%d offset=%d size=%d",
 125                           effective_block, effective_offset,
 126                           remain);
 127 #endif
 128                     bf_write (bf->bf, effective_block, effective_offset,
 129                               remain, p->data);
 130 #if 0
 131                     logf (LOG_LOG, "bf_write2 no=%d offset=%d size=%d",
 132                           effective_block+1, 0, p->nbytes - remain);
 133 #endif
 134                     bf_write (bf->bf, effective_block+1, 0,
 135                               p->nbytes - remain, (char*)p->data + remain);
 136                 }
 137             }
 138         }
 139         release_block (bf, p);
 140     }
 141 }
 142
 143 static struct Dict_file_block *alloc_block (Dict_BFile bf, int no)
 144 {
 145     struct Dict_file_block *p, **pp;
 146
 147     if (!bf->free_list)
 148         dict_bf_flush_blocks (bf, 1);
 149     assert (bf->free_list);
 150     p = bf->free_list;
 151     bf->free_list = p->h_next;
 152     p->dirty = 0;
 153     p->no = no;
 154
 155     /* insert at front in lru chain */
 156     p->lru_next = NULL;
 157     p->lru_prev = bf->lru_front;
 158     if (bf->lru_front)
 159         bf->lru_front->lru_next = p;
 160     else
 161         bf->lru_back = p;
 162     bf->lru_front = p;
 163
 164     /* insert in hash chain */
 165     pp = bf->hash_array + (no % bf->hash_size);
 166     p->h_next = *pp;
 167     p->h_prev = pp;
 168     if (*pp)
 169         (*pp)->h_prev = &p->h_next;
 170     *pp = p;
 171
 172     return p;
 173 }
 174
 175 static void move_to_front (Dict_BFile bf, struct Dict_file_block *p)
 176 {
 177     /* Already at front? */
 178     if (!p->lru_next)
 179         return ;
 180
 181     /* Remove */
 182     if (p->lru_prev)
 183         p->lru_prev->lru_next = p->lru_next;
 184     else
 185         bf->lru_back = p->lru_next;
 186     p->lru_next->lru_prev = p->lru_prev;
 187
 188     /* Insert at front */
 189     p->lru_next = NULL;
 190     p->lru_prev = bf->lru_front;
 191     if (bf->lru_front)
 192         bf->lru_front->lru_next = p;
 193     else
 194         bf->lru_back = p;
 195     bf->lru_front = p;
 196 }
 197
 198 int dict_bf_readp (Dict_BFile bf, int no, void **bufp)
 199 {
 200     struct Dict_file_block *p;
 201     int i;
 202     if ((p = find_block (bf, no)))
 203     {
 204         *bufp = p->data;
 205         move_to_front (bf, p);
 206         bf->hits++;
 207         return 1;
 208     }
 209     bf->misses++;
 210     p = alloc_block (bf, no);
 211
 212     if (!bf->compact_flag)
 213         i = bf_read (bf->bf, no, 0, 0, p->data);
 214     else
 215     {
 216         int effective_block = no / bf->block_size;
 217         int effective_offset = no - effective_block * bf->block_size;
 218
 219         i = bf_read (bf->bf, effective_block, effective_offset,
 220                      bf->block_size - effective_offset, p->data);
 221         if (i > 0 && effective_offset > 0)
 222             i = bf_read (bf->bf, effective_block+1, 0, effective_offset,
 223                          (char*) p->data + bf->block_size - effective_offset);
 224         i = 1;
 225     }
 226     if (i > 0)
 227     {
 228         *bufp = p->data;
 229         return i;
 230     }
 231     release_block (bf, p);
 232     *bufp = NULL;
 233     return i;
 234 }
 235
 236 int dict_bf_newp (Dict_BFile dbf, int no, void **bufp, int nbytes)
 237 {
 238     struct Dict_file_block *p;
 239     if (!(p = find_block (dbf, no)))
 240         p = alloc_block (dbf, no);
 241     else
 242         move_to_front (dbf, p);
 243     *bufp = p->data;
 244     memset (p->data, 0, dbf->block_size);
 245     p->dirty = 1;
 246     p->nbytes = nbytes;
 247 #if 0
 248     printf ("bf_newp of %d:", no);
 249     dict_pr_lru (dbf);
 250 #endif
 251     return 1;
 252 }
 253
 254 int dict_bf_touch (Dict_BFile dbf, int no)
 255 {
 256     struct Dict_file_block *p;
 257     if ((p = find_block (dbf, no)))
 258     {
 259         p->dirty = 1;
 260         return 0;
 261     }
 262     return -1;
 263 }
 264