index/kcompare.c

   1 /* $Id: kcompare.c,v 1.40 2002-08-02 19:26:55 adam Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
   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
  24
  25
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <stdio.h>
  29 #include <assert.h>
  30
  31 #include "index.h"
  32
  33 void key_logdump (int logmask, const void *p)
  34 {
  35     struct it_key key;
  36
  37     memcpy (&key, p, sizeof(key));
  38     logf (logmask, "%7d s=%-4d", key.sysno, key.seqno);
  39 }
  40
  41 int key_compare_it (const void *p1, const void *p2)
  42 {
  43     if (((struct it_key *) p1)->sysno != ((struct it_key *) p2)->sysno)
  44     {
  45         if (((struct it_key *) p1)->sysno > ((struct it_key *) p2)->sysno)
  46             return 2;
  47         else
  48             return -2;
  49     }
  50     if (((struct it_key *) p1)->seqno != ((struct it_key *) p2)->seqno)
  51     {
  52         if (((struct it_key *) p1)->seqno > ((struct it_key *) p2)->seqno)
  53             return 1;
  54         else
  55             return -1;
  56     }
  57     return 0;
  58 }
  59
  60 char *key_print_it (const void *p, char *buf)
  61 {
  62     const struct it_key *i = p;
  63     sprintf (buf, "%d:%d", i->sysno, i->seqno);
  64     return buf;
  65 }
  66
  67 int key_compare (const void *p1, const void *p2)
  68 {
  69     struct it_key i1, i2;
  70     memcpy (&i1, p1, sizeof(i1));
  71     memcpy (&i2, p2, sizeof(i2));
  72     if (i1.sysno != i2.sysno)
  73     {
  74         if (i1.sysno > i2.sysno)
  75             return 2;
  76         else
  77             return -2;
  78     }
  79     if (i1.seqno != i2.seqno)
  80     {
  81         if (i1.seqno > i2.seqno)
  82             return 1;
  83         else
  84             return -1;
  85     }
  86     return 0;
  87 }
  88
  89 int key_qsort_compare (const void *p1, const void *p2)
  90 {
  91     int r;
  92     size_t l;
  93     char *cp1 = *(char **) p1;
  94     char *cp2 = *(char **) p2;
  95
  96     if ((r = strcmp (cp1, cp2)))
  97         return r;
  98     l = strlen(cp1)+1;
  99     if ((r = key_compare (cp1+l+1, cp2+l+1)))
 100         return r;
 101     return cp1[l] - cp2[l];
 102 }
 103
 104 int key_get_pos (const void *p)
 105 {
 106     struct it_key key;
 107     memcpy (&key, p, sizeof(key));
 108     return key.seqno;
 109 }
 110
 111 struct iscz1_code_info {
 112     struct it_key key;
 113 };
 114
 115 static void *iscz1_code_start (int mode)
 116 {
 117     struct iscz1_code_info *p = (struct iscz1_code_info *)
 118         xmalloc (sizeof(*p));
 119     p->key.sysno = 0;
 120     p->key.seqno = 0;
 121     return p;
 122 }
 123
 124 static void iscz1_code_reset (void *vp)
 125 {
 126     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 127     p->key.sysno = 0;
 128     p->key.seqno = 0;
 129 }
 130
 131 static void iscz1_code_stop (int mode, void *p)
 132 {
 133     xfree (p);
 134 }
 135
 136 void iscz1_encode_int (unsigned d, char **dst)
 137 {
 138     unsigned char *bp = (unsigned char*) *dst;
 139
 140     if (d <= 63)
 141         *bp++ = d;
 142     else if (d <= 16383)
 143     {
 144         *bp++ = 64 | (d>>8);
 145        *bp++ = d & 255;
 146     }
 147     else if (d <= 4194303)
 148     {
 149         *bp++ = 128 | (d>>16);
 150         *bp++ = (d>>8) & 255;
 151         *bp++ = d & 255;
 152     }
 153     else
 154     {
 155         *bp++ = 192 | (d>>24);
 156         *bp++ = (d>>16) & 255;
 157         *bp++ = (d>>8) & 255;
 158         *bp++ = d & 255;
 159     }
 160     *dst = (char *) bp;
 161 }
 162
 163 int iscz1_decode_int (unsigned char **src)
 164 {
 165     unsigned c = *(*src)++;
 166     switch (c & 192)
 167     {
 168     case 0:
 169         return c;
 170     case 64:
 171         return ((c & 63) << 8) + *(*src)++;
 172     case 128:
 173         c = ((c & 63) << 8) + *(*src)++;
 174         c = (c << 8) + *(*src)++;
 175         return c;
 176     }
 177     if (c&32) /* expand sign bit to high bits */
 178        c = ((c | 63) << 8) + *(*src)++;
 179     else
 180        c = ((c & 63) << 8) + *(*src)++;
 181     c = (c << 8) + *(*src)++;
 182     c = (c << 8) + *(*src)++;
 183
 184     return c;
 185 }
 186
 187 static void iscz1_code_item (int mode, void *vp, char **dst, char **src)
 188 {
 189     struct iscz1_code_info *p = (struct iscz1_code_info *) vp;
 190     struct it_key tkey;
 191     int d;
 192
 193     if (mode == ISAMC_ENCODE)
 194     {
 195         memcpy (&tkey, *src, sizeof(struct it_key));
 196         d = tkey.sysno - p->key.sysno;
 197         if (d)
 198         {
 199             iscz1_encode_int (2*tkey.seqno + 1, dst);
 200             iscz1_encode_int (d, dst);
 201             p->key.sysno += d;
 202             p->key.seqno = tkey.seqno;
 203         }
 204         else
 205         {
 206             iscz1_encode_int (2*(tkey.seqno - p->key.seqno), dst);
 207             p->key.seqno = tkey.seqno;
 208         }
 209         (*src) += sizeof(struct it_key);
 210     }
 211     else
 212     {
 213         d = iscz1_decode_int ((unsigned char **) src);
 214         if (d & 1)
 215         {
 216             p->key.seqno = d>>1;
 217             p->key.sysno += iscz1_decode_int ((unsigned char **) src);
 218         }
 219         else
 220             p->key.seqno += d>>1;
 221         memcpy (*dst, &p->key, sizeof(struct it_key));
 222         (*dst) += sizeof(struct it_key);
 223     }
 224 }
 225
 226 ISAMS_M key_isams_m (Res res, ISAMS_M me)
 227 {
 228     isams_getmethod (me);
 229
 230     me->compare_item = key_compare;
 231
 232     me->code_start = iscz1_code_start;
 233     me->code_item = iscz1_code_item;
 234     me->code_stop = iscz1_code_stop;
 235
 236     me->debug = atoi(res_get_def (res, "isamsDebug", "0"));
 237
 238     return me;
 239 }
 240
 241 ISAMC_M key_isamc_m (Res res, ISAMC_M me)
 242 {
 243     isc_getmethod (me);
 244
 245     me->compare_item = key_compare;
 246
 247     me->code_start = iscz1_code_start;
 248     me->code_item = iscz1_code_item;
 249     me->code_stop = iscz1_code_stop;
 250     me->code_reset = iscz1_code_reset;
 251
 252     me->debug = atoi(res_get_def (res, "isamcDebug", "0"));
 253
 254     return me;
 255 }
 256
 257 ISAMD_M key_isamd_m (Res res,ISAMD_M me)
 258 {
 259
 260     me = isamd_getmethod (me);
 261
 262     me->compare_item = key_compare;
 263
 264     me->code_start = iscz1_code_start;
 265     me->code_item = iscz1_code_item;
 266     me->code_stop = iscz1_code_stop;
 267     me->code_reset = iscz1_code_reset;
 268
 269     me->debug = atoi(res_get_def (res, "isamdDebug", "0"));
 270
 271     return me;
 272 }
 273
 274 int key_SU_encode (int ch, char *out)
 275 {
 276     int i;
 277     for (i = 0; ch; i++)
 278     {
 279         if (ch >= 64)
 280             out[i] = 65 + (ch & 63);
 281         else
 282             out[i] = 1 + ch;
 283         ch = ch >> 6;
 284     }
 285     return i;
 286     /* in   out
 287        0     1
 288        1     2
 289        63    64
 290        64    65, 2
 291        65    66, 2
 292        127   128, 2
 293        128   65, 3
 294        191   128, 3
 295        192   65, 4
 296     */
 297 }
 298
 299 int key_SU_decode (int *ch, const unsigned char *out)
 300 {
 301     int len = 1;
 302     int fact = 1;
 303     *ch = 0;
 304     for (len = 1; *out >= 65; len++, out++)
 305     {
 306         *ch += (*out - 65) * fact;
 307         fact <<= 6;
 308     }
 309     *ch += (*out - 1) * fact;
 310     return len;
 311 }
 312
 313 /*
 314  * $Log: kcompare.c,v $
 315  * Revision 1.40  2002-08-02 19:26:55  adam
 316  * Towards GPL
 317  *
 318  * Revision 1.39  2002/04/12 14:55:22  adam
 319  * key_print_it
 320  *
 321  * Revision 1.38  2002/04/05 08:46:26  adam
 322  * Zebra with full functionality
 323  *
 324  * Revision 1.37  2001/11/19 23:08:30  adam
 325  * Added const qualifier for name parameter of key_SU_decode.
 326  *
 327  * Revision 1.36  2001/10/15 19:53:43  adam
 328  * POSIX thread updates. First work on term sets.
 329  *
 330  * Revision 1.35  1999/11/30 13:48:03  adam
 331  * Improved installation. Updated for inclusion of YAZ header files.
 332  *
 333  * Revision 1.34  1999/07/14 13:21:34  heikki
 334  * Added isam-d files. Compiles (almost) clean. Doesn't work at all
 335  *
 336  * Revision 1.33  1999/07/14 10:59:26  adam
 337  * Changed functions isc_getmethod, isams_getmethod.
 338  * Improved fatal error handling (such as missing EXPLAIN schema).
 339  *
 340  * Revision 1.32  1999/07/13 13:21:15  heikki
 341  * Managing negative deltas
 342  *
 343  * Revision 1.31  1999/07/06 09:37:04  heikki
 344  * Working on isamh - not ready yet.
 345  *
 346  * Revision 1.30  1999/06/30 15:07:23  heikki
 347  * Adding isamh stuff
 348  *
 349  * Revision 1.29  1999/06/30 09:08:23  adam
 350  * Added coder to reset.
 351  *
 352  * Revision 1.28  1999/05/26 07:49:13  adam
 353  * C++ compilation.
 354  *
 355  * Revision 1.27  1999/05/12 13:08:06  adam
 356  * First version of ISAMS.
 357  *
 358  * Revision 1.26  1999/02/02 14:50:54  adam
 359  * Updated WIN32 code specific sections. Changed header.
 360  *
 361  * Revision 1.25  1998/06/08 15:26:06  adam
 362  * Minor changes.
 363  *
 364  * Revision 1.24  1998/06/08 14:43:12  adam
 365  * Added suport for EXPLAIN Proxy servers - added settings databasePath
 366  * and explainDatabase to facilitate this. Increased maximum number
 367  * of databases and attributes in one register.
 368  *
 369  * Revision 1.23  1998/03/05 08:45:12  adam
 370  * New result set model and modular ranking system. Moved towards
 371  * descent server API. System information stored as "SGML" records.
 372  *
 373  * Revision 1.22  1997/09/22 12:39:06  adam
 374  * Added get_pos method for the ranked result sets.
 375  *
 376  * Revision 1.21  1997/09/17 12:19:13  adam
 377  * Zebra version corresponds to YAZ version 1.4.
 378  * Changed Zebra server so that it doesn't depend on global common_resource.
 379  *
 380  * Revision 1.20  1996/12/23 15:30:44  adam
 381  * Work on truncation.
 382  * Bug fix: result sets weren't deleted after server shut down.
 383  *
 384  * Revision 1.19  1996/12/11 12:08:00  adam
 385  * Added better compression.
 386  *
 387  * Revision 1.18  1996/10/29 14:09:44  adam
 388  * Use of cisam system - enabled if setting isamc is 1.
 389  *
 390  * Revision 1.17  1996/06/04 10:18:58  adam
 391  * Minor changes - removed include of ctype.h.
 392  *
 393  * Revision 1.16  1996/05/13  14:23:05  adam
 394  * Work on compaction of set/use bytes in dictionary.
 395  *
 396  * Revision 1.15  1995/11/20  16:59:46  adam
 397  * New update method: the 'old' keys are saved for each records.
 398  *
 399  * Revision 1.14  1995/10/30  15:08:08  adam
 400  * Bug fixes.
 401  *
 402  * Revision 1.13  1995/10/27  14:00:11  adam
 403  * Implemented detection of database availability.
 404  *
 405  * Revision 1.12  1995/10/17  18:02:08  adam
 406  * New feature: databases. Implemented as prefix to words in dictionary.
 407  *
 408  * Revision 1.11  1995/10/06  16:33:37  adam
 409  * Use attribute mappings.
 410  *
 411  * Revision 1.10  1995/09/29  14:01:41  adam
 412  * Bug fixes.
 413  *
 414  * Revision 1.9  1995/09/28  12:10:32  adam
 415  * Bug fixes. Field prefix used in queries.
 416  *
 417  * Revision 1.8  1995/09/28  09:19:42  adam
 418  * xfree/xmalloc used everywhere.
 419  * Extract/retrieve method seems to work for text records.
 420  *
 421  * Revision 1.7  1995/09/27  12:22:28  adam
 422  * More work on extract in record control.
 423  * Field name is not in isam keys but in prefix in dictionary words.
 424  *
 425  * Revision 1.6  1995/09/14  07:48:23  adam
 426  * Record control management.
 427  *
 428  * Revision 1.5  1995/09/11  13:09:34  adam
 429  * More work on relevance feedback.
 430  *
 431  * Revision 1.4  1995/09/08  14:52:27  adam
 432  * Minor changes. Dictionary is lower case now.
 433  *
 434  * Revision 1.3  1995/09/07  13:58:36  adam
 435  * New parameter: result-set file descriptor (RSFD) to support multiple
 436  * positions within the same result-set.
 437  * Boolean operators: and, or, not implemented.
 438  * Result-set references.
 439  *
 440  * Revision 1.2  1995/09/06  16:11:17  adam
 441  * Option: only one word key per file.
 442  *
 443  * Revision 1.1  1995/09/04  09:10:36  adam
 444  * More work on index add/del/update.
 445  * Merge sort implemented.
 446  * Initial work on z39 server.
 447  *
 448  */