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