Cross Reference: /ast/src/lib/libvcodex/vcsfxsort.c

Lines Matching defs:sfx
55 static int chktodo(Vcsfx_t* sfx, Vcsfxint_t lo, Vcsfxint_t hi)
66 		return (lo == 0 && hi == sfx->nstr-1) ? 1 : 0;
74 static int chkdata(Vcsfx_t* sfx, Vcsfxint_t lo, Vcsfxint_t hi)
76 	Vcsfxint_t	*idx = sfx->idx, *inv = sfx->inv;
79 	if(lo > hi || !chktodo(sfx,lo,hi))
100 static int cmpsfx(Vcsfx_t* sfx, Vcsfxint_t p, Vcsfxint_t s)
101 {	Vcchar_t	*ps = sfx->str+p, *ss = sfx->str+s;
103 	p = sfx->nstr-p; s = sfx->nstr-s;
112 static int chksorted(Vcsfx_t* sfx, Vcsfxint_t lo, Vcsfxint_t hi)
113 {	Vcsfxint_t	*i, *inv = sfx->inv, *idx = sfx->idx;
115 	if(!chktodo(sfx,lo,hi))
119 	min = min == sfx->idx ? min+1 : min;
120 	max = max < (sfx->idx+sfx->nstr-1) ? max+1 : max;
122 		DEBUG_ASSERT(cmpsfx(sfx, min[-1], min[0]) < 0);
132 static void sfxbsort(Vcsfx_t* sfx, Vcsfxint_t* grp)
134 static void sfxbsort(sfx, grp)
135 Vcsfx_t*	sfx;
142 	Vcsfxint_t	*idx = sfx->idx, *inv = sfx->inv;
145 	for(ends = (s = sfx->str)+sfx->nstr-1, i = *s; s < ends; i = j)
152 		{	inv[sfx->nstr-1] = n;
153 			idx[n++] = sfx->nstr-1;
157 	for(n = 0, ends = (s = sfx->str)+sfx->nstr-1, i = *s; s < ends; i = j)
161 	for(n = 0, ends = (s = sfx->str)+sfx->nstr-1, i = *s; s < ends; i = j)
166 	grp[256*256] = sfx->nstr; /* end of 255*255-group */
187 static void sfxqsort(Vcsfx_t* sfx, Vcsfxint_t* min, Vcsfxint_t* max, Vcsfxint_t hdr, int period)
189 static void sfxqsort(sfx, min, max, hdr, period)
190 Vcsfx_t*	sfx;
198 	Vcsfxint_t	*inv = sfx->inv, *idx = sfx->idx;
262 		sfxqsort(sfx, min, le-1, hdr, 0);
264 		/**/DEBUG_ASSERT(chkdata(sfx,min-idx,(le-1)-idx));
272 			sfxqsort(sfx, le, re, hdr+2, 0);
286 		sfxqsort(sfx, re+1, max, hdr, 0);
288 		/**/DEBUG_ASSERT(chkdata(sfx,min-idx,(le-1)-idx));
301 			/**/DEBUG_ASSERT(chkdata(sfx,min-idx,max-idx));
311 static void sfxcsort(Vcsfx_t* sfx, Vcsfxint_t y, Vcsfxint_t* grp)
313 static void sfxcsort(sfx, y, grp)
314 Vcsfx_t*	sfx;
321 	Vcchar_t	*str = sfx->str;
322 	Vcsfxint_t	*inv = sfx->inv, *idx = sfx->idx;
323 	Vcsfxint_t	endc = sfx->str[sfx->nstr-1];
352 	/**/DEBUG_ASSERT(chkdata(sfx, omin, omax));
356 static int sfxosort(Vcsfx_t* sfx, Vcsfxint_t x, Vcsfxint_t* grp, int dir)
358 static int sfxosort(sfx, x, grp, dir)
359 Vcsfx_t*	sfx;
369 	Vcchar_t	*str = sfx->str, endc = sfx->str[sfx->nstr-1];
370 	Vcsfxint_t	nstr = sfx->nstr, *inv = sfx->inv, *idx = sfx->idx;
413 		sfxqsort(sfx, idx+l, idx+r, 2, 2);
414 		/**/DEBUG_ASSERT(chkdata(sfx, l, r));
436 	Vcsfx_t		*sfx; /* suffix array structure	*/
442 	if(!(sfx = (Vcsfx_t*)malloc(sizeof(Vcsfx_t)+2*(nstr+1)*sizeof(Vcsfxint_t))) )
444 	sfx->idx = idx = (Vcsfxint_t*)(sfx+1);
445 	sfx->inv = inv = idx+nstr+1;
446 	sfx->str = str;
447 	sfx->nstr = (Vcsfxint_t)nstr;
448 	idx[sfx->nstr] = inv[sfx->nstr] = sfx->nstr; /* the infinite eos byte */
449 	if(sfx->nstr <= 1) /* the easy sorting case */
451 		return sfx;
454 	sfxbsort(sfx, grp); /* sort suffixes by first 2 bytes */
474 		if(sfxosort(sfx, x, grp, d) < 0)
476 		sfxcsort(sfx, x, grp);
520 		if(sfxosort(sfx, x, grp, 0) < 0)
522 		sfxcsort(sfx, x, grp); /* copy-sort */
534 	/**/DEBUG_ASSERT(chkdata(sfx,0,sfx->nstr-1) && chksorted(sfx,0,sfx->nstr-1) );
537 	{	free(sfx);
538 		sfx = NIL(Vcsfx_t*);
541 	return sfx;