index/kcompare.c

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