1 /* @(#)isort.h	1.12 08/09/18 J. Schilling from cdparanoia-III-alpha9.8 */
2 /*
3  * CopyPolicy: GNU Lesser General Public License v2.1 applies
4  * Copyright (C) 1997-2001,2008 by Monty (xiphmont@mit.edu)
5  * Copyright (C) 2002-2008 by J. Schilling
6  */
7 
8 #ifndef	_ISORT_H
9 #define	_ISORT_H
10 
11 typedef struct sort_link {
12 	struct sort_link *next;
13 } sort_link;
14 
15 typedef struct sort_info {
16 	Int16_t		*vector;	/* vector */
17 					/* vec storage doesn't belong to us */
18 
19 	long		*abspos;	/* pointer for side effects */
20 	long		size;		/* vector size */
21 
22 	long		maxsize;	/* maximum vector size */
23 
24 	long		sortbegin;	/* range of contiguous sorted area */
25 	long		lo;
26 	long		hi;		/* current post, overlap range */
27 	int		val;		/* ...and val */
28 
29 	/*
30 	 * sort structs
31 	 */
32 	sort_link	**head;		/* sort buckets (65536) */
33 
34 	long		*bucketusage;	/* of used buckets (65536) */
35 	long		lastbucket;
36 	sort_link	*revindex;
37 
38 } sort_info;
39 
40 /*
41  * sort_alloc()
42  *
43  * Allocates and initializes a new, empty sort_info object, which can
44  * be used to index up to (size) samples from a vector.
45  */
46 extern sort_info	*sort_alloc	__PR((long size));
47 
48 /*
49  * sort_unsortall() (internal)
50  *
51  * This function resets the index for further use with a different
52  * vector or range, without the overhead of an unnecessary free/alloc.
53  */
54 extern void		sort_unsortall	__PR((sort_info * i));
55 
56 /*
57  * sort_setup()
58  *
59  * This function initializes a previously allocated sort_info_t.  The
60  * sort_info_t is associated with a vector of samples of length
61  * (size), whose position begins at (*abspos) within the CD's stream
62  * of samples.  Only the range of samples between (sortlo, sorthi)
63  * will eventually be indexed for fast searching.  (sortlo, sorthi)
64  * are absolute sample positions.
65  *
66  * Note: size *must* be <= the size given to the preceding sort_alloc(),
67  * but no error checking is done here.
68  */
69 extern void		sort_setup	__PR((sort_info * i, Int16_t * vector,
70 						long *abspos, long size,
71 						long sortlo, long sorthi));
72 
73 /*
74  * sort_free()
75  *
76  * Releases all memory consumed by a sort_info object.
77  */
78 extern void		sort_free	__PR((sort_info * i));
79 
80 /*
81  * sort_getmatch()
82  *
83  * This function returns a sort_link_t pointer which refers to the
84  * first sample equal to (value) in the vector.  It only searches for
85  * hits within (overlap) samples of (post), where (post) is an offset
86  * within the vector.  The caller can determine the position of the
87  * matched sample using ipos(sort_info *, sort_link *).
88  *
89  * This function returns NULL if no matches were found.
90  */
91 extern sort_link	*sort_getmatch	__PR((sort_info * i, long post,
92 						long overlap, int value));
93 
94 /*
95  * sort_nextmatch()
96  *
97  * This function returns a sort_link_t pointer which refers to the
98  * next sample matching the criteria previously passed to
99  * sort_getmatch().  See sort_getmatch() for details.
100  *
101  * This function returns NULL if no further matches were found.
102  */
103 extern sort_link	*sort_nextmatch	__PR((sort_info * i, sort_link * prev));
104 
105 
106 
107 /*
108  * is()
109  *
110  * This macro returns the size of the vector indexed by the given sort_info_t.
111  */
112 #define	is(i)		((i)->size)
113 
114 /*
115  * ib()
116  *
117  * This macro returns the absolute position of the first sample in the vector
118  * indexed by the given sort_info_t.
119  */
120 #define	ib(i)		(*(i)->abspos)
121 
122 /*
123  * ie()
124  *
125  * This macro returns the absolute position of the sample after the last
126  * sample in the vector indexed by the given sort_info_t.
127  */
128 #define	ie(i)		((i)->size + *(i)->abspos)
129 
130 /*
131  * iv()
132  *
133  * This macro returns the vector indexed by the given sort_info_t.
134  */
135 #define	iv(i)		((i)->vector)
136 
137 /*
138  * ipos()
139  *
140  * This macro returns the relative position (offset) within the indexed vector
141  * at which the given match was found.
142  *
143  * It uses a little-known and frightening aspect of C pointer arithmetic:
144  * subtracting a pointer is not an arithmetic subtraction, but rather the
145  * additive inverse.  In other words, since
146  *   q     = p + n returns a pointer to the nth object in p,
147  *   q - p = p + n - p, and
148  *   q - p = n, not the difference of the two addresses.
149  */
150 #define	ipos(i, l)	((l) - (i)->revindex)
151 
152 #endif	/* _ISORT_H */
153