![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to mtchstring.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / cmd / odist / pax / src / lib / libodelta|
Return to mtchstring.c CVS log | Up to [Research Unix] / researchv10dc / cmd / odist / pax / src / lib / libodelta |
1.1 root 1: #include "update.h"
2:
3:
4: /*
5: ** Find the longest prefix of tar that match some substring of src
6: ** This uses an inverted index for speed.
7: */
8: #define ALPHA (256) /* alphabet size */
9:
10: static void freemem(n_index,index)
11: long *n_index;
12: char ***index;
13: {
14: register int i;
15: if(n_index && index)
16: {
17: for(i = 0; i < ALPHA; ++i)
18: if(n_index[i] > 0)
19: free(index[i]);
20: free(index);
21: free(n_index);
22: }
23: }
24:
25: /* initial assumptions: src[0] == tar[0] && src+n_match <= endsrc */
26: static long domatch(src,endsrc,tar,endtar,n_match)
27: char *src, *endsrc, *tar, *endtar;
28: long n_match;
29: {
30: register char *sp, *tp;
31:
32: /* see if this really improves on the current match */
33: for(sp = src+n_match, tp = tar+n_match; sp > src; --sp, --tp)
34: if(*sp != *tp)
35: break;
36:
37: /* got an improvement, match as many more as we can */
38: if(sp == src)
39: {
40: sp = src+n_match+1;
41: tp = tar+n_match+1;
42: for(; sp < endsrc && tp < endtar; ++sp, ++tp)
43: if(*sp != *tp)
44: break;
45: }
46: return tp-tar;
47: }
48:
49: /* the real thing */
50: long mtchstring(src,n_src,tar,n_tar,match)
51: char *src; /* the source string to match from */
52: long n_src; /* the length of src */
53: char *tar; /* the string a prefix of which is matched */
54: long n_tar; /* the length of tar */
55: char **match; /* to return the matched address in src */
56: {
57: char *endsrc, *endtar;
58: long n_match;
59: register int i;
60: register long n_ind;
61: register char **ind;
62: static long *N_index = NIL(long);
63: static char *Cursrc = NIL(char), ***Index = NIL(char**);
64: static int Alloced = 0;
65: char **malloc(), **realloc();
66:
67: /* free old inverted indices if necessary */
68: if(src != Cursrc)
69: {
70: if(Alloced)
71: freemem(N_index,Index);
72: Alloced = 0;
73: Cursrc = NIL(char);
74: }
75:
76: /* nothing to do */
77: if(!src || n_src <= 0 || !tar || n_tar <= 0)
78: return 0;
79:
80: endsrc = src + n_src;
81: endtar = tar + n_tar;
82:
83: /* build new index structure */
84: if(src != Cursrc)
85: {
86: Cursrc = src;
87: Alloced = 1;
88: if(N_index = (long*) malloc(ALPHA*sizeof(long)))
89: {
90: register char *sp;
91:
92: memzero((char*)N_index,ALPHA*sizeof(long));
93: if(!(Index = (char ***) malloc(ALPHA*sizeof(char**))))
94: {
95: free(N_index);
96: N_index = NIL(long);
97: Alloced = 0;
98: }
99: else for(sp = src; sp < endsrc; ++sp)
100: {
101: i = (int)(*((unsigned char *)(sp)));
102: ind = Index[i];
103: n_ind = N_index[i];
104:
105: /* make sure we have space */
106: if((n_ind%ALPHA) == 0)
107: {
108: ind = n_ind == 0 ?
109: malloc(ALPHA*sizeof(char *)) :
110: realloc(ind,(n_ind+ALPHA)*sizeof(char*));
111: Index[i] = ind;
112: }
113: if(ind)
114: {
115: ind[n_ind] = sp;
116: N_index[i] += 1;
117: }
118: else
119: {
120: freemem(N_index,Index);
121: N_index = NIL(long);
122: Index = NIL(char**);
123: Alloced = 0;
124: break;
125: }
126: }
127: }
128: }
129:
130: /* find longest matching prefix */
131: i = (int)(*((unsigned char *)(tar)));
132: ind = Alloced ? Index[i] : NULL;
133: n_ind = Alloced ? N_index[i] : -1;
134: n_match = 0;
135: while(1)
136: {
137: register long m;
138:
139: if(ind)
140: {
141: src = n_ind > 0 ? *ind++ : endsrc;
142: n_ind -= 1;
143: }
144: else for(; src+n_match < endsrc; ++src)
145: if(*src == *tar)
146: break;
147: if(src+n_match >= endsrc)
148: break;
149:
150: if((m = domatch(src,endsrc,tar,endtar,n_match)) > n_match)
151: {
152: n_match = m;
153: *match = src;
154: if(tar+n_match >= endtar)
155: break;
156: }
157: }
158:
159: return n_match;
160: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.