index/kcompare.c

   1 /* $Id: kcompare.c,v 1.42 2004-05-30 18:35:12 adam Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004
   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 #define INT_CODEC_NEW 0
  31
  32 #define CODEC_INLINE inline
  33
  34 void key_logdump (int logmask, const void *p)
  35 {
  36     struct it_key key;
  37
  38     memcpy (&key, p, sizeof(key));
  39     logf (logmask, "%7d s=%-4d", key.sysno, key.seqno);
  40 }
  41
  42 int key_compare_it (const void *p1, const void *p2)
  43 {
  44     if (((struct it_key *) p1)->sysno != ((struct it_key *) p2)->sysno)
  45     {
  46         if (((struct it_key *) p1)->sysno > ((struct it_key *) p2)->sysno)
  47             return 2;
  48         else
  49             return -2;
  50     }
  51     if (((struct it_key *) p1)->seqno != ((struct it_key *) p2)->seqno)
  52     {
  53         if (((struct it_key *) p1)->seqno > ((struct it_key *) p2)->seqno)
  54             return 1;
  55         else
  56             return -1;
  57     }
  58     return 0;
  59 }
  60
  61 char *key_print_it (const void *p, char *buf)
  62 {
  63     const struct it_key *i = p;
  64     sprintf (buf, "%d:%d", i->sysno, i->seqno);
  65     return buf;
  66 }
  67
  68 int key_compare (const void *p1, const void *p2)
  69 {
  70     struct it_key i1, i2;
  71     memcpy (&i1, p1, sizeof(i1));
  72     memcpy (&i2, p2, sizeof(i2));
  73     if (i1.sysno != i2.sysno)
  74     {
  75         if (i1.sysno > i2.sysno)
  76             return 2;
  77         else
  78             return -2;
  79     }
  80     if (i1.seqno != i2.seqno)
  81     {
  82         if (i1.seqno > i2.seqno)
  83             return 1;
  84         else
  85             return -1;
  86     }
  87     return 0;
  88 }
  89
  90 int key_qsort_compare (const void *p1, const void *p2)
  91 {
  92     int r;
  93     size_t l;
  94     char *cp1 = *(char **) p1;
  95     char *cp2 = *(char **) p2;
  96
  97     if ((r = strcmp (cp1, cp2)))
  98         return r;
  99     l = strlen(cp1)+1;
 100     if ((r = key_compare (cp1+l+1, cp2+l+1)))
 101         return r;
 102     return cp1[l] - cp2[l];
 103 }
 104
 105 struct iscz1_code_info {
 106     struct it_key key;
 107 };
 108
 109
 110 static void *iscz1_code_start (int mode)
 111 {
 112     struct iscz1_code_info *p = (struct iscz1_code_info *)
 113         xmalloc (sizeof(*p));
 114     p->key.sysno = 0;
 115     p->key.seqno = 0;
 116     return p;
 117 }
 118
 119 static void iscz1_code_reset (void *vp)
 120 {
 121     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 122     p->key.sysno = 0;
 123     p->key.seqno = 0;
 124 }
 125
 126 static void iscz1_code_stop (int mode, void *p)
 127 {
 128     xfree (p);
 129 }
 130
 131 #if INT_CODEC_NEW
 132 CODEC_INLINE void iscz1_encode_int (unsigned d, char **dst)
 133 {
 134     unsigned char *bp = (unsigned char*) *dst;
 135
 136     while (d > 127)
 137     {
 138         *bp++ = 128 | (d & 127);
 139         d = d >> 7;
 140     }
 141     *bp++ = d;
 142     *dst = (char *) bp;
 143 }
 144
 145 CODEC_INLINE int iscz1_decode_int (unsigned char **src)
 146 {
 147     unsigned d = 0;
 148     unsigned char c;
 149     unsigned r = 0;
 150
 151     while (((c = *(*src)++) & 128))
 152     {
 153         d += ((c&127) << r);
 154         r += 7;
 155     }
 156     d += (c << r);
 157     return d;
 158 }
 159 #else
 160 /* ! INT_CODEC_NEW */
 161
 162 CODEC_INLINE void iscz1_encode_int (unsigned d, char **dst)
 163 {
 164     unsigned char *bp = (unsigned char*) *dst;
 165
 166     if (d <= 63)
 167         *bp++ = d;
 168     else if (d <= 16383)
 169     {
 170         *bp++ = 64 | (d>>8);
 171        *bp++ = d & 255;
 172     }
 173     else if (d <= 4194303)
 174     {
 175         *bp++ = 128 | (d>>16);
 176         *bp++ = (d>>8) & 255;
 177         *bp++ = d & 255;
 178     }
 179     else
 180     {
 181         *bp++ = 192 | (d>>24);
 182         *bp++ = (d>>16) & 255;
 183         *bp++ = (d>>8) & 255;
 184         *bp++ = d & 255;
 185     }
 186     *dst = (char *) bp;
 187 }
 188
 189 CODEC_INLINE int iscz1_decode_int (unsigned char **src)
 190 {
 191     unsigned c = *(*src)++;
 192     switch (c & 192)
 193     {
 194     case 0:
 195         return c;
 196     case 64:
 197         return ((c & 63) << 8) + *(*src)++;
 198     case 128:
 199         c = ((c & 63) << 8) + *(*src)++;
 200         c = (c << 8) + *(*src)++;
 201         return c;
 202     }
 203     if (c&32) /* expand sign bit to high bits */
 204        c = ((c | 63) << 8) + *(*src)++;
 205     else
 206        c = ((c & 63) << 8) + *(*src)++;
 207     c = (c << 8) + *(*src)++;
 208     c = (c << 8) + *(*src)++;
 209
 210     return c;
 211 }
 212 #endif
 213
 214 static void iscz1_code_item (int mode, void *vp, char **dst, char **src)
 215 {
 216     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 217     struct it_key tkey;
 218     int d;
 219
 220     if (mode == ISAMC_ENCODE)
 221     {
 222         memcpy (&tkey, *src, sizeof(struct it_key));
 223         d = tkey.sysno - p->key.sysno;
 224         if (d)
 225         {
 226             iscz1_encode_int (2*tkey.seqno + 1, dst);
 227             iscz1_encode_int (d, dst);
 228             p->key.sysno += d;
 229             p->key.seqno = tkey.seqno;
 230         }
 231         else
 232         {
 233             iscz1_encode_int (2*(tkey.seqno - p->key.seqno), dst);
 234             p->key.seqno = tkey.seqno;
 235         }
 236         (*src) += sizeof(struct it_key);
 237     }
 238     else
 239     {
 240         d = iscz1_decode_int ((unsigned char **) src);
 241         if (d & 1)
 242         {
 243             p->key.seqno = d>>1;
 244             p->key.sysno += iscz1_decode_int ((unsigned char **) src);
 245         }
 246         else
 247             p->key.seqno += d>>1;
 248         memcpy (*dst, &p->key, sizeof(struct it_key));
 249         (*dst) += sizeof(struct it_key);
 250     }
 251 }
 252
 253 ISAMS_M *key_isams_m (Res res, ISAMS_M *me)
 254 {
 255     isams_getmethod (me);
 256
 257     me->compare_item = key_compare;
 258
 259     me->code_start = iscz1_code_start;
 260     me->code_item = iscz1_code_item;
 261     me->code_stop = iscz1_code_stop;
 262
 263     me->debug = atoi(res_get_def (res, "isamsDebug", "0"));
 264
 265     return me;
 266 }
 267
 268 ISAMC_M *key_isamc_m (Res res, ISAMC_M *me)
 269 {
 270     isc_getmethod (me);
 271
 272     me->compare_item = key_compare;
 273
 274     me->code_start = iscz1_code_start;
 275     me->code_item = iscz1_code_item;
 276     me->code_stop = iscz1_code_stop;
 277     me->code_reset = iscz1_code_reset;
 278
 279     me->debug = atoi(res_get_def (res, "isamcDebug", "0"));
 280
 281     return me;
 282 }
 283
 284 ISAMD_M *key_isamd_m (Res res, ISAMD_M *me)
 285 {
 286     me = isamd_getmethod (me);
 287
 288     me->compare_item = key_compare;
 289
 290     me->code_start = iscz1_code_start;
 291     me->code_item = iscz1_code_item;
 292     me->code_stop = iscz1_code_stop;
 293     me->code_reset = iscz1_code_reset;
 294
 295     me->debug = atoi(res_get_def (res, "isamdDebug", "0"));
 296
 297     return me;
 298 }
 299
 300 int key_SU_encode (int ch, char *out)
 301 {
 302     int i;
 303     for (i = 0; ch; i++)
 304     {
 305         if (ch >= 64)
 306             out[i] = 65 + (ch & 63);
 307         else
 308             out[i] = 1 + ch;
 309         ch = ch >> 6;
 310     }
 311     return i;
 312     /* in   out
 313        0     1
 314        1     2
 315        63    64
 316        64    65, 2
 317        65    66, 2
 318        127   128, 2
 319        128   65, 3
 320        191   128, 3
 321        192   65, 4
 322     */
 323 }
 324
 325 int key_SU_decode (int *ch, const unsigned char *out)
 326 {
 327     int len = 1;
 328     int fact = 1;
 329     *ch = 0;
 330     for (len = 1; *out >= 65; len++, out++)
 331     {
 332         *ch += (*out - 65) * fact;
 333         fact <<= 6;
 334     }
 335     *ch += (*out - 1) * fact;
 336     return len;
 337 }
 338