Optimized free block usage.
[idzebra-moved-to-github.git] / 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