index/kcompare.c

   1 /* $Id: kcompare.c,v 1.57 2005-05-31 07:29:10 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 (!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 <= 4 && 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 <= 4 && 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 int key_qsort_compare (const void *p1, const void *p2)
 122 {
 123     int r;
 124     size_t l;
 125     char *cp1 = *(char **) p1;
 126     char *cp2 = *(char **) p2;
 127
 128     if ((r = strcmp (cp1, cp2)))
 129         return r;
 130     l = strlen(cp1)+1;
 131     if ((r = key_compare (cp1+l+1, cp2+l+1)))
 132         return r;
 133     return cp1[l] - cp2[l];
 134 }
 135
 136 struct iscz1_code_info {
 137     struct it_key key;
 138 };
 139
 140 void *iscz1_start (void)
 141 {
 142     struct iscz1_code_info *p = (struct iscz1_code_info *)
 143         xmalloc (sizeof(*p));
 144     iscz1_reset(p);
 145     return p;
 146 }
 147
 148 void key_init(struct it_key *key)
 149 {
 150     int i;
 151     key->len = 0;
 152     for (i = 0; i<IT_KEY_LEVEL_MAX; i++)
 153         key->mem[i] = 0;
 154 }
 155
 156 void iscz1_reset (void *vp)
 157 {
 158     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 159     int i;
 160     p->key.len = 0;
 161     for (i = 0; i< IT_KEY_LEVEL_MAX; i++)
 162         p->key.mem[i] = 0;
 163 }
 164
 165 void iscz1_stop (void *p)
 166 {
 167     xfree (p);
 168 }
 169
 170 /* small encoder that works with unsigneds of any length */
 171 static CODEC_INLINE void iscz1_encode_int (zint d, char **dst)
 172 {
 173     unsigned char *bp = (unsigned char*) *dst;
 174
 175     while (d > 127)
 176     {
 177         *bp++ = (unsigned) (128 | (d & 127));
 178         d = d >> 7;
 179     }
 180     *bp++ = (unsigned) d;
 181     *dst = (char *) bp;
 182 }
 183
 184 /* small decoder that works with unsigneds of any length */
 185 static CODEC_INLINE zint iscz1_decode_int (unsigned char **src)
 186 {
 187     zint d = 0;
 188     unsigned char c;
 189     unsigned r = 0;
 190
 191     while (((c = *(*src)++) & 128))
 192     {
 193         d += ((zint) (c&127) << r);
 194         r += 7;
 195     }
 196     d += ((zint) c << r);
 197     return d;
 198 }
 199
 200 void iscz1_encode (void *vp, char **dst, const char **src)
 201 {
 202     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 203     struct it_key tkey;
 204     zint d;
 205     int i;
 206
 207     /*   1
 208          3, 2, 9, 12
 209          3, 2, 10, 2
 210          4, 1
 211
 212          if diff is 0, then there is more ...
 213          if diff is non-zero, then _may_ be more
 214     */
 215     memcpy (&tkey, *src, sizeof(struct it_key));
 216
 217     /* deal with leader + delta encoding .. */
 218     d = 0;
 219     assert(tkey.len > 0 && tkey.len <= 4);
 220     for (i = 0; i < tkey.len; i++)
 221     {
 222         d = tkey.mem[i] - p->key.mem[i];
 223         if (d || i == tkey.len-1)
 224         {  /* all have been equal until now, now make delta .. */
 225             p->key.mem[i] = tkey.mem[i];
 226             if (d > 0)
 227             {
 228                 iscz1_encode_int (i + (tkey.len << 3) + 64, dst);
 229                 i++;
 230                 iscz1_encode_int (d, dst);
 231             }
 232             else
 233             {
 234                 iscz1_encode_int (i + (tkey.len << 3), dst);
 235                 }
 236             break;
 237         }
 238     }
 239     /* rest uses absolute encoding ... */
 240     for (; i < tkey.len; i++)
 241     {
 242         iscz1_encode_int (tkey.mem[i], dst);
 243         p->key.mem[i] = tkey.mem[i];
 244     }
 245     (*src) += sizeof(struct it_key);
 246 }
 247
 248 void iscz1_decode (void *vp, char **dst, const char **src)
 249 {
 250     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 251     int i;
 252
 253     int leader = (int) iscz1_decode_int ((unsigned char **) src);
 254     i = leader & 7;
 255     if (leader & 64)
 256         p->key.mem[i] += iscz1_decode_int ((unsigned char **) src);
 257     else
 258         p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
 259     p->key.len = (leader >> 3) & 7;
 260     while (++i < p->key.len)
 261         p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
 262     memcpy (*dst, &p->key, sizeof(struct it_key));
 263     (*dst) += sizeof(struct it_key);
 264 }
 265
 266 ISAMS_M *key_isams_m (Res res, ISAMS_M *me)
 267 {
 268     isams_getmethod (me);
 269
 270     me->compare_item = key_compare;
 271     me->log_item = key_logdump_txt;
 272
 273     me->codec.start = iscz1_start;
 274     me->codec.decode = iscz1_decode;
 275     me->codec.encode = iscz1_encode;
 276     me->codec.stop = iscz1_stop;
 277     me->codec.reset = iscz1_reset;
 278
 279     me->debug = atoi(res_get_def (res, "isamsDebug", "0"));
 280
 281     return me;
 282 }
 283
 284 ISAMC_M *key_isamc_m (Res res, ISAMC_M *me)
 285 {
 286     isamc_getmethod (me);
 287
 288     me->compare_item = key_compare;
 289     me->log_item = key_logdump_txt;
 290
 291     me->codec.start = iscz1_start;
 292     me->codec.decode = iscz1_decode;
 293     me->codec.encode = iscz1_encode;
 294     me->codec.stop = iscz1_stop;
 295     me->codec.reset = iscz1_reset;
 296
 297     me->debug = atoi(res_get_def (res, "isamcDebug", "0"));
 298
 299     return me;
 300 }
 301
 302 int key_SU_encode (int ch, char *out)
 303 {
 304     int i;
 305     for (i = 0; ch; i++)
 306     {
 307         if (ch >= 64)
 308             out[i] = 65 + (ch & 63);
 309         else
 310             out[i] = 1 + ch;
 311         ch = ch >> 6;
 312     }
 313     return i;
 314     /* in   out
 315        0     1
 316        1     2
 317        63    64
 318        64    65, 2
 319        65    66, 2
 320        127   128, 2
 321        128   65, 3
 322        191   128, 3
 323        192   65, 4
 324     */
 325 }
 326
 327 int key_SU_decode (int *ch, const unsigned char *out)
 328 {
 329     int len = 1;
 330     int fact = 1;
 331     *ch = 0;
 332     for (len = 1; *out >= 65; len++, out++)
 333     {
 334         *ch += (*out - 65) * fact;
 335         fact <<= 6;
 336     }
 337     *ch += (*out - 1) * fact;
 338     return len;
 339 }
 340