2 * Copyright (C) 1994, Index Data I/S
4 * Sebastian Hammer, Adam Dickmeiss
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.
12 * Revision 1.5 1994/09/01 17:49:38 adam
13 * Removed stupid line. Work on insertion in dictionary. Not finished yet.
17 #include <sys/types.h>
27 static void pr_lru (Dict_BFile bf)
29 struct Dict_file_block *p;
30 for (p=bf->lru_back; p; p = p->lru_next)
32 printf (" %d", p->no);
38 static struct Dict_file_block *find_block (Dict_BFile bf, int no)
40 struct Dict_file_block *p;
42 for (p=bf->hash_array[no% bf->hash_size]; p; p=p->h_next)
48 static void release_block (Dict_BFile bf, struct Dict_file_block *p)
52 /* remove from lru queue */
54 p->lru_prev->lru_next = p->lru_next;
56 bf->lru_back = p->lru_next;
58 p->lru_next->lru_prev = p->lru_prev;
60 bf->lru_front = p->lru_prev;
62 /* remove from hash chain */
63 *p->h_prev = p->h_next;
65 p->h_next->h_prev = p->h_prev;
67 /* move to list of free blocks */
68 p->h_next = bf->free_list;
72 void dict_bf_flush_blocks (Dict_BFile bf, int no_to_flush)
74 struct Dict_file_block *p;
76 for (i=0; i != no_to_flush && bf->lru_back; i++)
81 bf_write (bf->bf, p->no, 0, 0, p->data);
83 release_block (bf, p);
87 static struct Dict_file_block *alloc_block (Dict_BFile bf, int no)
89 struct Dict_file_block *p, **pp;
92 dict_bf_flush_blocks (bf, 1);
93 assert (bf->free_list);
95 bf->free_list = p->h_next;
99 /* insert at front in lru chain */
101 p->lru_prev = bf->lru_front;
103 bf->lru_front->lru_next = p;
108 /* insert in hash chain */
109 pp = bf->hash_array + (no % bf->hash_size);
113 (*pp)->h_prev = &p->h_next;
119 static void move_to_front (Dict_BFile bf, struct Dict_file_block *p)
121 /* Already at front? */
127 p->lru_prev->lru_next = p->lru_next;
129 bf->lru_back = p->lru_next;
130 p->lru_next->lru_prev = p->lru_prev;
132 /* Insert at front */
134 p->lru_prev = bf->lru_front;
136 bf->lru_front->lru_next = p;
142 int dict_bf_readp (Dict_BFile bf, int no, void **bufp)
144 struct Dict_file_block *p;
147 if ((p = find_block (bf, no)))
150 move_to_front (bf, p);
155 p = alloc_block (bf, no);
156 i = bf_read (bf->bf, no, 0, 0, p->data);
162 release_block (bf, p);
167 int dict_bf_newp (Dict_BFile dbf, int no, void **bufp)
169 struct Dict_file_block *p;
170 if (!(p = find_block (dbf, no)))
171 p = alloc_block (dbf, no);
173 move_to_front (dbf, p);
175 memset (p->data, 0, dbf->block_size);
178 printf ("bf_newp of %d:", no);
184 int dict_bf_touch (Dict_BFile dbf, int no)
186 struct Dict_file_block *p;
187 if ((p = find_block (dbf, no)))