
Packit 
cb6d3d 
/*


Packit 
cb6d3d 
$Id: isort.h,v 1.6 2008/04/17 17:39:48 karl Exp $


Packit 
cb6d3d 


Packit 
cb6d3d 
Copyright (C) 2004, 2005, 2008 Rocky Bernstein <rocky@gnu.org>


Packit 
cb6d3d 
Copyright (C) 1998 Monty xiphmont@mit.edu


Packit 
cb6d3d 


Packit 
cb6d3d 
This program is free software: you can redistribute it and/or modify


Packit 
cb6d3d 
it under the terms of the GNU General Public License as published by


Packit 
cb6d3d 
the Free Software Foundation, either version 3 of the License, or


Packit 
cb6d3d 
(at your option) any later version.


Packit 
cb6d3d 


Packit 
cb6d3d 
This program is distributed in the hope that it will be useful,


Packit 
cb6d3d 
but WITHOUT ANY WARRANTY; without even the implied warranty of


Packit 
cb6d3d 
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


Packit 
cb6d3d 
GNU General Public License for more details.


Packit 
cb6d3d 


Packit 
cb6d3d 
You should have received a copy of the GNU General Public License


Packit 
cb6d3d 
along with this program. If not, see <http://www.gnu.org/licenses/>.


Packit 
cb6d3d 
*/


Packit 
cb6d3d 


Packit 
cb6d3d 
#ifndef _ISORT_H_


Packit 
cb6d3d 
#define _ISORT_H_


Packit 
cb6d3d 


Packit 
cb6d3d 
typedef struct sort_link{


Packit 
cb6d3d 
struct sort_link *next;


Packit 
cb6d3d 
} sort_link_t;


Packit 
cb6d3d 


Packit 
cb6d3d 
typedef struct sort_info {


Packit 
cb6d3d 
int16_t *vector; /* vector (storage doesn't belong to us) */


Packit 
cb6d3d 


Packit 
cb6d3d 
long *abspos; /* pointer for side effects */


Packit 
cb6d3d 
long size; /* vector size */


Packit 
cb6d3d 


Packit 
cb6d3d 
long maxsize; /* maximum vector size */


Packit 
cb6d3d 


Packit 
cb6d3d 
long sortbegin; /* range of contiguous sorted area */


Packit 
cb6d3d 
long lo,hi; /* current post, overlap range */


Packit 
cb6d3d 
int val; /* ...and val */


Packit 
cb6d3d 


Packit 
cb6d3d 
/* sort structs */


Packit 
cb6d3d 
sort_link_t **head; /* sort buckets (65536) */


Packit 
cb6d3d 


Packit 
cb6d3d 
long *bucketusage; /* of used buckets (65536) */


Packit 
cb6d3d 
long lastbucket;


Packit 
cb6d3d 
sort_link_t *revindex;


Packit 
cb6d3d 


Packit 
cb6d3d 
} sort_info_t;


Packit 
cb6d3d 


Packit 
cb6d3d 
/*! ========================================================================


Packit 
cb6d3d 
* sort_alloc()


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* Allocates and initializes a new, empty sort_info object, which can


Packit 
cb6d3d 
* be used to index up to (size) samples from a vector.


Packit 
cb6d3d 
*/


Packit 
cb6d3d 
extern sort_info_t *sort_alloc(long int size);


Packit 
cb6d3d 


Packit 
cb6d3d 
/*! ========================================================================


Packit 
cb6d3d 
* sort_unsortall() (internal)


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* This function resets the index for further use with a different


Packit 
cb6d3d 
* vector or range, without the overhead of an unnecessary free/alloc.


Packit 
cb6d3d 
*/


Packit 
cb6d3d 
extern void sort_unsortall(sort_info_t *i);


Packit 
cb6d3d 


Packit 
cb6d3d 
/*! ========================================================================


Packit 
cb6d3d 
* sort_setup()


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* This function initializes a previously allocated sort_info_t. The


Packit 
cb6d3d 
* sort_info_t is associated with a vector of samples of length


Packit 
cb6d3d 
* (size), whose position begins at (*abspos) within the CD's stream


Packit 
cb6d3d 
* of samples. Only the range of samples between (sortlo, sorthi)


Packit 
cb6d3d 
* will eventually be indexed for fast searching. (sortlo, sorthi)


Packit 
cb6d3d 
* are absolute sample positions.


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* ???: Why is abspos a pointer? Why not just store a copy?


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* Note: size *must* be <= the size given to the preceding sort_alloc(),


Packit 
cb6d3d 
* but no error checking is done here.


Packit 
cb6d3d 
*/


