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