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