dict/drdwr.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: drdwr.c,v $
   7  * Revision 1.6  1994-09-06 13:05:14  adam
   8  * Further development of insertion. Some special cases are
   9  * not properly handled yet! assert(0) are put here. The
  10  * binary search in each page definitely reduce usr CPU.
  11  *
  12  * Revision 1.5  1994/09/01  17:49:38  adam
  13  * Removed stupid line. Work on insertion in dictionary. Not finished yet.
  14  *
  15  */
  16
  17 #include <sys/types.h>
  18 #include <fcntl.h>
  19 #include <unistd.h>
  20 #include <string.h>
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <assert.h>
  24
  25 #include <dict.h>
  26
  27 static void pr_lru (Dict_BFile bf)
  28 {
  29     struct Dict_file_block *p;
  30     for (p=bf->lru_back; p; p = p->lru_next)
  31     {
  32         printf (" %d", p->no);
  33     }
  34     printf ("\n");
  35     fflush (stdout);
  36 }
  37
  38 static struct Dict_file_block *find_block (Dict_BFile bf, int no)
  39 {
  40     struct Dict_file_block *p;
  41
  42     for (p=bf->hash_array[no% bf->hash_size]; p; p=p->h_next)
  43         if (p->no == no)
  44             break;
  45     return p;
  46 }
  47
  48 static void release_block (Dict_BFile bf, struct Dict_file_block *p)
  49 {
  50     assert (p);
  51
  52     /* remove from lru queue */
  53     if (p->lru_prev)
  54         p->lru_prev->lru_next = p->lru_next;
  55     else
  56         bf->lru_back = p->lru_next;
  57     if (p->lru_next)
  58         p->lru_next->lru_prev = p->lru_prev;
  59     else
  60         bf->lru_front = p->lru_prev;
  61
  62     /* remove from hash chain */
  63     *p->h_prev = p->h_next;
  64     if (p->h_next)
  65         p->h_next->h_prev = p->h_prev;
  66
  67     /* move to list of free blocks */
  68     p->h_next = bf->free_list;
  69     bf->free_list = p;
  70 }
  71
  72 void dict_bf_flush_blocks (Dict_BFile bf, int no_to_flush)
  73 {
  74     struct Dict_file_block *p;
  75     int i;
  76     for (i=0; i != no_to_flush && bf->lru_back; i++)
  77     {
  78         p = bf->lru_back;
  79         if (p->dirty)
  80         {
  81             bf_write (bf->bf, p->no, 0, 0, p->data);
  82         }
  83         release_block (bf, p);
  84     }
  85 }
  86
  87 static struct Dict_file_block *alloc_block (Dict_BFile bf, int no)
  88 {
  89     struct Dict_file_block *p, **pp;
  90
  91     if (!bf->free_list)
  92         dict_bf_flush_blocks (bf, 1);
  93     assert (bf->free_list);
  94     p = bf->free_list;
  95     bf->free_list = p->h_next;
  96     p->dirty = 0;
  97     p->no = no;
  98
  99     /* insert at front in lru chain */
 100     p->lru_next = NULL;
 101     p->lru_prev = bf->lru_front;
 102     if (bf->lru_front)
 103         bf->lru_front->lru_next = p;
 104     else
 105         bf->lru_back = p;
 106     bf->lru_front = p;
 107
 108     /* insert in hash chain */
 109     pp = bf->hash_array + (no % bf->hash_size);
 110     p->h_next = *pp;
 111     p->h_prev = pp;
 112     if (*pp)
 113         (*pp)->h_prev = &p->h_next;
 114     *pp = p;
 115
 116     return p;
 117 }
 118
 119 static void move_to_front (Dict_BFile bf, struct Dict_file_block *p)
 120 {
 121     /* Already at front? */
 122     if (!p->lru_next)
 123         return ;
 124
 125     /* Remove */
 126     if (p->lru_prev)
 127         p->lru_prev->lru_next = p->lru_next;
 128     else
 129         bf->lru_back = p->lru_next;
 130     p->lru_next->lru_prev = p->lru_prev;
 131
 132     /* Insert at front */
 133     p->lru_next = NULL;
 134     p->lru_prev = bf->lru_front;
 135     if (bf->lru_front)
 136         bf->lru_front->lru_next = p;
 137     else
 138         bf->lru_back = p;
 139     bf->lru_front = p;
 140 }
 141
 142 int dict_bf_readp (Dict_BFile bf, int no, void **bufp)
 143 {
 144     struct Dict_file_block *p;
 145     int i;
 146     assert (no < 1000);
 147     if ((p = find_block (bf, no)))
 148     {
 149         *bufp = p->data;
 150         move_to_front (bf, p);
 151         bf->hits++;
 152         return 1;
 153     }
 154     bf->misses++;
 155     p = alloc_block (bf, no);
 156     i = bf_read (bf->bf, no, 0, 0, p->data);
 157     if (i > 0)
 158     {
 159         *bufp = p->data;
 160         return i;
 161     }
 162     release_block (bf, p);
 163     *bufp = NULL;
 164     return i;
 165 }
 166
 167 int dict_bf_newp (Dict_BFile dbf, int no, void **bufp)
 168 {
 169     struct Dict_file_block *p;
 170     if (!(p = find_block (dbf, no)))
 171         p = alloc_block (dbf, no);
 172     else
 173         move_to_front (dbf, p);
 174     *bufp = p->data;
 175     memset (p->data, 0, dbf->block_size);
 176     p->dirty = 1;
 177 #if 0
 178     printf ("bf_newp of %d:", no);
 179     pr_lru (dbf);
 180 #endif
 181     return 1;
 182 }
 183
 184 int dict_bf_touch (Dict_BFile dbf, int no)
 185 {
 186     struct Dict_file_block *p;
 187     if ((p = find_block (dbf, no)))
 188     {
 189         p->dirty = 1;
 190         return 0;
 191     }
 192     return -1;
 193 }
 194