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