index/kcompare.c

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