dict/lookup.c

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