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