dict/scan.c

   1 /*
   2  * Copyright (C) 1994-1998, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: scan.c,v $
   7  * Revision 1.11  1998-06-22 11:34:45  adam
   8  * Changed scan callback function so it doesn't stop further scanning.
   9  *
  10  * Revision 1.10  1998/03/06 16:58:04  adam
  11  * Fixed bug which related to scanning of large indexes.
  12  *
  13  * Revision 1.9  1997/10/27 14:33:04  adam
  14  * Moved towards generic character mapping depending on "structure"
  15  * field in abstract syntax file. Fixed a few memory leaks. Fixed
  16  * bug with negative integers when doing searches with relational
  17  * operators.
  18  *
  19  * Revision 1.8  1996/02/02 13:43:52  adam
  20  * The public functions simply use char instead of Dict_char to represent
  21  * search strings. Dict_char is used internally only.
  22  *
  23  * Revision 1.7  1995/12/11  09:04:50  adam
  24  * Bug fix: the lookup/scan/lookgrep didn't handle empty dictionary.
  25  *
  26  * Revision 1.6  1995/11/20  11:58:04  adam
  27  * Support for YAZ in standard located directories, such as /usr/local/..
  28  *
  29  * Revision 1.5  1995/10/09  16:18:32  adam
  30  * Function dict_lookup_grep got extra client data parameter.
  31  *
  32  * Revision 1.4  1995/10/06  13:52:00  adam
  33  * Bug fixes. Handler may abort further scanning.
  34  *
  35  * Revision 1.3  1995/10/06  11:06:07  adam
  36  * Bug fixes.
  37  *
  38  * Revision 1.2  1995/10/06  10:43:16  adam
  39  * Minor changes.
  40  *
  41  * Revision 1.1  1995/10/06  09:04:18  adam
  42  * First version of scan.
  43  *
  44  */
  45 #include <stdlib.h>
  46 #include <string.h>
  47 #include <stdio.h>
  48 #include <assert.h>
  49
  50 #include <dict.h>
  51
  52 int dict_scan_trav (Dict dict, Dict_ptr ptr, int pos, Dict_char *str,
  53                     int start, int *count, void *client,
  54                     int (*userfunc)(char *, const char *, int, void *),
  55                     int dir)
  56 {
  57     int lo, hi, j;
  58     void *p;
  59     short *indxp;
  60     char *info;
  61
  62     dict_bf_readp (dict->dbf, ptr, &p);
  63     hi = DICT_nodir(p)-1;
  64     if (start == 0 && dir == -1)
  65         lo = hi;
  66     else
  67         lo = start;
  68     indxp = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
  69
  70     while (lo <= hi && lo >= 0 && *count > 0)
  71     {
  72         if (indxp[-lo] > 0)
  73         {
  74             /* string (Dict_char *) DICT_EOS terminated */
  75             /* unsigned char        length of information */
  76             /* char *               information */
  77
  78             info = (char*)p + indxp[-lo];
  79             for (j = 0; info[j] != DICT_EOS; j++)
  80                 str[pos+j] = info[j];
  81             str[pos+j] = DICT_EOS;
  82             (*userfunc)((char*) str, info+(j+1)*sizeof(Dict_char),
  83                             *count * dir, client);
  84             --(*count);
  85         }
  86         else
  87         {
  88             Dict_char dc;
  89             Dict_ptr subptr;
  90
  91             /* Dict_ptr             subptr */
  92             /* Dict_char            sub char */
  93             /* unsigned char        length of information */
  94             /* char *               information */
  95
  96             info = (char*)p - indxp[-lo];
  97             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
  98             str[pos] = dc;
  99             memcpy (&subptr, info, sizeof(Dict_ptr));
 100             if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 101             {
 102                  str[pos+1] = DICT_EOS;
 103                  if ((*userfunc)((char*) str,
 104                                  info+sizeof(Dict_ptr)+sizeof(Dict_char),
 105                                  *count * dir, client))
 106                      return 1;
 107                  --(*count);
 108             }
 109             if (*count > 0 && subptr)
 110             {
 111                 dict_scan_trav (dict, subptr, pos+1, str, 0, count,
 112                                 client, userfunc, dir);
 113                 dict_bf_readp (dict->dbf, ptr, &p);
 114                 indxp = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
 115             }
 116         }
 117         lo += dir;
 118     }
 119     return 0;
 120 }
 121
 122 int dict_scan_r (Dict dict, Dict_ptr ptr, int pos, Dict_char *str,
 123                  int *before, int *after, void *client,
 124                  int (*userfunc)(char *, const char *, int, void *))
 125 {
 126     int cmp = 0, mid, lo, hi;
 127     void *p;
 128     short *indxp;
 129     char *info;
 130
 131     dict_bf_readp (dict->dbf, ptr, &p);
 132     if (!p)
 133         return 0;
 134     mid = lo = 0;
 135     hi = DICT_nodir(p)-1;
 136     indxp = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
 137     while (lo <= hi)
 138     {
 139         mid = (lo+hi)/2;
 140         if (indxp[-mid] > 0)
 141         {
 142             /* string (Dict_char *) DICT_EOS terminated */
 143             /* unsigned char        length of information */
 144             /* char *               information */
 145             info = (char*)p + indxp[-mid];
 146             cmp = dict_strcmp ((Dict_char*) info, str + pos);
 147             if (!cmp)
 148             {
 149                 if (*after)
 150                 {
 151                     (*userfunc)((char *) str, info+
 152                                 (dict_strlen((Dict_char*) info)+1)
 153                                 *sizeof(Dict_char),
 154                                 *after, client);
 155                     --(*after);
 156                 }
 157                 break;
 158             }
 159         }
 160         else
 161         {
 162             Dict_char dc;
 163             Dict_ptr subptr;
 164
 165             /* Dict_ptr             subptr */
 166             /* Dict_char            sub char */
 167             /* unsigned char        length of information */
 168             /* char *               information */
 169             info = (char*)p - indxp[-mid];
 170             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
 171             cmp = dc - str[pos];
 172             if (!cmp)
 173             {
 174                 memcpy (&subptr, info, sizeof(Dict_ptr));
 175                 if (str[pos+1] == DICT_EOS)
 176                 {
 177                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 178                     {
 179                         if (*after)
 180                         {
 181                             (*userfunc)((char*) str,
 182                                         info+sizeof(Dict_ptr)+
 183                                         sizeof(Dict_char),
 184                                         *after, client);
 185                             --(*after);
 186                         }
 187                     }
 188                     if (*after && subptr)
 189                         if (dict_scan_trav (dict, subptr, pos+1, str, 0,
 190                                             after, client, userfunc, 1))
 191                             return 1;
 192                 }
 193                 else if (subptr)
 194                 {
 195                     if (dict_scan_r (dict, subptr, pos+1, str, before, after,
 196                                      client, userfunc))
 197                         return 1;
 198                 }
 199                 break;
 200             }
 201         }
 202         if (cmp < 0)
 203             lo = mid+1;
 204         else
 205             hi = mid-1;
 206     }
 207     if (lo>hi && cmp < 0)
 208         ++mid;
 209     if (*after)
 210         if (dict_scan_trav (dict, ptr, pos, str, cmp ? mid : mid+1, after,
 211                             client, userfunc, 1))
 212             return 1;
 213     if (*before && mid > 1)
 214         if (dict_scan_trav (dict, ptr, pos, str, mid-1, before,
 215                             client, userfunc, -1))
 216             return 1;
 217     return 0;
 218 }
 219
 220 int dict_scan (Dict dict, char *str, int *before, int *after, void *client,
 221                int (*f)(char *name, const char *info, int pos, void *client))
 222 {
 223     int i;
 224
 225     logf (LOG_DEBUG, "dict_scan");
 226     for (i = 0; str[i]; i++)
 227     {
 228         logf (LOG_DEBUG, " %3d  %c", str[i],
 229               (str[i] > ' ' && str[i] < 127) ? str[i] : '?');
 230     }
 231     if (dict->head.last <= 1)
 232         return 0;
 233     return dict_scan_r (dict, 1, 0, (Dict_char *) str, before, after, client,
 234                         f);
 235 }
 236