index/kcompare.c

   1 /* $Id: kcompare.c,v 1.55 2005-01-15 19:38:25 adam Exp $
   2    Copyright (C) 1995-2005
   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 #ifdef __GNUC__
  31 #define CODEC_INLINE inline
  32 #else
  33 #define CODEC_INLINE
  34 #endif
  35
  36 void key_logdump_txt (int logmask, const void *p, const char *txt)
  37 {
  38     struct it_key key;
  39     if (p)
  40     {
  41         char formstr[128];
  42         int i;
  43
  44         memcpy (&key, p, sizeof(key));
  45         assert(key.len > 0 && key.len <= IT_KEY_LEVEL_MAX);
  46         *formstr = '\0';
  47         for (i = 0; i<key.len; i++)
  48         {
  49             if (i)
  50                 strcat(formstr, ".");
  51             sprintf(formstr + strlen(formstr), ZINT_FORMAT, key.mem[i]);
  52         }
  53         yaz_log (logmask, "%s %s", formstr, txt);
  54     }
  55     else
  56         yaz_log(logmask, " (null) %s",txt);
  57 }
  58
  59 void key_logdump (int logmask, const void *p)
  60 {
  61     key_logdump_txt(logmask,  p, "");
  62 }
  63
  64 int key_compare_it (const void *p1, const void *p2)
  65 {
  66     int i, l = ((struct it_key *) p1)->len;
  67     if (((struct it_key *) p2)->len > l)
  68         l = ((struct it_key *) p2)->len;
  69     assert (l <= 4 && l > 0);
  70     for (i = 0; i < l; i++)
  71     {
  72         if (((struct it_key *) p1)->mem[i] != ((struct it_key *) p2)->mem[i])
  73         {
  74             if (((struct it_key *) p1)->mem[i] > ((struct it_key *) p2)->mem[i])
  75                 return l-i;
  76             else
  77                 return i-l;
  78         }
  79     }
  80     return 0;
  81 }
  82
  83 char *key_print_it (const void *p, char *buf)
  84 {
  85     strcpy(buf, "");
  86     return buf;
  87 }
  88
  89 int key_compare (const void *p1, const void *p2)
  90 {
  91     struct it_key i1, i2;
  92     int i, l;
  93     memcpy (&i1, p1, sizeof(i1));
  94     memcpy (&i2, p2, sizeof(i2));
  95     l = i1.len;
  96     if (i2.len > l)
  97         l = i2.len;
  98     assert (l <= 4 && l > 0);
  99     for (i = 0; i < l; i++)
 100     {
 101         if (i1.mem[i] != i2.mem[i])
 102         {
 103             if (i1.mem[i] > i2.mem[i])
 104                 return l-i;
 105             else
 106                 return i-l;
 107         }
 108     }
 109     return 0;
 110 }
 111
 112 zint key_get_seq(const void *p)
 113 {
 114     struct it_key k;
 115     memcpy (&k, p, sizeof(k));
 116     return k.mem[k.len-1];
 117 }
 118
 119 int key_qsort_compare (const void *p1, const void *p2)
 120 {
 121     int r;
 122     size_t l;
 123     char *cp1 = *(char **) p1;
 124     char *cp2 = *(char **) p2;
 125
 126     if ((r = strcmp (cp1, cp2)))
 127         return r;
 128     l = strlen(cp1)+1;
 129     if ((r = key_compare (cp1+l+1, cp2+l+1)))
 130         return r;
 131     return cp1[l] - cp2[l];
 132 }
 133
 134 struct iscz1_code_info {
 135     struct it_key key;
 136 };
 137
 138 void *iscz1_start (void)
 139 {
 140     struct iscz1_code_info *p = (struct iscz1_code_info *)
 141         xmalloc (sizeof(*p));
 142     iscz1_reset(p);
 143     return p;
 144 }
 145
 146 void key_init(struct it_key *key)
 147 {
 148     int i;
 149     key->len = 0;
 150     for (i = 0; i<IT_KEY_LEVEL_MAX; i++)
 151         key->mem[i] = 0;
 152 }
 153
 154 void iscz1_reset (void *vp)
 155 {
 156     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 157     int i;
 158     p->key.len = 0;
 159     for (i = 0; i< IT_KEY_LEVEL_MAX; i++)
 160         p->key.mem[i] = 0;
 161 }
 162
 163 void iscz1_stop (void *p)
 164 {
 165     xfree (p);
 166 }
 167
 168 /* small encoder that works with unsigneds of any length */
 169 static CODEC_INLINE void iscz1_encode_int (zint d, char **dst)
 170 {
 171     unsigned char *bp = (unsigned char*) *dst;
 172
 173     while (d > 127)
 174     {
 175         *bp++ = (unsigned) (128 | (d & 127));
 176         d = d >> 7;
 177     }
 178     *bp++ = (unsigned) d;
 179     *dst = (char *) bp;
 180 }
 181
 182 /* small decoder that works with unsigneds of any length */
 183 static CODEC_INLINE zint iscz1_decode_int (unsigned char **src)
 184 {
 185     zint d = 0;
 186     unsigned char c;
 187     unsigned r = 0;
 188
 189     while (((c = *(*src)++) & 128))
 190     {
 191         d += ((zint) (c&127) << r);
 192         r += 7;
 193     }
 194     d += ((zint) c << r);
 195     return d;
 196 }
 197
 198 void iscz1_encode (void *vp, char **dst, const char **src)
 199 {
 200     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 201     struct it_key tkey;
 202     zint d;
 203     int i;
 204
 205     /*   1
 206          3, 2, 9, 12
 207          3, 2, 10, 2
 208          4, 1
 209
 210          if diff is 0, then there is more ...
 211          if diff is non-zero, then _may_ be more
 212     */
 213     memcpy (&tkey, *src, sizeof(struct it_key));
 214
 215     /* deal with leader + delta encoding .. */
 216     d = 0;
 217     assert(tkey.len > 0 && tkey.len <= 4);
 218     for (i = 0; i < tkey.len; i++)
 219     {
 220         d = tkey.mem[i] - p->key.mem[i];
 221         if (d || i == tkey.len-1)
 222         {  /* all have been equal until now, now make delta .. */
 223             p->key.mem[i] = tkey.mem[i];
 224             if (d > 0)
 225             {
 226                 iscz1_encode_int (i + (tkey.len << 3) + 64, dst);
 227                 i++;
 228                 iscz1_encode_int (d, dst);
 229             }
 230             else
 231             {
 232                 iscz1_encode_int (i + (tkey.len << 3), dst);
 233                 }
 234             break;
 235         }
 236     }
 237     /* rest uses absolute encoding ... */
 238     for (; i < tkey.len; i++)
 239     {
 240         iscz1_encode_int (tkey.mem[i], dst);
 241         p->key.mem[i] = tkey.mem[i];
 242     }
 243     (*src) += sizeof(struct it_key);
 244 }
 245
 246 void iscz1_decode (void *vp, char **dst, const char **src)
 247 {
 248     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 249     int i;
 250
 251     int leader = (int) iscz1_decode_int ((unsigned char **) src);
 252     i = leader & 7;
 253     if (leader & 64)
 254         p->key.mem[i] += iscz1_decode_int ((unsigned char **) src);
 255     else
 256         p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
 257     p->key.len = (leader >> 3) & 7;
 258     while (++i < p->key.len)
 259         p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
 260     memcpy (*dst, &p->key, sizeof(struct it_key));
 261     (*dst) += sizeof(struct it_key);
 262 }
 263
 264 ISAMS_M *key_isams_m (Res res, ISAMS_M *me)
 265 {
 266     isams_getmethod (me);
 267
 268     me->compare_item = key_compare;
 269     me->log_item = key_logdump_txt;
 270
 271     me->codec.start = iscz1_start;
 272     me->codec.decode = iscz1_decode;
 273     me->codec.encode = iscz1_encode;
 274     me->codec.stop = iscz1_stop;
 275     me->codec.reset = iscz1_reset;
 276
 277     me->debug = atoi(res_get_def (res, "isamsDebug", "0"));
 278
 279     return me;
 280 }
 281
 282 ISAMC_M *key_isamc_m (Res res, ISAMC_M *me)
 283 {
 284     isc_getmethod (me);
 285
 286     me->compare_item = key_compare;
 287     me->log_item = key_logdump_txt;
 288
 289     me->codec.start = iscz1_start;
 290     me->codec.decode = iscz1_decode;
 291     me->codec.encode = iscz1_encode;
 292     me->codec.stop = iscz1_stop;
 293     me->codec.reset = iscz1_reset;
 294
 295     me->debug = atoi(res_get_def (res, "isamcDebug", "0"));
 296
 297     return me;
 298 }
 299
 300 int key_SU_encode (int ch, char *out)
 301 {
 302     int i;
 303     for (i = 0; ch; i++)
 304     {
 305         if (ch >= 64)
 306             out[i] = 65 + (ch & 63);
 307         else
 308             out[i] = 1 + ch;
 309         ch = ch >> 6;
 310     }
 311     return i;
 312     /* in   out
 313        0     1
 314        1     2
 315        63    64
 316        64    65, 2
 317        65    66, 2
 318        127   128, 2
 319        128   65, 3
 320        191   128, 3
 321        192   65, 4
 322     */
 323 }
 324
 325 int key_SU_decode (int *ch, const unsigned char *out)
 326 {
 327     int len = 1;
 328     int fact = 1;
 329     *ch = 0;
 330     for (len = 1; *out >= 65; len++, out++)
 331     {
 332         *ch += (*out - 65) * fact;
 333         fact <<= 6;
 334     }
 335     *ch += (*out - 1) * fact;
 336     return len;
 337 }
 338