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