dict/scan.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: scan.c,v $
   7  * Revision 1.1  1995-10-06 09:04:18  adam
   8  * First version of scan.
   9  *
  10  */
  11 #include <stdlib.h>
  12 #include <string.h>
  13 #include <stdio.h>
  14 #include <assert.h>
  15
  16 #include <dict.h>
  17
  18 void dict_scan_trav (Dict dict, Dict_ptr ptr, int pos, Dict_char *str,
  19                     int start, int *count,
  20                     int (*userfunc)(Dict_char *, const char *, int pos),
  21                     int dir)
  22 {
  23     int lo, hi, j;
  24     void *p;
  25     short *indxp;
  26     char *info;
  27
  28     dict_bf_readp (dict->dbf, ptr, &p);
  29     hi = DICT_nodir(p)-1;
  30     if (start == 0 && dir == -1)
  31         lo = hi;
  32     else
  33         lo = start;
  34     indxp = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
  35
  36     while (lo <= hi && lo >= 0 && *count > 0)
  37     {
  38         if (indxp[-lo] > 0)
  39         {
  40             /* string (Dict_char *) DICT_EOS terminated */
  41             /* unsigned char        length of information */
  42             /* char *               information */
  43
  44             info = (char*)p + indxp[-lo];
  45             for (j = 0; info[j] != DICT_EOS; j++)
  46                 str[pos+j] = info[j];
  47             str[pos+j] = DICT_EOS;
  48             (*userfunc)(str, info+j*sizeof(Dict_char), *count * dir);
  49             --(*count);
  50         }
  51         else
  52         {
  53             Dict_char dc;
  54             Dict_ptr subptr;
  55
  56             /* Dict_ptr             subptr */
  57             /* Dict_char            sub char */
  58             /* unsigned char        length of information */
  59             /* char *               information */
  60
  61             info = (char*)p - indxp[-lo];
  62             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
  63             str[pos] = dc;
  64             memcpy (&subptr, info, sizeof(Dict_ptr));
  65             if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
  66             {
  67                  str[pos+1] = DICT_EOS;
  68                  (*userfunc)(str, info+sizeof(Dict_ptr)+sizeof(Dict_char),
  69                              *count * dir);
  70                  --(*count);
  71             }
  72             if (*count > 0 && subptr)
  73                  dict_scan_trav (dict, subptr, pos+1, str, 0, count,
  74                                  userfunc, dir);
  75         }
  76         lo += dir;
  77     }
  78 }
  79
  80 int dict_scan_r (Dict dict, Dict_ptr ptr, int pos, Dict_char *str,
  81                  int *before, int *after,
  82                  int (*userfunc)(Dict_char *, const char *, int))
  83 {
  84     int cmp = 0, mid, lo, hi, j;
  85     void *p;
  86     short *indxp;
  87     char *info;
  88
  89     dict_bf_readp (dict->dbf, ptr, &p);
  90     mid = lo = 0;
  91     hi = DICT_nodir(p)-1;
  92     indxp = (short*) ((char*) p+DICT_pagesize(dict)-sizeof(short));
  93     while (lo <= hi)
  94     {
  95         mid = (lo+hi)/2;
  96         if (indxp[-mid] > 0)
  97         {
  98             /* string (Dict_char *) DICT_EOS terminated */
  99             /* unsigned char        length of information */
 100             /* char *               information */
 101             info = (char*)p + indxp[-mid];
 102             cmp = dict_strcmp ((Dict_char*) info, str + pos);
 103             if (!cmp)
 104             {
 105                 for (j = 0; info[j++] != DICT_EOS; )
 106                     ;
 107                 (*userfunc)(str, info+j*sizeof(Dict_char), *after);
 108                 --(*after);
 109                 break;
 110             }
 111         }
 112         else
 113         {
 114             Dict_char dc;
 115             Dict_ptr subptr;
 116
 117             /* Dict_ptr             subptr */
 118             /* Dict_char            sub char */
 119             /* unsigned char        length of information */
 120             /* char *               information */
 121             info = (char*)p - indxp[-mid];
 122             memcpy (&dc, info+sizeof(Dict_ptr), sizeof(Dict_char));
 123             cmp = dc - str[pos];
 124             if (!cmp)
 125             {
 126                 memcpy (&subptr, info, sizeof(Dict_ptr));
 127                 if (str[pos+1] == DICT_EOS)
 128                 {
 129                     if (info[sizeof(Dict_ptr)+sizeof(Dict_char)])
 130                     {
 131                         (*userfunc)(str,
 132                                     info+sizeof(Dict_ptr)+sizeof(Dict_char),
 133                                     *after);
 134                         --(*after);
 135                     }
 136                     if (*after > 0 && subptr)
 137                         dict_scan_trav (dict, subptr, pos+1, str, 0,
 138                                         after, userfunc, 1);
 139                 }
 140                 else if (*after > 0 && subptr)
 141                     dict_scan_r (dict, subptr, pos+1, str, before, after,
 142                                  userfunc);
 143                 break;
 144             }
 145         }
 146         if (cmp < 0)
 147             lo = mid+1;
 148         else
 149             hi = mid-1;
 150     }
 151     if (lo>hi && cmp < 0)
 152         ++mid;
 153     if (*after)
 154         dict_scan_trav (dict, ptr, pos, str, cmp ? mid : mid+1, after,
 155                         userfunc, 1);
 156     if (*before && mid > 1)
 157         dict_scan_trav (dict, ptr, pos, str, mid-1, before,
 158                         userfunc, -1);
 159     return 0;
 160 }
 161
 162 int dict_scan (Dict dict, Dict_char *str, int *before, int *after,
 163                int (*f)(Dict_char *name, const char *info, int pos))
 164 {
 165     int i;
 166     i = dict_scan_r (dict, 1, 0, str, before, after, f);
 167     return i;
 168 }
 169