dict/lookup.c

   1 /*
   2  * Copyright (C) 1994-1999, Index Data
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: lookup.c,v $
   7  * Revision 1.9  1999-02-02 14:50:25  adam
   8  * Updated WIN32 code specific sections. Changed header.
   9  *
  10  * Revision 1.8  1998/03/05 08:17:24  adam
  11  * Added a few comments - no code changed.
  12  *
  13  * Revision 1.7  1996/02/02 13:43:51  adam
  14  * The public functions simply use char instead of Dict_char to represent
  15  * search strings. Dict_char is used internally only.
  16  *
  17  * Revision 1.6  1995/12/11  09:04:50  adam
  18  * Bug fix: the lookup/scan/lookgrep didn't handle empty dictionary.
  19  *
  20  * Revision 1.5  1995/09/04  09:09:15  adam
  21  * String arg in lookup is const.
  22  *
  23  * Revision 1.4  1994/10/05  12:16:51  adam
  24  * Pagesize is a resource now.
  25  *
  26  * Revision 1.3  1994/09/26  10:17:25  adam
  27  * Minor changes.
  28  *
  29  * Revision 1.2  1994/09/16  15:39:14  adam
  30  * Initial code of lookup - not tested yet.
  31  *
  32  * Revision 1.1  1994/08/16  16:26:48  adam
  33  * Added dict.
  34  *
  35  */
  36
  37 #include <stdlib.h>
  38 #include <string.h>
  39 #include <stdio.h>
  40 #include <assert.h>
  41
  42 #include <dict.h>
  43
  44 static char *dict_look (Dict dict, const Dict_char *str)
  45 {
  46     Dict_ptr ptr = 1;
  47     int mid, lo, hi;
  48     int cmp;
  49     void *p;
  50     short *indxp;
  51     char *info;
  52
  53     dict_bf_readp (dict->dbf, ptr, &p);
  54     mid = lo = 0;
  55     hi = DICT_nodir(p)-1;
  56     indxp = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
  57     while (lo <= hi)
  58     {
  59         mid = (lo+hi)/2;
  60         if (indxp[-mid] > 0)
  61         {
  62             /* string (Dict_char *) DICT_EOS terminated */
  63             /* unsigned char        length of information */
  64             /* char *               information */
  65             info = (char*)p + indxp[-mid];
  66             cmp = dict_strcmp((Dict_char*) info, str);
  67             if (!cmp)
  68                 return info+(dict_strlen ((Dict_char*) info)+1)
  69                     *sizeof(Dict_char);
  70         }
  71         else
  72         {
  73             Dict_char dc;
  74             Dict_ptr subptr;
  75
  76             /* Dict_ptr             subptr */
  77             /* Dict_char            sub char */
  78             /* unsigned char        length of information */
  79             /* char *               information */
  80             info = (char*)p - indxp[-mid];
  81             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
  82             cmp = dc- *str;
  83             if (!cmp)
  84             {
  85                 memcpy (&subptr, info, sizeof(Dict_ptr));
  86                 if (*++str == DICT_EOS)
  87                 {
  88                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
  89                         return info+sizeof(Dict_ptr)+sizeof(Dict_char);
  90                     return NULL;
  91                 }
  92                 else
  93                 {
  94                     if (subptr == 0)
  95                         return NULL;
  96                     ptr = subptr;
  97                     dict_bf_readp (dict->dbf, ptr, &p);
  98                     mid = lo = 0;
  99                     hi = DICT_nodir(p)-1;
 100                     indxp = (short*) ((char*) p+DICT_pagesize(dict)
 101                                       -sizeof(short));
 102                     continue;
 103                 }
 104             }
 105         }
 106         if (cmp < 0)
 107             lo = mid+1;
 108         else
 109             hi = mid-1;
 110     }
 111     return NULL;
 112 }
 113
 114 char *dict_lookup (Dict dict, const char *p)
 115 {
 116     if (dict->head.last <= 1)
 117         return NULL;
 118     return dict_look (dict, (const Dict_char *) p);
 119 }
 120
 121