index/kcompare.c

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