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.2  1994-09-16 15:39:14  adam
   8  * Initial code of lookup - not tested yet.
   9  *
  10  * Revision 1.1  1994/08/16  16:26:48  adam
  11  * Added dict.
  12  *
  13  */
  14
  15 #include <stdlib.h>
  16 #include <string.h>
  17 #include <stdio.h>
  18 #include <assert.h>
  19
  20 #include <dict.h>
  21
  22 static char *dict_look (Dict dict, Dict_char *str)
  23 {
  24     Dict_ptr ptr = 1;
  25     int mid, lo, hi;
  26     int cmp;
  27     void *p;
  28     short *indxp;
  29     char *info;
  30
  31     dict_bf_readp (dict->dbf, ptr, &p);
  32     mid = lo = 0;
  33     hi = DICT_nodir(p)-1;
  34     indxp = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
  35     while (lo <= hi)
  36     {
  37         mid = (lo+hi)/2;
  38         if (indxp[-mid] > 0)
  39         {
  40             /* string (Dict_char *) DICT_EOS terminated */
  41             /* unsigned char        length of information */
  42             /* char *               information */
  43             info = (char*)p + indxp[-mid];
  44             cmp = dict_strcmp((Dict_char*) info, str);
  45             if (!cmp)
  46                 return info+(dict_strlen (info)+1)*sizeof(Dict_char);
  47         }
  48         else
  49         {
  50             Dict_char dc;
  51             Dict_ptr subptr;
  52
  53             /* Dict_ptr             subptr */
  54             /* Dict_char            sub char */
  55             /* unsigned char        length of information */
  56             /* char *               information */
  57             info = (char*)p - indxp[-mid];
  58             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
  59             cmp = dc- *str;
  60             if (!cmp)
  61             {
  62                 memcpy (&subptr, info, sizeof(Dict_ptr));
  63                 if (*++str == DICT_EOS)
  64                     return info+sizeof(Dict_ptr)+sizeof(Dict_char);
  65                 else
  66                 {
  67                     if (subptr == 0)
  68                         return NULL;
  69                     ptr = subptr;
  70                     dict_bf_readp (dict->dbf, ptr, &p);
  71                     mid = lo = 0;
  72                     hi = DICT_nodir(p)-1;
  73                     indxp = (short*) ((char*) p+DICT_PAGESIZE-sizeof(short));
  74                     continue;
  75                 }
  76             }
  77         }
  78         if (cmp < 0)
  79             lo = mid+1;
  80         else
  81             hi = mid-1;
  82     }
  83     return NULL;
  84 }
  85
  86 char *dict_lookup (Dict dict, Dict_char *p)
  87 {
  88     if (dict->head.last == 1)
  89         return NULL;
  90     return dict_look (dict, p);
  91 }
  92
  93