isort.h

Go to the documentation of this file.

/*
  $Id: isort.h,v 1.6 2008/04/17 17:39:48 karl Exp $
 
  Copyright (C) 2004, 2005, 2008 Rocky Bernstein <rocky@gnu.org>
  Copyright (C) 1998 Monty xiphmont@mit.edu
 
  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.
 
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
 
  You should have received a copy of the GNU General Public License
  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
 
#ifndef _ISORT_H_
#define _ISORT_H_
 
typedef struct sort_link{
  struct sort_link *next;
} sort_link_t;
 
typedef struct sort_info {
  int16_t *vector;               /* vector (storage doesn't belong to us) */
 
  long  *abspos;                 /* pointer for side effects */
  long  size;                    /* vector size */
 
  long  maxsize;                 /* maximum vector size */
 
  long sortbegin;                /* range of contiguous sorted area */
  long lo,hi;                    /* current post, overlap range */
  int  val;                      /* ...and val */
 
  /* sort structs */
  sort_link_t **head;           /* sort buckets (65536) */
 
  long *bucketusage;          /*  of used buckets (65536) */
  long lastbucket;
  sort_link_t *revindex;
 
} sort_info_t;
 
extern sort_info_t *sort_alloc(long int size);
 
extern void sort_unsortall(sort_info_t *i);
 
extern void sort_setup(sort_info_t *i, int16_t *vector, long int *abspos,
                       long int size, long int sortlo, long int sorthi);
 
/* =========================================================================
 * sort_free()
 *
 * Releases all memory consumed by a sort_info object.
 */
extern void sort_free(sort_info_t *i);
 
extern sort_link_t *sort_getmatch(sort_info_t *i, long post, long overlap,
                                  int value);
 
extern sort_link_t *sort_nextmatch(sort_info_t *i, sort_link_t *prev);
 
/* ===========================================================================
 * is()
 *
 * This macro returns the size of the vector indexed by the given sort_info_t.
 */
#define is(i) (i->size)
 
/* ===========================================================================
 * ib()
 *
 * This macro returns the absolute position of the first sample in the vector
 * indexed by the given sort_info_t.
 */
#define ib(i) (*i->abspos)
 
/* ===========================================================================
 * ie()
 *
 * This macro returns the absolute position of the sample after the last
 * sample in the vector indexed by the given sort_info_t.
 */
#define ie(i) (i->size+*i->abspos)
 
/* ===========================================================================
 * iv()
 *
 * This macro returns the vector indexed by the given sort_info_t.
 */
#define iv(i) (i->vector)
 
/* ===========================================================================
 * ipos()
 *
 * This macro returns the relative position (offset) within the indexed vector
 * at which the given match was found.
 *
 * It uses a little-known and frightening aspect of C pointer arithmetic:
 * subtracting a pointer is not an arithmetic subtraction, but rather the
 * additive inverse.  In other words, since
 *   q     = p + n returns a pointer to the nth object in p,
 *   q - p = p + n - p, and
 *   q - p = n, not the difference of the two addresses.
 */
#define ipos(i,l) (l-i->revindex)
 
#endif /* _ISORT_H_ */