index/kcompare.c

   1 /* $Id: kcompare.c,v 1.46 2004-06-09 13:11:49 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_get_seq(const void *p)
  98 {
  99     struct it_key k;
 100     memcpy (&k, p, sizeof(k));
 101     return k.seqno;
 102 }
 103
 104 int key_qsort_compare (const void *p1, const void *p2)
 105 {
 106     int r;
 107     size_t l;
 108     char *cp1 = *(char **) p1;
 109     char *cp2 = *(char **) p2;
 110
 111     if ((r = strcmp (cp1, cp2)))
 112         return r;
 113     l = strlen(cp1)+1;
 114     if ((r = key_compare (cp1+l+1, cp2+l+1)))
 115         return r;
 116     return cp1[l] - cp2[l];
 117 }
 118
 119 struct iscz1_code_info {
 120     struct it_key key;
 121 };
 122
 123 void *iscz1_code_start (int mode)
 124 {
 125     struct iscz1_code_info *p = (struct iscz1_code_info *)
 126         xmalloc (sizeof(*p));
 127     p->key.sysno = 0;
 128     p->key.seqno = 0;
 129     return p;
 130 }
 131
 132 void iscz1_code_reset (void *vp)
 133 {
 134     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 135     p->key.sysno = 0;
 136     p->key.seqno = 0;
 137 }
 138
 139 void iscz1_code_stop (int mode, void *p)
 140 {
 141     xfree (p);
 142 }
 143
 144 #if INT_CODEC_NEW
 145 static CODEC_INLINE void iscz1_encode_int (unsigned d, char **dst)
 146 {
 147     unsigned char *bp = (unsigned char*) *dst;
 148
 149     while (d > 127)
 150     {
 151         *bp++ = 128 | (d & 127);
 152         d = d >> 7;
 153     }
 154     *bp++ = d;
 155     *dst = (char *) bp;
 156 }
 157
 158 static CODEC_INLINE int iscz1_decode_int (unsigned char **src)
 159 {
 160     unsigned d = 0;
 161     unsigned char c;
 162     unsigned r = 0;
 163
 164     while (((c = *(*src)++) & 128))
 165     {
 166         d += ((c&127) << r);
 167         r += 7;
 168     }
 169     d += (c << r);
 170     return d;
 171 }
 172 #else
 173 /* ! INT_CODEC_NEW */
 174
 175 static CODEC_INLINE void iscz1_encode_int (unsigned d, char **dst)
 176 {
 177     unsigned char *bp = (unsigned char*) *dst;
 178
 179     if (d <= 63)
 180         *bp++ = d;
 181     else if (d <= 16383)
 182     {
 183         *bp++ = 64 | (d>>8);
 184        *bp++ = d & 255;
 185     }
 186     else if (d <= 4194303)
 187     {
 188         *bp++ = 128 | (d>>16);
 189         *bp++ = (d>>8) & 255;
 190         *bp++ = d & 255;
 191     }
 192     else
 193     {
 194         *bp++ = 192 | (d>>24);
 195         *bp++ = (d>>16) & 255;
 196         *bp++ = (d>>8) & 255;
 197         *bp++ = d & 255;
 198     }
 199     *dst = (char *) bp;
 200 }
 201
 202 static CODEC_INLINE int iscz1_decode_int (unsigned char **src)
 203 {
 204     unsigned c = *(*src)++;
 205     switch (c & 192)
 206     {
 207     case 0:
 208         return c;
 209     case 64:
 210         return ((c & 63) << 8) + *(*src)++;
 211     case 128:
 212         c = ((c & 63) << 8) + *(*src)++;
 213         c = (c << 8) + *(*src)++;
 214         return c;
 215     }
 216     if (c&32) /* expand sign bit to high bits */
 217        c = ((c | 63) << 8) + *(*src)++;
 218     else
 219        c = ((c & 63) << 8) + *(*src)++;
 220     c = (c << 8) + *(*src)++;
 221     c = (c << 8) + *(*src)++;
 222
 223     return c;
 224 }
 225 #endif
 226
 227 void iscz1_code_item (int mode, void *vp, char **dst, char **src)
 228 {
 229     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 230     struct it_key tkey;
 231     int d;
 232
 233     if (mode == ISAMC_ENCODE)
 234     {
 235         memcpy (&tkey, *src, sizeof(struct it_key));
 236         d = tkey.sysno - p->key.sysno;
 237         if (d)
 238         {
 239             iscz1_encode_int (2*tkey.seqno + 1, dst);
 240             iscz1_encode_int (d, dst);
 241             p->key.sysno += d;
 242             p->key.seqno = tkey.seqno;
 243         }
 244         else
 245         {
 246             iscz1_encode_int (2*(tkey.seqno - p->key.seqno), dst);
 247             p->key.seqno = tkey.seqno;
 248         }
 249         (*src) += sizeof(struct it_key);
 250     }
 251     else
 252     {
 253         d = iscz1_decode_int ((unsigned char **) src);
 254         if (d & 1)
 255         {
 256             p->key.seqno = d>>1;
 257             p->key.sysno += iscz1_decode_int ((unsigned char **) src);
 258         }
 259         else
 260             p->key.seqno += d>>1;
 261         memcpy (*dst, &p->key, sizeof(struct it_key));
 262         (*dst) += sizeof(struct it_key);
 263     }
 264 }
 265
 266 ISAMS_M *key_isams_m (Res res, ISAMS_M *me)
 267 {
 268     isams_getmethod (me);
 269
 270     me->compare_item = key_compare;
 271     me->log_item = key_logdump_txt;
 272
 273     me->code_start = iscz1_code_start;
 274     me->code_item = iscz1_code_item;
 275     me->code_stop = iscz1_code_stop;
 276
 277     me->debug = atoi(res_get_def (res, "isamsDebug", "0"));
 278
 279     return me;
 280 }
 281
 282 ISAMC_M *key_isamc_m (Res res, ISAMC_M *me)
 283 {
 284     isc_getmethod (me);
 285
 286     me->compare_item = key_compare;
 287     me->log_item = key_logdump_txt;
 288
 289     me->code_start = iscz1_code_start;
 290     me->code_item = iscz1_code_item;
 291     me->code_stop = iscz1_code_stop;
 292     me->code_reset = iscz1_code_reset;
 293
 294     me->debug = atoi(res_get_def (res, "isamcDebug", "0"));
 295
 296     return me;
 297 }
 298
 299 ISAMD_M *key_isamd_m (Res res, ISAMD_M *me)
 300 {
 301     me = isamd_getmethod (me);
 302
 303     me->compare_item = key_compare;
 304     me->log_item = key_logdump_txt;
 305
 306     me->code_start = iscz1_code_start;
 307     me->code_item = iscz1_code_item;
 308     me->code_stop = iscz1_code_stop;
 309     me->code_reset = iscz1_code_reset;
 310
 311     me->debug = atoi(res_get_def (res, "isamdDebug", "0"));
 312
 313     return me;
 314 }
 315
 316 int key_SU_encode (int ch, char *out)
 317 {
 318     int i;
 319     for (i = 0; ch; i++)
 320     {
 321         if (ch >= 64)
 322             out[i] = 65 + (ch & 63);
 323         else
 324             out[i] = 1 + ch;
 325         ch = ch >> 6;
 326     }
 327     return i;
 328     /* in   out
 329        0     1
 330        1     2
 331        63    64
 332        64    65, 2
 333        65    66, 2
 334        127   128, 2
 335        128   65, 3
 336        191   128, 3
 337        192   65, 4
 338     */
 339 }
 340
 341 int key_SU_decode (int *ch, const unsigned char *out)
 342 {
 343     int len = 1;
 344     int fact = 1;
 345     *ch = 0;
 346     for (len = 1; *out >= 65; len++, out++)
 347     {
 348         *ch += (*out - 65) * fact;
 349         fact <<= 6;
 350     }
 351     *ch += (*out - 1) * fact;
 352     return len;
 353 }
 354