util/it_key.c

   1 /* This file is part of the Zebra server.
   2    Copyright (C) 2004-2013 Index Data
   3
   4 Zebra is free software; you can redistribute it and/or modify it under
   5 the terms of the GNU General Public License as published by the Free
   6 Software Foundation; either version 2, or (at your option) any later
   7 version.
   8
   9 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12 for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; if not, write to the Free Software
  16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17
  18 */
  19
  20 #if HAVE_CONFIG_H
  21 #include <config.h>
  22 #endif
  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 char *key_print_it (const void *p, char *buf)
  68 {
  69     strcpy(buf, "");
  70     return buf;
  71 }
  72
  73 int key_compare (const void *p1, const void *p2)
  74 {
  75     struct it_key i1, i2;
  76     int i, l;
  77     memcpy (&i1, p1, sizeof(i1));
  78     memcpy (&i2, p2, sizeof(i2));
  79     l = i1.len;
  80     if (i2.len > l)
  81         l = i2.len;
  82     assert (l <= IT_KEY_LEVEL_MAX && l > 0);
  83     for (i = 0; i < l; i++)
  84     {
  85         if (i1.mem[i] != i2.mem[i])
  86         {
  87             if (i1.mem[i] > i2.mem[i])
  88                 return l-i;
  89             else
  90                 return i-l;
  91         }
  92     }
  93     return 0;
  94 }
  95
  96 zint key_get_seq(const void *p)
  97 {
  98     struct it_key k;
  99     memcpy (&k, p, sizeof(k));
 100     return k.mem[k.len-1];
 101 }
 102
 103 zint key_get_segment(const void *p)
 104 {
 105     struct it_key k;
 106     memcpy (&k, p, sizeof(k));
 107     return k.mem[k.len-2];
 108 }
 109
 110 int key_qsort_compare (const void *p1, const void *p2)
 111 {
 112     int r;
 113     size_t l;
 114     char *cp1 = *(char **) p1;
 115     char *cp2 = *(char **) p2;
 116
 117     if ((r = strcmp (cp1, cp2)))
 118         return r;
 119     l = strlen(cp1)+1;
 120     if ((r = key_compare (cp1+l+1, cp2+l+1)))
 121         return r;
 122     return cp1[l] - cp2[l];
 123 }
 124
 125 struct iscz1_code_info {
 126     struct it_key key;
 127 };
 128
 129 void *iscz1_start (void)
 130 {
 131     struct iscz1_code_info *p = (struct iscz1_code_info *)
 132         xmalloc (sizeof(*p));
 133     iscz1_reset(p);
 134     return p;
 135 }
 136
 137 void key_init(struct it_key *key)
 138 {
 139     int i;
 140     key->len = 0;
 141     for (i = 0; i < IT_KEY_LEVEL_MAX; i++)
 142         key->mem[i] = 0;
 143 }
 144
 145 void iscz1_reset (void *vp)
 146 {
 147     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 148     int i;
 149     p->key.len = 0;
 150     for (i = 0; i < IT_KEY_LEVEL_MAX; i++)
 151         p->key.mem[i] = 0;
 152 }
 153
 154 void iscz1_stop (void *p)
 155 {
 156     xfree (p);
 157 }
 158
 159 /* small encoder that works with unsigneds of any length */
 160 static CODEC_INLINE void iscz1_encode_int (zint d, char **dst)
 161 {
 162     unsigned char *bp = (unsigned char*) *dst;
 163
 164     while (d > 127)
 165     {
 166         *bp++ = (unsigned) (128 | (d & 127));
 167         d = d >> 7;
 168     }
 169     *bp++ = (unsigned) d;
 170     *dst = (char *) bp;
 171 }
 172
 173 /* small decoder that works with unsigneds of any length */
 174 static CODEC_INLINE zint iscz1_decode_int (unsigned char **src)
 175 {
 176     zint d = 0;
 177     unsigned char c;
 178     unsigned r = 0;
 179
 180     while (((c = *(*src)++) & 128))
 181     {
 182         d += ((zint) (c&127) << r);
 183         r += 7;
 184     }
 185     d += ((zint) c << r);
 186     return d;
 187 }
 188
 189 void iscz1_encode (void *vp, char **dst, const char **src)
 190 {
 191     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 192     struct it_key tkey;
 193     zint d;
 194     int i;
 195
 196     /*   1
 197          3, 2, 9, 12
 198          3, 2, 10, 2
 199          4, 1
 200
 201          if diff is 0, then there is more ...
 202          if diff is non-zero, then _may_ be more
 203     */
 204     memcpy (&tkey, *src, sizeof(struct it_key));
 205
 206     /* deal with leader + delta encoding .. */
 207     d = 0;
 208     assert(tkey.len > 0 && tkey.len <= IT_KEY_LEVEL_MAX);
 209     for (i = 0; i < tkey.len; i++)
 210     {
 211         d = tkey.mem[i] - p->key.mem[i];
 212         if (d || i == tkey.len-1)
 213         {  /* all have been equal until now, now make delta .. */
 214             p->key.mem[i] = tkey.mem[i];
 215             if (d > 0)
 216             {
 217                 iscz1_encode_int (i + (tkey.len << 3) + 64, dst);
 218                 i++;
 219                 iscz1_encode_int (d, dst);
 220             }
 221             else
 222             {
 223                 iscz1_encode_int (i + (tkey.len << 3), dst);
 224                 }
 225             break;
 226         }
 227     }
 228     /* rest uses absolute encoding ... */
 229     for (; i < tkey.len; i++)
 230     {
 231         iscz1_encode_int (tkey.mem[i], dst);
 232         p->key.mem[i] = tkey.mem[i];
 233     }
 234     (*src) += sizeof(struct it_key);
 235 }
 236
 237 void iscz1_decode (void *vp, char **dst, const char **src)
 238 {
 239     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 240     int i;
 241
 242     int leader = (int) iscz1_decode_int ((unsigned char **) src);
 243     i = leader & 7;
 244     if (leader & 64)
 245         p->key.mem[i] += iscz1_decode_int ((unsigned char **) src);
 246     else
 247         p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
 248     p->key.len = (leader >> 3) & 7;
 249     while (++i < p->key.len)
 250         p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
 251     memcpy (*dst, &p->key, sizeof(struct it_key));
 252     (*dst) += sizeof(struct it_key);
 253 }
 254
 255 /*
 256  * Local variables:
 257  * c-basic-offset: 4
 258  * c-file-style: "Stroustrup"
 259  * indent-tabs-mode: nil
 260  * End:
 261  * vim: shiftwidth=4 tabstop=8 expandtab
 262  */
 263