util/it_key.c

   1 /* This file is part of the Zebra server.
   2    Copyright (C) 1994-2009 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 #include <stdlib.h>
  21 #include <string.h>
  22 #include <stdio.h>
  23 #include <assert.h>
  24
  25 #include <yaz/xmalloc.h>
  26 #include <it_key.h>
  27
  28 #ifdef __GNUC__
  29 #define CODEC_INLINE inline
  30 #else
  31 #define CODEC_INLINE
  32 #endif
  33
  34 void key_logdump_txt(int logmask, const void *p, const char *txt)
  35 {
  36     struct it_key key;
  37     if (!txt)
  38         txt = "(none)";
  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, " (no key) %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 <= IT_KEY_LEVEL_MAX && 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 <= IT_KEY_LEVEL_MAX && 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 zint key_get_segment(const void *p)
 120 {
 121     struct it_key k;
 122     memcpy (&k, p, sizeof(k));
 123     return k.mem[k.len-2];
 124 }
 125
 126 int key_qsort_compare (const void *p1, const void *p2)
 127 {
 128     int r;
 129     size_t l;
 130     char *cp1 = *(char **) p1;
 131     char *cp2 = *(char **) p2;
 132
 133     if ((r = strcmp (cp1, cp2)))
 134         return r;
 135     l = strlen(cp1)+1;
 136     if ((r = key_compare (cp1+l+1, cp2+l+1)))
 137         return r;
 138     return cp1[l] - cp2[l];
 139 }
 140
 141 struct iscz1_code_info {
 142     struct it_key key;
 143 };
 144
 145 void *iscz1_start (void)
 146 {
 147     struct iscz1_code_info *p = (struct iscz1_code_info *)
 148         xmalloc (sizeof(*p));
 149     iscz1_reset(p);
 150     return p;
 151 }
 152
 153 void key_init(struct it_key *key)
 154 {
 155     int i;
 156     key->len = 0;
 157     for (i = 0; i < IT_KEY_LEVEL_MAX; i++)
 158         key->mem[i] = 0;
 159 }
 160
 161 void iscz1_reset (void *vp)
 162 {
 163     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 164     int i;
 165     p->key.len = 0;
 166     for (i = 0; i < IT_KEY_LEVEL_MAX; i++)
 167         p->key.mem[i] = 0;
 168 }
 169
 170 void iscz1_stop (void *p)
 171 {
 172     xfree (p);
 173 }
 174
 175 /* small encoder that works with unsigneds of any length */
 176 static CODEC_INLINE void iscz1_encode_int (zint d, char **dst)
 177 {
 178     unsigned char *bp = (unsigned char*) *dst;
 179
 180     while (d > 127)
 181     {
 182         *bp++ = (unsigned) (128 | (d & 127));
 183         d = d >> 7;
 184     }
 185     *bp++ = (unsigned) d;
 186     *dst = (char *) bp;
 187 }
 188
 189 /* small decoder that works with unsigneds of any length */
 190 static CODEC_INLINE zint iscz1_decode_int (unsigned char **src)
 191 {
 192     zint d = 0;
 193     unsigned char c;
 194     unsigned r = 0;
 195
 196     while (((c = *(*src)++) & 128))
 197     {
 198         d += ((zint) (c&127) << r);
 199         r += 7;
 200     }
 201     d += ((zint) c << r);
 202     return d;
 203 }
 204
 205 void iscz1_encode (void *vp, char **dst, const char **src)
 206 {
 207     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 208     struct it_key tkey;
 209     zint d;
 210     int i;
 211
 212     /*   1
 213          3, 2, 9, 12
 214          3, 2, 10, 2
 215          4, 1
 216
 217          if diff is 0, then there is more ...
 218          if diff is non-zero, then _may_ be more
 219     */
 220     memcpy (&tkey, *src, sizeof(struct it_key));
 221
 222     /* deal with leader + delta encoding .. */
 223     d = 0;
 224     assert(tkey.len > 0 && tkey.len <= IT_KEY_LEVEL_MAX);
 225     for (i = 0; i < tkey.len; i++)
 226     {
 227         d = tkey.mem[i] - p->key.mem[i];
 228         if (d || i == tkey.len-1)
 229         {  /* all have been equal until now, now make delta .. */
 230             p->key.mem[i] = tkey.mem[i];
 231             if (d > 0)
 232             {
 233                 iscz1_encode_int (i + (tkey.len << 3) + 64, dst);
 234                 i++;
 235                 iscz1_encode_int (d, dst);
 236             }
 237             else
 238             {
 239                 iscz1_encode_int (i + (tkey.len << 3), dst);
 240                 }
 241             break;
 242         }
 243     }
 244     /* rest uses absolute encoding ... */
 245     for (; i < tkey.len; i++)
 246     {
 247         iscz1_encode_int (tkey.mem[i], dst);
 248         p->key.mem[i] = tkey.mem[i];
 249     }
 250     (*src) += sizeof(struct it_key);
 251 }
 252
 253 void iscz1_decode (void *vp, char **dst, const char **src)
 254 {
 255     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 256     int i;
 257
 258     int leader = (int) iscz1_decode_int ((unsigned char **) src);
 259     i = leader & 7;
 260     if (leader & 64)
 261         p->key.mem[i] += iscz1_decode_int ((unsigned char **) src);
 262     else
 263         p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
 264     p->key.len = (leader >> 3) & 7;
 265     while (++i < p->key.len)
 266         p->key.mem[i] = iscz1_decode_int ((unsigned char **) src);
 267     memcpy (*dst, &p->key, sizeof(struct it_key));
 268     (*dst) += sizeof(struct it_key);
 269 }
 270
 271 /*
 272  * Local variables:
 273  * c-basic-offset: 4
 274  * c-file-style: "Stroustrup"
 275  * indent-tabs-mode: nil
 276  * End:
 277  * vim: shiftwidth=4 tabstop=8 expandtab
 278  */
 279