util/it_key.c

   1 /* $Id: it_key.c,v 1.1 2006-11-21 14:32:38 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 <yaz/xmalloc.h>
  29 #include <it_key.h>
  30
  31 #ifdef __GNUC__
  32 #define CODEC_INLINE inline
  33 #else
  34 #define CODEC_INLINE
  35 #endif
  36
  37 void key_logdump_txt(int logmask, const void *p, const char *txt)
  38 {
  39     struct it_key key;
  40     if (!txt)
  41         txt = "(none)";
  42     if (p)
  43     {
  44         char formstr[128];
  45         int i;
  46
  47         memcpy (&key, p, sizeof(key));
  48         assert(key.len > 0 && key.len <= IT_KEY_LEVEL_MAX);
  49         *formstr = '\0';
  50         for (i = 0; i<key.len; i++)
  51         {
  52             if (i)
  53                 strcat(formstr, ".");
  54             sprintf(formstr + strlen(formstr), ZINT_FORMAT, key.mem[i]);
  55         }
  56         yaz_log(logmask, "%s %s", formstr, txt);
  57     }
  58     else
  59         yaz_log(logmask, " (no key) %s",txt);
  60 }
  61
  62 void key_logdump(int logmask, const void *p)
  63 {
  64     key_logdump_txt(logmask,  p, "");
  65 }
  66
  67 int key_compare_it (const void *p1, const void *p2)
  68 {
  69     int i, l = ((struct it_key *) p1)->len;
  70     if (((struct it_key *) p2)->len > l)
  71         l = ((struct it_key *) p2)->len;
  72     assert (l <= IT_KEY_LEVEL_MAX && l > 0);
  73     for (i = 0; i < l; i++)
  74     {
  75         if (((struct it_key *) p1)->mem[i] != ((struct it_key *) p2)->mem[i])
  76         {
  77             if (((struct it_key *) p1)->mem[i] > ((struct it_key *) p2)->mem[i])
  78                 return l-i;
  79             else
  80                 return i-l;
  81         }
  82     }
  83     return 0;
  84 }
  85
  86 char *key_print_it (const void *p, char *buf)
  87 {
  88     strcpy(buf, "");
  89     return buf;
  90 }
  91
  92 int key_compare (const void *p1, const void *p2)
  93 {
  94     struct it_key i1, i2;
  95     int i, l;
  96     memcpy (&i1, p1, sizeof(i1));
  97     memcpy (&i2, p2, sizeof(i2));
  98     l = i1.len;
  99     if (i2.len > l)
 100         l = i2.len;
 101     assert (l <= IT_KEY_LEVEL_MAX && l > 0);
 102     for (i = 0; i < l; i++)
 103     {
 104         if (i1.mem[i] != i2.mem[i])
 105         {
 106             if (i1.mem[i] > i2.mem[i])
 107                 return l-i;
 108             else
 109                 return i-l;
 110         }
 111     }
 112     return 0;
 113 }
 114
 115 zint key_get_seq(const void *p)
 116 {
 117     struct it_key k;
 118     memcpy (&k, p, sizeof(k));
 119     return k.mem[k.len-1];
 120 }
 121
 122 zint key_get_segment(const void *p)
 123 {
 124     struct it_key k;
 125     memcpy (&k, p, sizeof(k));
 126     return k.mem[k.len-2];
 127 }
 128
 129 int key_qsort_compare (const void *p1, const void *p2)
 130 {
 131     int r;
 132     size_t l;
 133     char *cp1 = *(char **) p1;
 134     char *cp2 = *(char **) p2;
 135
 136     if ((r = strcmp (cp1, cp2)))
 137         return r;
 138     l = strlen(cp1)+1;
 139     if ((r = key_compare (cp1+l+1, cp2+l+1)))
 140         return r;
 141     return cp1[l] - cp2[l];
 142 }
 143
 144 struct iscz1_code_info {
 145     struct it_key key;
 146 };
 147
 148 void *iscz1_start (void)
 149 {
 150     struct iscz1_code_info *p = (struct iscz1_code_info *)
 151         xmalloc (sizeof(*p));
 152     iscz1_reset(p);
 153     return p;
 154 }
 155
 156 void key_init(struct it_key *key)
 157 {
 158     int i;
 159     key->len = 0;
 160     for (i = 0; i < IT_KEY_LEVEL_MAX; i++)
 161         key->mem[i] = 0;
 162 }
 163
 164 void iscz1_reset (void *vp)
 165 {
 166     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 167     int i;
 168     p->key.len = 0;
 169     for (i = 0; i < IT_KEY_LEVEL_MAX; i++)
 170         p->key.mem[i] = 0;
 171 }
 172
 173 void iscz1_stop (void *p)
 174 {
 175     xfree (p);
 176 }
 177
 178 /* small encoder that works with unsigneds of any length */
 179 static CODEC_INLINE void iscz1_encode_int (zint d, char **dst)
 180 {
 181     unsigned char *bp = (unsigned char*) *dst;
 182
 183     while (d > 127)
 184     {
 185         *bp++ = (unsigned) (128 | (d & 127));
 186         d = d >> 7;
 187     }
 188     *bp++ = (unsigned) d;
 189     *dst = (char *) bp;
 190 }
 191
 192 /* small decoder that works with unsigneds of any length */
 193 static CODEC_INLINE zint iscz1_decode_int (unsigned char **src)
 194 {
 195     zint d = 0;
 196     unsigned char c;
 197     unsigned r = 0;
 198
 199     while (((c = *(*src)++) & 128))
 200     {
 201         d += ((zint) (c&127) << r);
 202         r += 7;
 203     }
 204     d += ((zint) c << r);
 205     return d;
 206 }
 207
 208 void iscz1_encode (void *vp, char **dst, const char **src)
 209 {
 210     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 211     struct it_key tkey;
 212     zint d;
 213     int i;
 214
 215     /*   1
 216          3, 2, 9, 12
 217          3, 2, 10, 2
 218          4, 1
 219
 220          if diff is 0, then there is more ...
 221          if diff is non-zero, then _may_ be more
 222     */
 223     memcpy (&tkey, *src, sizeof(struct it_key));
 224
 225     /* deal with leader + delta encoding .. */
 226     d = 0;
 227     assert(tkey.len > 0 && tkey.len <= IT_KEY_LEVEL_MAX);
 228     for (i = 0; i < tkey.len; i++)
 229     {
 230         d = tkey.mem[i] - p->key.mem[i];
 231         if (d || i == tkey.len-1)
 232         {  /* all have been equal until now, now make delta .. */
 233             p->key.mem[i] = tkey.mem[i];
 234             if (d > 0)
 235             {
 236                 iscz1_encode_int (i + (tkey.len << 3) + 64, dst);
 237                 i++;
 238                 iscz1_encode_int (d, dst);
 239             }
 240             else
 241             {
 242                 iscz1_encode_int (i + (tkey.len << 3), dst);
 243                 }
 244             break;
 245         }
 246     }
 247     /* rest uses absolute encoding ... */
 248     for (; i < tkey.len; i++)
 249     {
 250         iscz1_encode_int (tkey.mem[i], dst);
 251         p->key.mem[i] = tkey.mem[i];
 252     }
 253     (*src) += sizeof(struct it_key);
 254 }
 255
 256 void iscz1_decode (void *vp, char **dst, const char **src)
 257 {
 258     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 259     int i;
 260
 261     int leader = (int) iscz1_decode_int ((unsigned char **) src);
 262     i = leader & 7;
 263     if (leader & 64)
 264         p->key.mem[i] += iscz1_decode_int ((unsigned char **) src);
 265     else
 266         p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
 267     p->key.len = (leader >> 3) & 7;
 268     while (++i < p->key.len)
 269         p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
 270     memcpy (*dst, &p->key, sizeof(struct it_key));
 271     (*dst) += sizeof(struct it_key);
 272 }
 273
 274 /*
 275  * Local variables:
 276  * c-basic-offset: 4
 277  * indent-tabs-mode: nil
 278  * End:
 279  * vim: shiftwidth=4 tabstop=8 expandtab
 280  */
 281