08a895b74fb4d6e0d8b0f487955a8b8039bfd7f1
[idzebra-moved-to-github.git] / index / kcompare.c
1 /* $Id: kcompare.c,v 1.45 2004-06-02 12:29:03 adam Exp $
2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004
3    Index Data Aps
4
5 This file is part of the Zebra server.
6
7 Zebra is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with Zebra; see the file LICENSE.zebra.  If not, write to the
19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.
21 */
22
23 #include <stdlib.h>
24 #include <string.h>
25 #include <stdio.h>
26 #include <assert.h>
27
28 #include "index.h"
29
30 #define INT_CODEC_NEW 0
31 #define CODEC_INLINE inline
32 void key_logdump_txt (int logmask, const void *p, const char *txt)
33 {
34     struct it_key key;
35     if (p)
36     {
37         memcpy (&key, p, sizeof(key));
38         logf (logmask, "%7d:%-4d %s", key.sysno, key.seqno,txt);
39     }
40     else
41         logf(logmask, " (null) %s",txt);
42 }
43
44 void key_logdump (int logmask, const void *p)
45 {
46     key_logdump_txt(logmask,p,"");
47 }
48
49 int key_compare_it (const void *p1, const void *p2)
50 {
51     if (((struct it_key *) p1)->sysno != ((struct it_key *) p2)->sysno)
52     {
53         if (((struct it_key *) p1)->sysno > ((struct it_key *) p2)->sysno)
54             return 2;
55         else
56             return -2;
57     }
58     if (((struct it_key *) p1)->seqno != ((struct it_key *) p2)->seqno)
59     {
60         if (((struct it_key *) p1)->seqno > ((struct it_key *) p2)->seqno)
61             return 1;
62         else
63             return -1;
64     }
65     return 0;
66 }
67
68 char *key_print_it (const void *p, char *buf)
69 {
70     const struct it_key *i = p;
71     sprintf (buf, "%d:%d", i->sysno, i->seqno);
72     return buf;
73 }
74
75 int key_compare (const void *p1, const void *p2)
76 {
77     struct it_key i1, i2;
78     memcpy (&i1, p1, sizeof(i1));
79     memcpy (&i2, p2, sizeof(i2));
80     if (i1.sysno != i2.sysno)
81     {
82         if (i1.sysno > i2.sysno)
83             return 2;
84         else
85             return -2;
86     }
87     if (i1.seqno != i2.seqno)
88     {
89         if (i1.seqno > i2.seqno)
90             return 1;
91         else
92             return -1;
93     }
94     return 0;
95 }
96
97 int key_qsort_compare (const void *p1, const void *p2)
98 {
99     int r;
100     size_t l;
101     char *cp1 = *(char **) p1;
102     char *cp2 = *(char **) p2;
103  
104     if ((r = strcmp (cp1, cp2)))
105         return r;
106     l = strlen(cp1)+1;
107     if ((r = key_compare (cp1+l+1, cp2+l+1)))
108         return r;
109     return cp1[l] - cp2[l];
110 }
111
112 struct iscz1_code_info {
113     struct it_key key;
114 };
115
116
117 static void *iscz1_code_start (int mode)
118 {
119     struct iscz1_code_info *p = (struct iscz1_code_info *)
120         xmalloc (sizeof(*p));
121     p->key.sysno = 0;
122     p->key.seqno = 0;
123     return p;
124 }
125
126 static void iscz1_code_reset (void *vp)
127 {
128     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
129     p->key.sysno = 0;
130     p->key.seqno = 0;
131 }
132
133 static void iscz1_code_stop (int mode, void *p)
134 {
135     xfree (p);
136 }
137
138 #if INT_CODEC_NEW 
139 static CODEC_INLINE void iscz1_encode_int (unsigned d, char **dst)
140 {
141     unsigned char *bp = (unsigned char*) *dst;
142
143     while (d > 127)
144     {
145         *bp++ = 128 | (d & 127);
146         d = d >> 7;
147     }
148     *bp++ = d;
149     *dst = (char *) bp;
150 }
151
152 static CODEC_INLINE int iscz1_decode_int (unsigned char **src)
153 {
154     unsigned d = 0;
155     unsigned char c;
156     unsigned r = 0;
157
158     while (((c = *(*src)++) & 128))
159     {
160         d += ((c&127) << r);
161         r += 7;
162     }
163     d += (c << r);
164     return d;
165 }
166 #else
167 /* ! INT_CODEC_NEW */
168
169 static CODEC_INLINE void iscz1_encode_int (unsigned d, char **dst)
170 {
171     unsigned char *bp = (unsigned char*) *dst;
172
173     if (d <= 63)
174         *bp++ = d;
175     else if (d <= 16383)
176     {
177         *bp++ = 64 | (d>>8);
178        *bp++ = d & 255;
179     }
180     else if (d <= 4194303)
181     {
182         *bp++ = 128 | (d>>16);
183         *bp++ = (d>>8) & 255;
184         *bp++ = d & 255;
185     }
186     else
187     {
188         *bp++ = 192 | (d>>24);
189         *bp++ = (d>>16) & 255;
190         *bp++ = (d>>8) & 255;
191         *bp++ = d & 255;
192     }
193     *dst = (char *) bp;
194 }
195
196 static CODEC_INLINE int iscz1_decode_int (unsigned char **src)
197 {
198     unsigned c = *(*src)++;
199     switch (c & 192)
200     {
201     case 0:
202         return c;
203     case 64:
204         return ((c & 63) << 8) + *(*src)++;
205     case 128:
206         c = ((c & 63) << 8) + *(*src)++;
207         c = (c << 8) + *(*src)++;
208         return c;
209     }
210     if (c&32) /* expand sign bit to high bits */
211        c = ((c | 63) << 8) + *(*src)++;
212     else
213        c = ((c & 63) << 8) + *(*src)++;
214     c = (c << 8) + *(*src)++;
215     c = (c << 8) + *(*src)++;
216     
217     return c;
218 }
219 #endif
220
221 static void iscz1_code_item (int mode, void *vp, char **dst, char **src)
222 {
223     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
224     struct it_key tkey;
225     int d;
226
227     if (mode == ISAMC_ENCODE)
228     {
229         memcpy (&tkey, *src, sizeof(struct it_key));
230         d = tkey.sysno - p->key.sysno;
231         if (d)
232         {
233             iscz1_encode_int (2*tkey.seqno + 1, dst);
234             iscz1_encode_int (d, dst);
235             p->key.sysno += d;
236             p->key.seqno = tkey.seqno;
237         }
238         else
239         {
240             iscz1_encode_int (2*(tkey.seqno - p->key.seqno), dst);
241             p->key.seqno = tkey.seqno;
242         }
243         (*src) += sizeof(struct it_key);
244     }
245     else
246     {
247         d = iscz1_decode_int ((unsigned char **) src);
248         if (d & 1)
249         {
250             p->key.seqno = d>>1;
251             p->key.sysno += iscz1_decode_int ((unsigned char **) src);
252         }
253         else
254             p->key.seqno += d>>1;
255         memcpy (*dst, &p->key, sizeof(struct it_key));
256         (*dst) += sizeof(struct it_key);
257     }
258 }
259
260 ISAMS_M *key_isams_m (Res res, ISAMS_M *me)
261 {
262     isams_getmethod (me);
263
264     me->compare_item = key_compare;
265     me->log_item = key_logdump_txt;
266
267     me->code_start = iscz1_code_start;
268     me->code_item = iscz1_code_item;
269     me->code_stop = iscz1_code_stop;
270
271     me->debug = atoi(res_get_def (res, "isamsDebug", "0"));
272
273     return me;
274 }
275
276 ISAMC_M *key_isamc_m (Res res, ISAMC_M *me)
277 {
278     isc_getmethod (me);
279
280     me->compare_item = key_compare;
281     me->log_item = key_logdump_txt;
282
283     me->code_start = iscz1_code_start;
284     me->code_item = iscz1_code_item;
285     me->code_stop = iscz1_code_stop;
286     me->code_reset = iscz1_code_reset;
287
288     me->debug = atoi(res_get_def (res, "isamcDebug", "0"));
289
290     return me;
291 }
292
293 ISAMD_M *key_isamd_m (Res res, ISAMD_M *me)
294 {
295     me = isamd_getmethod (me);
296
297     me->compare_item = key_compare;
298     me->log_item = key_logdump_txt;
299
300     me->code_start = iscz1_code_start;
301     me->code_item = iscz1_code_item;
302     me->code_stop = iscz1_code_stop;
303     me->code_reset = iscz1_code_reset;
304
305     me->debug = atoi(res_get_def (res, "isamdDebug", "0"));
306
307     return me;
308 }
309
310 int key_SU_encode (int ch, char *out)
311 {
312     int i;
313     for (i = 0; ch; i++)
314     {
315         if (ch >= 64)
316             out[i] = 65 + (ch & 63);
317         else
318             out[i] = 1 + ch;
319         ch = ch >> 6;
320     }
321     return i;
322     /* in   out
323        0     1
324        1     2
325        63    64
326        64    65, 2
327        65    66, 2
328        127   128, 2
329        128   65, 3
330        191   128, 3
331        192   65, 4
332     */
333 }
334
335 int key_SU_decode (int *ch, const unsigned char *out)
336 {
337     int len = 1;
338     int fact = 1;
339     *ch = 0;
340     for (len = 1; *out >= 65; len++, out++)
341     {
342         *ch += (*out - 65) * fact;
343         fact <<= 6;
344     }
345     *ch += (*out - 1) * fact;
346     return len;
347 }
348