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