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
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 #include "config.h"
11 #ifdef __CYGWIN__
12 # define EXTCONST extern const
13 #else
14 # include "EXTERN.h"
15 #endif
16 #include "sdbm.h"
17 #include "tune.h"
18 #include "pair.h"
19
20 #define exhash(item)    sdbm_hash((item).dptr, (item).dsize)
21
22 /* 
23  * forward 
24  */
25 static int seepair proto((char *, int, const char *, int));
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
47 int
48 fitpair(char *pag, int need)
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
64 void
65 putpair(char *pag, datum key, datum val)
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
90 datum
91 getpair(char *pag, datum key)
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
109 int
110 exipair(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
120 #ifdef SEEDUPS
121 int
122 duppair(char *pag, datum key)
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
129 datum
130 getnkey(char *pag, int num)
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
148 int
149 delpair(char *pag, datum key)
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
194 #ifdef HAS_MEMMOVE
195                 dst -= m;
196                 src -= m;
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  */
220 static int
221 seepair(char *pag, register int n, register const char *key, register int siz)
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] &&
229                     memEQ(key, pag + ino[i], siz))
230                         return i;
231                 off = ino[i + 1];
232         }
233         return 0;
234 }
235
236 void
237 splpage(char *pag, char *New, long int sbit)
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);
249         (void) memset(New, 0, PBLKSIZ);
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  */
260                 (void) putpair((exhash(key) & sbit) ? New : pag, key, val);
261
262                 off = ino[1];
263                 n -= 2;
264         }
265
266         debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, 
267                ((short *) New)[0] / 2,
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  */
277 int
278 chkpage(char *pag)
279 {
280         register int n;
281         register int off;
282         register short *ino = (short *) pag;
283
284         if ((n = ino[0]) < 0 || n > (int)(PBLKSIZ / sizeof(short)))
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 }