index/kcompare.c

   1 /* $Id: kcompare.c,v 1.47 2004-08-04 08:35:23 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 #if IT_KEY_NEW
  31 #define INT_CODEC_NEW 1
  32 #else
  33 #define INT_CODEC_NEW 0
  34 #endif
  35
  36 #define CODEC_INLINE inline
  37 void key_logdump_txt (int logmask, const void *p, const char *txt)
  38 {
  39     struct it_key key;
  40     if (p)
  41     {
  42 #if IT_KEY_NEW
  43         char formstr[128];
  44         int i;
  45
  46         memcpy (&key, p, sizeof(key));
  47         assert(key.len > 0 && key.len <= IT_KEY_LEVEL_MAX);
  48         *formstr = '\0';
  49         for (i = 0; i<key.len; i++)
  50         {
  51             sprintf(formstr + strlen(formstr), ZINT_FORMAT, key.mem[i]);
  52             if (i)
  53                 strcat(formstr, " ");
  54         }
  55         logf (logmask, "%s %s", formstr, txt);
  56 #else
  57 /* !IT_KEY_NEW */
  58         memcpy (&key, p, sizeof(key));
  59         logf (logmask, "%7d:%-4d %s", key.sysno, key.seqno, txt);
  60 #endif
  61     }
  62     else
  63         logf(logmask, " (null) %s",txt);
  64 }
  65
  66 void key_logdump (int logmask, const void *p)
  67 {
  68     key_logdump_txt(logmask,  p, "");
  69 }
  70
  71 int key_compare_it (const void *p1, const void *p2)
  72 {
  73 #if IT_KEY_NEW
  74     int i, l = ((struct it_key *) p1)->len;
  75     if (((struct it_key *) p2)->len > l)
  76         l = ((struct it_key *) p2)->len;
  77     assert (l <= 4 && l > 0);
  78     for (i = 0; i < l; i++)
  79     {
  80         if (((struct it_key *) p1)->mem[i] != ((struct it_key *) p2)->mem[i])
  81         {
  82             if (((struct it_key *) p1)->mem[i] > ((struct it_key *) p2)->mem[i])
  83                 return l-i;
  84             else
  85                 return i-l;
  86         }
  87     }
  88 #else
  89     if (((struct it_key *) p1)->sysno != ((struct it_key *) p2)->sysno)
  90     {
  91         if (((struct it_key *) p1)->sysno > ((struct it_key *) p2)->sysno)
  92             return 2;
  93         else
  94             return -2;
  95     }
  96     if (((struct it_key *) p1)->seqno != ((struct it_key *) p2)->seqno)
  97     {
  98         if (((struct it_key *) p1)->seqno > ((struct it_key *) p2)->seqno)
  99             return 1;
 100         else
 101             return -1;
 102     }
 103 #endif
 104     return 0;
 105 }
 106
 107 char *key_print_it (const void *p, char *buf)
 108 {
 109 #if IT_KEY_NEW
 110     strcpy(buf, "");
 111 #else
 112     const struct it_key *i = p;
 113     sprintf (buf, "%d:%d", i->sysno, i->seqno);
 114 #endif
 115     return buf;
 116 }
 117
 118 int key_compare (const void *p1, const void *p2)
 119 {
 120     struct it_key i1, i2;
 121     memcpy (&i1, p1, sizeof(i1));
 122     memcpy (&i2, p2, sizeof(i2));
 123 #if IT_KEY_NEW
 124     int i, l = i1.len;
 125     if (i2.len > l)
 126         l = i2.len;
 127     assert (l <= 4 && l > 0);
 128     for (i = 0; i < l; i++)
 129     {
 130         if (i1.mem[i] != i2.mem[i])
 131         {
 132             if (i1.mem[i] > i2.mem[i])
 133                 return l-i;
 134             else
 135                 return i-l;
 136         }
 137     }
 138 #else
 139     if (i1.sysno != i2.sysno)
 140     {
 141         if (i1.sysno > i2.sysno)
 142             return 2;
 143         else
 144             return -2;
 145     }
 146     if (i1.seqno != i2.seqno)
 147     {
 148         if (i1.seqno > i2.seqno)
 149             return 1;
 150         else
 151             return -1;
 152     }
 153 #endif
 154     return 0;
 155 }
 156
 157 int key_get_seq(const void *p)
 158 {
 159     struct it_key k;
 160     memcpy (&k, p, sizeof(k));
 161 #if IT_KEY_NEW
 162     return k.mem[k.len-1];
 163 #else
 164     return k.seqno;
 165 #endif
 166 }
 167
 168 int key_qsort_compare (const void *p1, const void *p2)
 169 {
 170     int r;
 171     size_t l;
 172     char *cp1 = *(char **) p1;
 173     char *cp2 = *(char **) p2;
 174
 175     if ((r = strcmp (cp1, cp2)))
 176         return r;
 177     l = strlen(cp1)+1;
 178     if ((r = key_compare (cp1+l+1, cp2+l+1)))
 179         return r;
 180     return cp1[l] - cp2[l];
 181 }
 182
 183 struct iscz1_code_info {
 184     struct it_key key;
 185 };
 186
 187 void *iscz1_start (void)
 188 {
 189     struct iscz1_code_info *p = (struct iscz1_code_info *)
 190         xmalloc (sizeof(*p));
 191     iscz1_reset(p);
 192     return p;
 193 }
 194
 195 #if IT_KEY_NEW
 196 void key_init(struct it_key *key)
 197 {
 198     int i;
 199     key->len = 0;
 200     for (i = 0; i<IT_KEY_LEVEL_MAX; i++)
 201         key->mem[i] = 0;
 202 }
 203 #endif
 204
 205 void iscz1_reset (void *vp)
 206 {
 207     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 208 #if IT_KEY_NEW
 209     int i;
 210     p->key.len = 0;
 211     for (i = 0; i< IT_KEY_LEVEL_MAX; i++)
 212         p->key.mem[i] = 0;
 213 #else
 214     p->key.sysno = 0;
 215     p->key.seqno = 0;
 216 #endif
 217 }
 218
 219 void iscz1_stop (void *p)
 220 {
 221     xfree (p);
 222 }
 223
 224 #if INT_CODEC_NEW
 225 /* small encoder that works with unsigneds of any length */
 226 static CODEC_INLINE void iscz1_encode_int (zint d, char **dst)
 227 {
 228     unsigned char *bp = (unsigned char*) *dst;
 229
 230     while (d > 127)
 231     {
 232         *bp++ = 128 | (d & 127);
 233         d = d >> 7;
 234     }
 235     *bp++ = d;
 236     *dst = (char *) bp;
 237 }
 238
 239 /* small decoder that works with unsigneds of any length */
 240 static CODEC_INLINE zint iscz1_decode_int (unsigned char **src)
 241 {
 242     zint d = 0;
 243     unsigned char c;
 244     unsigned r = 0;
 245
 246     while (((c = *(*src)++) & 128))
 247     {
 248         d += ((zint) (c&127) << r);
 249         r += 7;
 250     }
 251     d += ((zint) c << r);
 252     return d;
 253 }
 254 #else
 255 /* ! INT_CODEC_NEW */
 256
 257 /* old encoder that works with unsigneds up to 30 bits */
 258 static CODEC_INLINE void iscz1_encode_int (unsigned d, char **dst)
 259 {
 260     unsigned char *bp = (unsigned char*) *dst;
 261
 262     if (d <= 63)
 263         *bp++ = d;
 264     else if (d <= 16383)
 265     {
 266         *bp++ = 64 | (d>>8);
 267        *bp++ = d & 255;
 268     }
 269     else if (d <= 4194303)
 270     {
 271         *bp++ = 128 | (d>>16);
 272         *bp++ = (d>>8) & 255;
 273         *bp++ = d & 255;
 274     }
 275     else
 276     {
 277         *bp++ = 192 | (d>>24);
 278         *bp++ = (d>>16) & 255;
 279         *bp++ = (d>>8) & 255;
 280         *bp++ = d & 255;
 281     }
 282     *dst = (char *) bp;
 283 }
 284
 285 /* old decoder that works with unsigneds up to 30 bits */
 286 static CODEC_INLINE int iscz1_decode_int (unsigned char **src)
 287 {
 288     unsigned c = *(*src)++;
 289     switch (c & 192)
 290     {
 291     case 0:
 292         return c;
 293     case 64:
 294         return ((c & 63) << 8) + *(*src)++;
 295     case 128:
 296         c = ((c & 63) << 8) + *(*src)++;
 297         c = (c << 8) + *(*src)++;
 298         return c;
 299     }
 300     if (c&32) /* expand sign bit to high bits */
 301        c = ((c | 63) << 8) + *(*src)++;
 302     else
 303        c = ((c & 63) << 8) + *(*src)++;
 304     c = (c << 8) + *(*src)++;
 305     c = (c << 8) + *(*src)++;
 306
 307     return c;
 308 }
 309 #endif
 310
 311 void iscz1_encode (void *vp, char **dst, const char **src)
 312 {
 313     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 314     struct it_key tkey;
 315 #if IT_KEY_NEW
 316     zint d;
 317     int i;
 318 #else
 319     int d;
 320 #endif
 321
 322     /*   1
 323          3, 2, 9, 12
 324          3, 2, 10, 2
 325          4, 1
 326
 327          if diff is 0, then there is more ...
 328          if diff is non-zero, then _may_ be more
 329     */
 330     memcpy (&tkey, *src, sizeof(struct it_key));
 331 #if IT_KEY_NEW
 332     /* deal with leader + delta encoding .. */
 333     d = 0;
 334     assert(tkey.len > 0 && tkey.len <= 4);
 335     for (i = 0; i < tkey.len; i++)
 336     {
 337         d = tkey.mem[i] - p->key.mem[i];
 338         if (d || i == tkey.len-1)
 339         {  /* all have been equal until now, now make delta .. */
 340             p->key.mem[i] = tkey.mem[i];
 341             if (d > 0)
 342             {
 343                 iscz1_encode_int (i + (tkey.len << 3) + 64, dst);
 344                 i++;
 345                 iscz1_encode_int (d, dst);
 346             }
 347             else
 348             {
 349                 iscz1_encode_int (i + (tkey.len << 3), dst);
 350                 }
 351             break;
 352         }
 353     }
 354     /* rest uses absolute encoding ... */
 355     for (; i < tkey.len; i++)
 356     {
 357         iscz1_encode_int (tkey.mem[i], dst);
 358         p->key.mem[i] = tkey.mem[i];
 359     }
 360     (*src) += sizeof(struct it_key);
 361 #else
 362     d = tkey.sysno - p->key.sysno;
 363     if (d)
 364     {
 365         iscz1_encode_int (2*tkey.seqno + 1, dst);
 366         iscz1_encode_int (d, dst);
 367         p->key.sysno += d;
 368         p->key.seqno = tkey.seqno;
 369     }
 370     else
 371     {
 372         iscz1_encode_int (2*(tkey.seqno - p->key.seqno), dst);
 373         p->key.seqno = tkey.seqno;
 374     }
 375     (*src) += sizeof(struct it_key);
 376 #endif
 377 }
 378
 379 void iscz1_decode (void *vp, char **dst, const char **src)
 380 {
 381     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 382 #if IT_KEY_NEW
 383     int i;
 384 #else
 385     int d;
 386 #endif
 387
 388 #if IT_KEY_NEW
 389     int leader = iscz1_decode_int ((unsigned char **) src);
 390     i = leader & 7;
 391     if (leader & 64)
 392         p->key.mem[i] += iscz1_decode_int ((unsigned char **) src);
 393     else
 394         p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
 395     p->key.len = (leader >> 3) & 7;
 396     while (++i < p->key.len)
 397         p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
 398     memcpy (*dst, &p->key, sizeof(struct it_key));
 399     (*dst) += sizeof(struct it_key);
 400 #else
 401     d = iscz1_decode_int ((unsigned char **) src);
 402     if (d & 1)
 403     {
 404         p->key.seqno = d>>1;
 405         p->key.sysno += iscz1_decode_int ((unsigned char **) src);
 406     }
 407     else
 408         p->key.seqno += d>>1;
 409     memcpy (*dst, &p->key, sizeof(struct it_key));
 410     (*dst) += sizeof(struct it_key);
 411 #endif
 412 }
 413
 414 ISAMS_M *key_isams_m (Res res, ISAMS_M *me)
 415 {
 416     isams_getmethod (me);
 417
 418     me->compare_item = key_compare;
 419     me->log_item = key_logdump_txt;
 420
 421     me->codec.start = iscz1_start;
 422     me->codec.decode = iscz1_decode;
 423     me->codec.encode = iscz1_encode;
 424     me->codec.stop = iscz1_stop;
 425     me->codec.reset = iscz1_reset;
 426
 427     me->debug = atoi(res_get_def (res, "isamsDebug", "0"));
 428
 429     return me;
 430 }
 431
 432 ISAMC_M *key_isamc_m (Res res, ISAMC_M *me)
 433 {
 434     isc_getmethod (me);
 435
 436     me->compare_item = key_compare;
 437     me->log_item = key_logdump_txt;
 438
 439     me->codec.start = iscz1_start;
 440     me->codec.decode = iscz1_decode;
 441     me->codec.encode = iscz1_encode;
 442     me->codec.stop = iscz1_stop;
 443     me->codec.reset = iscz1_reset;
 444
 445     me->debug = atoi(res_get_def (res, "isamcDebug", "0"));
 446
 447     return me;
 448 }
 449
 450 int key_SU_encode (int ch, char *out)
 451 {
 452     int i;
 453     for (i = 0; ch; i++)
 454     {
 455         if (ch >= 64)
 456             out[i] = 65 + (ch & 63);
 457         else
 458             out[i] = 1 + ch;
 459         ch = ch >> 6;
 460     }
 461     return i;
 462     /* in   out
 463        0     1
 464        1     2
 465        63    64
 466        64    65, 2
 467        65    66, 2
 468        127   128, 2
 469        128   65, 3
 470        191   128, 3
 471        192   65, 4
 472     */
 473 }
 474
 475 int key_SU_decode (int *ch, const unsigned char *out)
 476 {
 477     int len = 1;
 478     int fact = 1;
 479     *ch = 0;
 480     for (len = 1; *out >= 65; len++, out++)
 481     {
 482         *ch += (*out - 65) * fact;
 483         fact <<= 6;
 484     }
 485     *ch += (*out - 1) * fact;
 486     return len;
 487 }
 488