index/kcompare.c

   1 /* $Id: kcompare.c,v 1.46.2.3 2006-08-14 10:38:58 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 this program; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20
  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 #ifdef __GNUC__
  32 #define CODEC_INLINE inline
  33 #else
  34 #define CODEC_INLINE
  35 #endif
  36
  37 void key_logdump_txt (int logmask, const void *p, const char *txt)
  38 {
  39     struct it_key key;
  40     if (p)
  41     {
  42         memcpy (&key, p, sizeof(key));
  43         logf (logmask, "%7d:%-4d %s", key.sysno, key.seqno,txt);
  44     }
  45     else
  46         logf(logmask, " (null) %s",txt);
  47 }
  48
  49 void key_logdump (int logmask, const void *p)
  50 {
  51     key_logdump_txt(logmask,p,"");
  52 }
  53
  54 int key_compare_it (const void *p1, const void *p2)
  55 {
  56     if (((struct it_key *) p1)->sysno != ((struct it_key *) p2)->sysno)
  57     {
  58         if (((struct it_key *) p1)->sysno > ((struct it_key *) p2)->sysno)
  59             return 2;
  60         else
  61             return -2;
  62     }
  63     if (((struct it_key *) p1)->seqno != ((struct it_key *) p2)->seqno)
  64     {
  65         if (((struct it_key *) p1)->seqno > ((struct it_key *) p2)->seqno)
  66             return 1;
  67         else
  68             return -1;
  69     }
  70     return 0;
  71 }
  72
  73 char *key_print_it (const void *p, char *buf)
  74 {
  75     const struct it_key *i = p;
  76     sprintf (buf, "%d:%d", i->sysno, i->seqno);
  77     return buf;
  78 }
  79
  80 int key_compare (const void *p1, const void *p2)
  81 {
  82     struct it_key i1, i2;
  83     memcpy (&i1, p1, sizeof(i1));
  84     memcpy (&i2, p2, sizeof(i2));
  85     if (i1.sysno != i2.sysno)
  86     {
  87         if (i1.sysno > i2.sysno)
  88             return 2;
  89         else
  90             return -2;
  91     }
  92     if (i1.seqno != i2.seqno)
  93     {
  94         if (i1.seqno > i2.seqno)
  95             return 1;
  96         else
  97             return -1;
  98     }
  99     return 0;
 100 }
 101
 102 int key_get_seq(const void *p)
 103 {
 104     struct it_key k;
 105     memcpy (&k, p, sizeof(k));
 106     return k.seqno;
 107 }
 108
 109 int key_qsort_compare (const void *p1, const void *p2)
 110 {
 111     int r;
 112     size_t l;
 113     char *cp1 = *(char **) p1;
 114     char *cp2 = *(char **) p2;
 115
 116     if ((r = strcmp (cp1, cp2)))
 117         return r;
 118     l = strlen(cp1)+1;
 119     if ((r = key_compare (cp1+l+1, cp2+l+1)))
 120         return r;
 121     return cp1[l] - cp2[l];
 122 }
 123
 124 struct iscz1_code_info {
 125     struct it_key key;
 126 };
 127
 128 void *iscz1_code_start (int mode)
 129 {
 130     struct iscz1_code_info *p = (struct iscz1_code_info *)
 131         xmalloc (sizeof(*p));
 132     p->key.sysno = 0;
 133     p->key.seqno = 0;
 134     return p;
 135 }
 136
 137 void iscz1_code_reset (void *vp)
 138 {
 139     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 140     p->key.sysno = 0;
 141     p->key.seqno = 0;
 142 }
 143
 144 void iscz1_code_stop (int mode, void *p)
 145 {
 146     xfree (p);
 147 }
 148
 149 #if INT_CODEC_NEW
 150 static CODEC_INLINE void iscz1_encode_int (unsigned d, char **dst)
 151 {
 152     unsigned char *bp = (unsigned char*) *dst;
 153
 154     while (d > 127)
 155     {
 156         *bp++ = 128 | (d & 127);
 157         d = d >> 7;
 158     }
 159     *bp++ = d;
 160     *dst = (char *) bp;
 161 }
 162
 163 static CODEC_INLINE int iscz1_decode_int (unsigned char **src)
 164 {
 165     unsigned d = 0;
 166     unsigned char c;
 167     unsigned r = 0;
 168
 169     while (((c = *(*src)++) & 128))
 170     {
 171         d += ((c&127) << r);
 172         r += 7;
 173     }
 174     d += (c << r);
 175     return d;
 176 }
 177 #else
 178 /* ! INT_CODEC_NEW */
 179
 180 static CODEC_INLINE void iscz1_encode_int (unsigned d, char **dst)
 181 {
 182     unsigned char *bp = (unsigned char*) *dst;
 183
 184     if (d <= 63)
 185         *bp++ = d;
 186     else if (d <= 16383)
 187     {
 188         *bp++ = 64 | (d>>8);
 189        *bp++ = d & 255;
 190     }
 191     else if (d <= 4194303)
 192     {
 193         *bp++ = 128 | (d>>16);
 194         *bp++ = (d>>8) & 255;
 195         *bp++ = d & 255;
 196     }
 197     else
 198     {
 199         *bp++ = 192 | (d>>24);
 200         *bp++ = (d>>16) & 255;
 201         *bp++ = (d>>8) & 255;
 202         *bp++ = d & 255;
 203     }
 204     *dst = (char *) bp;
 205 }
 206
 207 static CODEC_INLINE int iscz1_decode_int (unsigned char **src)
 208 {
 209     unsigned c = *(*src)++;
 210     switch (c & 192)
 211     {
 212     case 0:
 213         return c;
 214     case 64:
 215         return ((c & 63) << 8) + *(*src)++;
 216     case 128:
 217         c = ((c & 63) << 8) + *(*src)++;
 218         c = (c << 8) + *(*src)++;
 219         return c;
 220     }
 221     if (c&32) /* expand sign bit to high bits */
 222        c = ((c | 63) << 8) + *(*src)++;
 223     else
 224        c = ((c & 63) << 8) + *(*src)++;
 225     c = (c << 8) + *(*src)++;
 226     c = (c << 8) + *(*src)++;
 227
 228     return c;
 229 }
 230 #endif
 231
 232 void iscz1_code_item (int mode, void *vp, char **dst, char **src)
 233 {
 234     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 235     struct it_key tkey;
 236     int d;
 237
 238     if (mode == ISAMC_ENCODE)
 239     {
 240         memcpy (&tkey, *src, sizeof(struct it_key));
 241         d = tkey.sysno - p->key.sysno;
 242         if (d)
 243         {
 244             iscz1_encode_int (2*tkey.seqno + 1, dst);
 245             iscz1_encode_int (d, dst);
 246             p->key.sysno += d;
 247             p->key.seqno = tkey.seqno;
 248         }
 249         else
 250         {
 251             iscz1_encode_int (2*(tkey.seqno - p->key.seqno), dst);
 252             p->key.seqno = tkey.seqno;
 253         }
 254         (*src) += sizeof(struct it_key);
 255     }
 256     else
 257     {
 258         d = iscz1_decode_int ((unsigned char **) src);
 259         if (d & 1)
 260         {
 261             p->key.seqno = d>>1;
 262             p->key.sysno += iscz1_decode_int ((unsigned char **) src);
 263         }
 264         else
 265             p->key.seqno += d>>1;
 266         memcpy (*dst, &p->key, sizeof(struct it_key));
 267         (*dst) += sizeof(struct it_key);
 268     }
 269 }
 270
 271 ISAMS_M *key_isams_m (Res res, ISAMS_M *me)
 272 {
 273     isams_getmethod (me);
 274
 275     me->compare_item = key_compare;
 276     me->log_item = key_logdump_txt;
 277
 278     me->code_start = iscz1_code_start;
 279     me->code_item = iscz1_code_item;
 280     me->code_stop = iscz1_code_stop;
 281
 282     me->debug = atoi(res_get_def (res, "isamsDebug", "0"));
 283
 284     return me;
 285 }
 286
 287 ISAMC_M *key_isamc_m (Res res, ISAMC_M *me)
 288 {
 289     isc_getmethod (me);
 290
 291     me->compare_item = key_compare;
 292     me->log_item = key_logdump_txt;
 293
 294     me->code_start = iscz1_code_start;
 295     me->code_item = iscz1_code_item;
 296     me->code_stop = iscz1_code_stop;
 297     me->code_reset = iscz1_code_reset;
 298
 299     me->debug = atoi(res_get_def (res, "isamcDebug", "0"));
 300
 301     return me;
 302 }
 303
 304 ISAMD_M *key_isamd_m (Res res, ISAMD_M *me)
 305 {
 306     me = isamd_getmethod (me);
 307
 308     me->compare_item = key_compare;
 309     me->log_item = key_logdump_txt;
 310
 311     me->code_start = iscz1_code_start;
 312     me->code_item = iscz1_code_item;
 313     me->code_stop = iscz1_code_stop;
 314     me->code_reset = iscz1_code_reset;
 315
 316     me->debug = atoi(res_get_def (res, "isamdDebug", "0"));
 317
 318     return me;
 319 }
 320
 321 int key_SU_encode (int ch, char *out)
 322 {
 323     int i;
 324     for (i = 0; ch; i++)
 325     {
 326         if (ch >= 64)
 327             out[i] = 65 + (ch & 63);
 328         else
 329             out[i] = 1 + ch;
 330         ch = ch >> 6;
 331     }
 332     return i;
 333     /* in   out
 334        0     1
 335        1     2
 336        63    64
 337        64    65, 2
 338        65    66, 2
 339        127   128, 2
 340        128   65, 3
 341        191   128, 3
 342        192   65, 4
 343     */
 344 }
 345
 346 int key_SU_decode (int *ch, const unsigned char *out)
 347 {
 348     int len = 1;
 349     int fact = 1;
 350     *ch = 0;
 351     for (len = 1; *out >= 65; len++, out++)
 352     {
 353         *ch += (*out - 65) * fact;
 354         fact <<= 6;
 355     }
 356     *ch += (*out - 1) * fact;
 357     return len;
 358 }
 359