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