Ads

 1 /******************************************************************************
 2 *
 3 * Copyright (C) 2006, The Gentee Group. All rights reserved. 
 4 * This file is part of the Gentee open source project <http://www.gentee.com>. 
 5 * 
 6 * THIS FILE IS PROVIDED UNDER THE TERMS OF THE GENTEE LICENSE ("AGREEMENT"). 
 7 * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS FILE CONSTITUTES RECIPIENTS 
 8 * ACCEPTANCE OF THE AGREEMENT.
 9 *
10 * search 20.04.2007 0.0.A.
11 *
12 * Author:  
13 *
14 ******************************************************************************/
15 
16 #include "../common/memory.h"
17 #include "search.h"
18 
19 //Quick search Sunday's algorithm
20 
21 void STDCALL qs_init( pssearch psearch, pubyte pattern, uint m, uint flag ) 
22 {
23    uint i;
24 
25    psearch->pattern = pattern;
26    psearch->size = m;
27    psearch->flag = flag;
28 
29    for ( i = 0; i < ABC_COUNT; ++i )
30       psearch->shift[ i ] = m + 1;
31    
32    if ( flag & QS_IGNCASE )
33       for ( i = 0; i < m; ++i )
34          psearch->shift[ _lower[ pattern[ i ]]] = m - i;
35    else
36       for ( i = 0; i < m; ++i )
37          psearch->shift[ pattern[ i ]] = m - i;
38 }
39 
40 uint STDCALL qs_search( pssearch psearch, pubyte y, uint n ) 
41 {
42    uint j, i, m;
43    pubyte x;
44 
45    j = 0;
46    m = psearch->size;
47    x = psearch->pattern;
48    if ( n < m ) return n;
49 
50    if ( psearch->flag & QS_IGNCASE )
51    {
52       while ( j <= n - m ) 
53       {
54          for ( i = 0; i < m; i++ )
55          {
56             if ( _lower[ x[ i ]] != _lower[ y[ j + i ]] ) goto nextign;
57          }
58          if ( psearch->flag & QS_WORD )
59          {
60             if (( !j || !_name[ y[ j - 1 ]]) && ( j + m == n || 
61                   !_name[ y[ j + m ]])) return j;
62          }
63          else
64             if ( psearch->flag & QS_BEGINWORD )
65             {
66                if ( !j || !_name[ y[ j - 1 ]] ) return j;
67             }
68             else return j;
69 nextign:
70          j += psearch->shift[ _lower[ y[ j + m ]]];
71       }
72    }
73    else
74       while ( j <= n - m ) 
75       {
76          for ( i = 0; i < m; i++ )
77          {
78             if ( x[ i ] != y[ j + i ] ) goto next;
79          }
80          if ( psearch->flag & QS_WORD )
81          {
82             if (( !j || !_name[ y[ j - 1 ]]) && ( j + m == n || 
83                   !_name[ y[ j + m ]])) return j;
84          }
85          else
86             if ( psearch->flag & QS_BEGINWORD )
87             {
88                if ( !j || !_name[ y[ j - 1 ]] ) return j;
89             }
90             else return j;
91 next:
92          j += psearch->shift[ y[ j + m ]];
93       }
94 
95    return n;
96 }
97 
98 //--------------------------------------------------------------------------