Packit 
cb6d3d 
extern void sort_setup(sort_info_t *i, int16_t *vector, long int *abspos,


Packit 
cb6d3d 
long int size, long int sortlo, long int sorthi);


Packit 
cb6d3d 


Packit 
cb6d3d 
/* =========================================================================


Packit 
cb6d3d 
* sort_free()


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* Releases all memory consumed by a sort_info object.


Packit 
cb6d3d 
*/


Packit 
cb6d3d 
extern void sort_free(sort_info_t *i);


Packit 
cb6d3d 


Packit 
cb6d3d 
/*! ========================================================================


Packit 
cb6d3d 
* sort_getmatch()


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* This function returns a sort_link_t pointer which refers to the


Packit 
cb6d3d 
* first sample equal to (value) in the vector. It only searches for


Packit 
cb6d3d 
* hits within (overlap) samples of (post), where (post) is an offset


Packit 
cb6d3d 
* within the vector. The caller can determine the position of the


Packit 
cb6d3d 
* matched sample using ipos(sort_info *, sort_link *).


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* This function returns NULL if no matches were found.


Packit 
cb6d3d 
*/


Packit 
cb6d3d 
extern sort_link_t *sort_getmatch(sort_info_t *i, long post, long overlap,


Packit 
cb6d3d 
int value);


Packit 
cb6d3d 


Packit 
cb6d3d 
/*! ========================================================================


Packit 
cb6d3d 
* sort_nextmatch()


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* This function returns a sort_link_t pointer which refers to the


Packit 
cb6d3d 
* next sample matching the criteria previously passed to


Packit 
cb6d3d 
* sort_getmatch(). See sort_getmatch() for details.


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* This function returns NULL if no further matches were found.


Packit 
cb6d3d 
*/


Packit 
cb6d3d 
extern sort_link_t *sort_nextmatch(sort_info_t *i, sort_link_t *prev);


Packit 
cb6d3d 


Packit 
cb6d3d 
/* ===========================================================================


Packit 
cb6d3d 
* is()


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* This macro returns the size of the vector indexed by the given sort_info_t.


Packit 
cb6d3d 
*/


Packit 
cb6d3d 
#define is(i) (i>size)


Packit 
cb6d3d 


Packit 
cb6d3d 
/* ===========================================================================


Packit 
cb6d3d 
* ib()


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* This macro returns the absolute position of the first sample in the vector


Packit 
cb6d3d 
* indexed by the given sort_info_t.


Packit 
cb6d3d 
*/


Packit 
cb6d3d 
#define ib(i) (*i>abspos)


Packit 
cb6d3d 


Packit 
cb6d3d 
/* ===========================================================================


Packit 
cb6d3d 
* ie()


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* This macro returns the absolute position of the sample after the last


Packit 
cb6d3d 
* sample in the vector indexed by the given sort_info_t.


Packit 
cb6d3d 
*/


Packit 
cb6d3d 
#define ie(i) (i>size+*i>abspos)


Packit 
cb6d3d 


Packit 
cb6d3d 
/* ===========================================================================


Packit 
cb6d3d 
* iv()


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* This macro returns the vector indexed by the given sort_info_t.


Packit 
cb6d3d 
*/


Packit 
cb6d3d 
#define iv(i) (i>vector)


Packit 
cb6d3d 


Packit 
cb6d3d 
/* ===========================================================================


Packit 
cb6d3d 
* ipos()


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* This macro returns the relative position (offset) within the indexed vector


Packit 
cb6d3d 
* at which the given match was found.


Packit 
cb6d3d 
*


Packit 
cb6d3d 
* It uses a littleknown and frightening aspect of C pointer arithmetic:


Packit 
cb6d3d 
* subtracting a pointer is not an arithmetic subtraction, but rather the


Packit 
cb6d3d 
* additive inverse. In other words, since


Packit 
cb6d3d 
* q = p + n returns a pointer to the nth object in p,


Packit 
cb6d3d 
* q  p = p + n  p, and


Packit 
cb6d3d 
* q  p = n, not the difference of the two addresses.


Packit 
cb6d3d 
*/


Packit 
cb6d3d 
#define ipos(i,l) (li>revindex)


Packit 
cb6d3d 


Packit 
cb6d3d 
#endif /* _ISORT_H_ */


Packit 
cb6d3d 
