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