1 /* $Id: kcompare.c,v 1.50 2004-08-06 12:28:22 adam Exp $
2 Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004
5 This file is part of the Zebra server.
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
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
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
31 #define INT_CODEC_NEW 1
33 #define INT_CODEC_NEW 0
37 #define CODEC_INLINE inline
42 void key_logdump_txt (int logmask, const void *p, const char *txt)
51 memcpy (&key, p, sizeof(key));
52 assert(key.len > 0 && key.len <= IT_KEY_LEVEL_MAX);
54 for (i = 0; i<key.len; i++)
56 sprintf(formstr + strlen(formstr), ZINT_FORMAT, key.mem[i]);
60 logf (logmask, "%s %s", formstr, txt);
63 memcpy (&key, p, sizeof(key));
64 logf (logmask, "%7d:%-4d %s", key.sysno, key.seqno, txt);
68 logf(logmask, " (null) %s",txt);
71 void key_logdump (int logmask, const void *p)
73 key_logdump_txt(logmask, p, "");
76 int key_compare_it (const void *p1, const void *p2)
79 int i, l = ((struct it_key *) p1)->len;
80 if (((struct it_key *) p2)->len > l)
81 l = ((struct it_key *) p2)->len;
82 assert (l <= 4 && l > 0);
83 for (i = 0; i < l; i++)
85 if (((struct it_key *) p1)->mem[i] != ((struct it_key *) p2)->mem[i])
87 if (((struct it_key *) p1)->mem[i] > ((struct it_key *) p2)->mem[i])
94 if (((struct it_key *) p1)->sysno != ((struct it_key *) p2)->sysno)
96 if (((struct it_key *) p1)->sysno > ((struct it_key *) p2)->sysno)
101 if (((struct it_key *) p1)->seqno != ((struct it_key *) p2)->seqno)
103 if (((struct it_key *) p1)->seqno > ((struct it_key *) p2)->seqno)
112 char *key_print_it (const void *p, char *buf)
117 const struct it_key *i = p;
118 sprintf (buf, "%d:%d", i->sysno, i->seqno);
123 int key_compare (const void *p1, const void *p2)
125 struct it_key i1, i2;
129 memcpy (&i1, p1, sizeof(i1));
130 memcpy (&i2, p2, sizeof(i2));
135 assert (l <= 4 && l > 0);
136 for (i = 0; i < l; i++)
138 if (i1.mem[i] != i2.mem[i])
140 if (i1.mem[i] > i2.mem[i])
147 if (i1.sysno != i2.sysno)
149 if (i1.sysno > i2.sysno)
154 if (i1.seqno != i2.seqno)
156 if (i1.seqno > i2.seqno)
165 int key_get_seq(const void *p)
168 memcpy (&k, p, sizeof(k));
170 return (int) k.mem[k.len-1];
176 int key_qsort_compare (const void *p1, const void *p2)
180 char *cp1 = *(char **) p1;
181 char *cp2 = *(char **) p2;
183 if ((r = strcmp (cp1, cp2)))
186 if ((r = key_compare (cp1+l+1, cp2+l+1)))
188 return cp1[l] - cp2[l];
191 struct iscz1_code_info {
195 void *iscz1_start (void)
197 struct iscz1_code_info *p = (struct iscz1_code_info *)
198 xmalloc (sizeof(*p));
204 void key_init(struct it_key *key)
208 for (i = 0; i<IT_KEY_LEVEL_MAX; i++)
213 void iscz1_reset (void *vp)
215 struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
219 for (i = 0; i< IT_KEY_LEVEL_MAX; i++)
227 void iscz1_stop (void *p)
233 /* small encoder that works with unsigneds of any length */
234 static CODEC_INLINE void iscz1_encode_int (zint d, char **dst)
236 unsigned char *bp = (unsigned char*) *dst;
240 *bp++ = (unsigned) (128 | (d & 127));
243 *bp++ = (unsigned) d;
247 /* small decoder that works with unsigneds of any length */
248 static CODEC_INLINE zint iscz1_decode_int (unsigned char **src)
254 while (((c = *(*src)++) & 128))
256 d += ((zint) (c&127) << r);
259 d += ((zint) c << r);
263 /* ! INT_CODEC_NEW */
265 /* old encoder that works with unsigneds up to 30 bits */
266 static CODEC_INLINE void iscz1_encode_int (unsigned d, char **dst)
268 unsigned char *bp = (unsigned char*) *dst;
277 else if (d <= 4194303)
279 *bp++ = 128 | (d>>16);
280 *bp++ = (d>>8) & 255;
285 *bp++ = 192 | (d>>24);
286 *bp++ = (d>>16) & 255;
287 *bp++ = (d>>8) & 255;
293 /* old decoder that works with unsigneds up to 30 bits */
294 static CODEC_INLINE int iscz1_decode_int (unsigned char **src)
296 unsigned c = *(*src)++;
302 return ((c & 63) << 8) + *(*src)++;
304 c = ((c & 63) << 8) + *(*src)++;
305 c = (c << 8) + *(*src)++;
308 if (c&32) /* expand sign bit to high bits */
309 c = ((c | 63) << 8) + *(*src)++;
311 c = ((c & 63) << 8) + *(*src)++;
312 c = (c << 8) + *(*src)++;
313 c = (c << 8) + *(*src)++;
319 void iscz1_encode (void *vp, char **dst, const char **src)
321 struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
335 if diff is 0, then there is more ...
336 if diff is non-zero, then _may_ be more
338 memcpy (&tkey, *src, sizeof(struct it_key));
340 /* deal with leader + delta encoding .. */
342 assert(tkey.len > 0 && tkey.len <= 4);
343 for (i = 0; i < tkey.len; i++)
345 d = tkey.mem[i] - p->key.mem[i];
346 if (d || i == tkey.len-1)
347 { /* all have been equal until now, now make delta .. */
348 p->key.mem[i] = tkey.mem[i];
351 iscz1_encode_int (i + (tkey.len << 3) + 64, dst);
353 iscz1_encode_int (d, dst);
357 iscz1_encode_int (i + (tkey.len << 3), dst);
362 /* rest uses absolute encoding ... */
363 for (; i < tkey.len; i++)
365 iscz1_encode_int (tkey.mem[i], dst);
366 p->key.mem[i] = tkey.mem[i];
368 (*src) += sizeof(struct it_key);
370 d = tkey.sysno - p->key.sysno;
373 iscz1_encode_int (2*tkey.seqno + 1, dst);
374 iscz1_encode_int (d, dst);
376 p->key.seqno = tkey.seqno;
380 iscz1_encode_int (2*(tkey.seqno - p->key.seqno), dst);
381 p->key.seqno = tkey.seqno;
383 (*src) += sizeof(struct it_key);
387 void iscz1_decode (void *vp, char **dst, const char **src)
389 struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
397 int leader = (int) iscz1_decode_int ((unsigned char **) src);
400 p->key.mem[i] += iscz1_decode_int ((unsigned char **) src);
402 p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
403 p->key.len = (leader >> 3) & 7;
404 while (++i < p->key.len)
405 p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
406 memcpy (*dst, &p->key, sizeof(struct it_key));
407 (*dst) += sizeof(struct it_key);
409 d = iscz1_decode_int ((unsigned char **) src);
413 p->key.sysno += iscz1_decode_int ((unsigned char **) src);
416 p->key.seqno += d>>1;
417 memcpy (*dst, &p->key, sizeof(struct it_key));
418 (*dst) += sizeof(struct it_key);
422 ISAMS_M *key_isams_m (Res res, ISAMS_M *me)
424 isams_getmethod (me);
426 me->compare_item = key_compare;
427 me->log_item = key_logdump_txt;
429 me->codec.start = iscz1_start;
430 me->codec.decode = iscz1_decode;
431 me->codec.encode = iscz1_encode;
432 me->codec.stop = iscz1_stop;
433 me->codec.reset = iscz1_reset;
435 me->debug = atoi(res_get_def (res, "isamsDebug", "0"));
440 ISAMC_M *key_isamc_m (Res res, ISAMC_M *me)
444 me->compare_item = key_compare;
445 me->log_item = key_logdump_txt;
447 me->codec.start = iscz1_start;
448 me->codec.decode = iscz1_decode;
449 me->codec.encode = iscz1_encode;
450 me->codec.stop = iscz1_stop;
451 me->codec.reset = iscz1_reset;
453 me->debug = atoi(res_get_def (res, "isamcDebug", "0"));
458 int key_SU_encode (int ch, char *out)
464 out[i] = 65 + (ch & 63);
483 int key_SU_decode (int *ch, const unsigned char *out)
488 for (len = 1; *out >= 65; len++, out++)
490 *ch += (*out - 65) * fact;
493 *ch += (*out - 1) * fact;