dict/scan.c

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