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