This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
Further ANSI changes now builds and passes (most) tests
[perl5.git] / ext / SDBM_File / sdbm / pair.c
1 /*
2  * sdbm - ndbm work-alike hashed database library
3  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
4  * author: oz@nexus.yorku.ca
5  * status: public domain.
6  *
7  * page-level routines
8  */
9
10 #ifndef lint
11 static char rcsid[] = "$Id: pair.c,v 1.10 90/12/13 13:00:35 oz Exp $";
12 #endif
13
14 #include "config.h"
15 #include "sdbm.h"
16 #include "tune.h"
17 #include "pair.h"
18
19 #define exhash(item)    sdbm_hash((item).dptr, (item).dsize)
20
21 /* 
22  * forward 
23  */
24 static int seepair proto((char *, int, char *, int));
25
26 /*
27  * page format:
28  *      +------------------------------+
29  * ino  | n | keyoff | datoff | keyoff |
30  *      +------------+--------+--------+
31  *      | datoff | - - - ---->         |
32  *      +--------+---------------------+
33  *      |        F R E E A R E A       |
34  *      +--------------+---------------+
35  *      |  <---- - - - | data          |
36  *      +--------+-----+----+----------+
37  *      |  key   | data     | key      |
38  *      +--------+----------+----------+
39  *
40  * calculating the offsets for free area:  if the number
41  * of entries (ino[0]) is zero, the offset to the END of
42  * the free area is the block size. Otherwise, it is the
43  * nth (ino[ino[0]]) entry's offset.
44  */
45
46 int
47 fitpair(char *pag, int need)
48 {
49         register int n;
50         register int off;
51         register int free;
52         register short *ino = (short *) pag;
53
54         off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
55         free = off - (n + 1) * sizeof(short);
56         need += 2 * sizeof(short);
57
58         debug(("free %d need %d\n", free, need));
59
60         return need <= free;
61 }
62
63 void
64 putpair(char *pag, datum key, datum val)
65 {
66         register int n;
67         register int off;
68         register short *ino = (short *) pag;
69
70         off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
71 /*
72  * enter the key first
73  */
74         off -= key.dsize;
75         (void) memcpy(pag + off, key.dptr, key.dsize);
76         ino[n + 1] = off;
77 /*
78  * now the data
79  */
80         off -= val.dsize;
81         (void) memcpy(pag + off, val.dptr, val.dsize);
82         ino[n + 2] = off;
83 /*
84  * adjust item count
85  */
86         ino[0] += 2;
87 }
88
89 datum
90 getpair(char *pag, datum key)
91 {
92         register int i;
93         register int n;
94         datum val;
95         register short *ino = (short *) pag;
96
97         if ((n = ino[0]) == 0)
98                 return nullitem;
99
100         if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
101                 return nullitem;
102
103         val.dptr = pag + ino[i + 1];
104         val.dsize = ino[i] - ino[i + 1];
105         return val;
106 }
107
108 #ifdef SEEDUPS
109 int
110 duppair(char *pag, datum key)
111 {
112         register short *ino = (short *) pag;
113         return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
114 }
115 #endif
116
117 datum
118 getnkey(char *pag, int num)
119 {
120         datum key;
121         register int off;
122         register short *ino = (short *) pag;
123
124         num = num * 2 - 1;
125         if (ino[0] == 0 || num > ino[0])
126                 return nullitem;
127
128         off = (num > 1) ? ino[num - 1] : PBLKSIZ;
129
130         key.dptr = pag + ino[num];
131         key.dsize = off - ino[num];
132
133         return key;
134 }
135
136 int
137 delpair(char *pag, datum key)
138 {
139         register int n;
140         register int i;
141         register short *ino = (short *) pag;
142
143         if ((n = ino[0]) == 0)
144                 return 0;
145
146         if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
147                 return 0;
148 /*
149  * found the key. if it is the last entry
150  * [i.e. i == n - 1] we just adjust the entry count.
151  * hard case: move all data down onto the deleted pair,
152  * shift offsets onto deleted offsets, and adjust them.
153  * [note: 0 < i < n]
154  */
155         if (i < n - 1) {
156                 register int m;
157                 register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
158                 register char *src = pag + ino[i + 1];
159                 register int   zoo = dst - src;
160
161                 debug(("free-up %d ", zoo));
162 /*
163  * shift data/keys down
164  */
165                 m = ino[i + 1] - ino[n];
166 #ifdef DUFF
167 #define MOVB    *--dst = *--src
168
169                 if (m > 0) {
170                         register int loop = (m + 8 - 1) >> 3;
171
172                         switch (m & (8 - 1)) {
173                         case 0: do {
174                                 MOVB;   case 7: MOVB;
175                         case 6: MOVB;   case 5: MOVB;
176                         case 4: MOVB;   case 3: MOVB;
177                         case 2: MOVB;   case 1: MOVB;
178                                 } while (--loop);
179                         }
180                 }
181 #else
182 #ifdef HAS_MEMMOVE
183                 dst -= m;
184                 src -= m;
185                 memmove(dst, src, m);
186 #else
187                 while (m--)
188                         *--dst = *--src;
189 #endif
190 #endif
191 /*
192  * adjust offset index up
193  */
194                 while (i < n - 1) {
195                         ino[i] = ino[i + 2] + zoo;
196                         i++;
197                 }
198         }
199         ino[0] -= 2;
200         return 1;
201 }
202
203 /*
204  * search for the key in the page.
205  * return offset index in the range 0 < i < n.
206  * return 0 if not found.
207  */
208 static int
209 seepair(char *pag, register int n, register char *key, register int siz)
210 {
211         register int i;
212         register int off = PBLKSIZ;
213         register short *ino = (short *) pag;
214
215         for (i = 1; i < n; i += 2) {
216                 if (siz == off - ino[i] &&
217                     memEQ(key, pag + ino[i], siz))
218                         return i;
219                 off = ino[i + 1];
220         }
221         return 0;
222 }
223
224 void
225 splpage(char *pag, char *New, long int sbit)
226 {
227         datum key;
228         datum val;
229
230         register int n;
231         register int off = PBLKSIZ;
232         char cur[PBLKSIZ];
233         register short *ino = (short *) cur;
234
235         (void) memcpy(cur, pag, PBLKSIZ);
236         (void) memset(pag, 0, PBLKSIZ);
237         (void) memset(New, 0, PBLKSIZ);
238
239         n = ino[0];
240         for (ino++; n > 0; ino += 2) {
241                 key.dptr = cur + ino[0]; 
242                 key.dsize = off - ino[0];
243                 val.dptr = cur + ino[1];
244                 val.dsize = ino[0] - ino[1];
245 /*
246  * select the page pointer (by looking at sbit) and insert
247  */
248                 (void) putpair((exhash(key) & sbit) ? New : pag, key, val);
249
250                 off = ino[1];
251                 n -= 2;
252         }
253
254         debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, 
255                ((short *) New)[0] / 2,
256                ((short *) pag)[0] / 2));
257 }
258
259 /*
260  * check page sanity: 
261  * number of entries should be something
262  * reasonable, and all offsets in the index should be in order.
263  * this could be made more rigorous.
264  */
265 int
266 chkpage(char *pag)
267 {
268         register int n;
269         register int off;
270         register short *ino = (short *) pag;
271
272         if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short))
273                 return 0;
274
275         if (n > 0) {
276                 off = PBLKSIZ;
277                 for (ino++; n > 0; ino += 2) {
278                         if (ino[0] > off || ino[1] > off ||
279                             ino[1] > ino[0])
280                                 return 0;
281                         off = ino[1];
282                         n -= 2;
283                 }
284         }
285         return 1;
286 }