|
Packit |
a38265 |
/*
|
|
Packit |
a38265 |
Copyright (C) 2003 Commonwealth Scientific and Industrial Research
|
|
Packit |
a38265 |
Organisation (CSIRO) Australia
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
Redistribution and use in source and binary forms, with or without
|
|
Packit |
a38265 |
modification, are permitted provided that the following conditions
|
|
Packit |
a38265 |
are met:
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
- Redistributions of source code must retain the above copyright
|
|
Packit |
a38265 |
notice, this list of conditions and the following disclaimer.
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
- Redistributions in binary form must reproduce the above copyright
|
|
Packit |
a38265 |
notice, this list of conditions and the following disclaimer in the
|
|
Packit |
a38265 |
documentation and/or other materials provided with the distribution.
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
- Neither the name of CSIRO Australia nor the names of its
|
|
Packit |
a38265 |
contributors may be used to endorse or promote products derived from
|
|
Packit |
a38265 |
this software without specific prior written permission.
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
|
|
Packit |
a38265 |
``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
|
Packit |
a38265 |
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
|
|
Packit |
a38265 |
PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE ORGANISATION OR
|
|
Packit |
a38265 |
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
|
Packit |
a38265 |
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
|
Packit |
a38265 |
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
|
|
Packit |
a38265 |
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
|
|
Packit |
a38265 |
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
|
|
Packit |
a38265 |
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
|
|
Packit |
a38265 |
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
Packit |
a38265 |
*/
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
#include "config.h"
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
#include <stdio.h>
|
|
Packit |
a38265 |
#include <stdlib.h>
|
|
Packit |
a38265 |
#include <string.h>
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
#include "oggz_macros.h"
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
typedef int (*OggzFunc) (void * data);
|
|
Packit |
a38265 |
typedef int (*OggzFunc1) (void * data, void * arg);
|
|
Packit |
a38265 |
typedef int (*OggzFindFunc) (void * data, long serialno);
|
|
Packit |
a38265 |
typedef int (*OggzCmpFunc) (const void * a, const void * b, void * user_data);
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
typedef struct _OggzVector OggzVector;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
typedef union {
|
|
Packit |
a38265 |
void * p;
|
|
Packit |
a38265 |
long l;
|
|
Packit |
a38265 |
} oggz_data_t;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
struct _OggzVector {
|
|
Packit |
a38265 |
int max_elements;
|
|
Packit |
a38265 |
int nr_elements;
|
|
Packit |
a38265 |
oggz_data_t * data;
|
|
Packit |
a38265 |
OggzCmpFunc compare;
|
|
Packit |
a38265 |
void * compare_user_data;
|
|
Packit |
a38265 |
};
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
/*
|
|
Packit |
a38265 |
* A vector of void * or long; iff it's a vector of void * objects, it
|
|
Packit |
a38265 |
* can be optionally sorted. (The sorting is used to implement the
|
|
Packit |
a38265 |
* packet queue; the vector of longs is used to implement OggzTable)
|
|
Packit |
a38265 |
*
|
|
Packit |
a38265 |
* if you set a comparison function (oggz_vector_set_cmp()), the vector
|
|
Packit |
a38265 |
* will be sorted and new elements will be inserted in sorted order.
|
|
Packit |
a38265 |
*
|
|
Packit |
a38265 |
* if you don't set a comparison function, new elements will be appended
|
|
Packit |
a38265 |
* at the tail
|
|
Packit |
a38265 |
*
|
|
Packit |
a38265 |
* to unset the comparison function, call oggz_vector_set_cmp (NULL,NULL)
|
|
Packit |
a38265 |
*/
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
OggzVector *
|
|
Packit |
a38265 |
oggz_vector_new (void)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
OggzVector * vector;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
vector = oggz_malloc (sizeof (OggzVector));
|
|
Packit |
a38265 |
if (vector == NULL) return NULL;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
vector->max_elements = 0;
|
|
Packit |
a38265 |
vector->nr_elements = 0;
|
|
Packit |
a38265 |
vector->data = NULL;
|
|
Packit |
a38265 |
vector->compare = NULL;
|
|
Packit |
a38265 |
vector->compare_user_data = NULL;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return vector;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
static void
|
|
Packit |
a38265 |
oggz_vector_clear (OggzVector * vector)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
if (vector->data)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
oggz_free (vector->data);
|
|
Packit |
a38265 |
vector->data = NULL;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
vector->nr_elements = 0;
|
|
Packit |
a38265 |
vector->max_elements = 0;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
void
|
|
Packit |
a38265 |
oggz_vector_delete (OggzVector * vector)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
oggz_vector_clear (vector);
|
|
Packit |
a38265 |
oggz_free (vector);
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
int
|
|
Packit |
a38265 |
oggz_vector_size (OggzVector * vector)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
if (vector == NULL) return 0;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return vector->nr_elements;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
void *
|
|
Packit |
a38265 |
oggz_vector_nth_p (OggzVector * vector, int n)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
if (vector == NULL) return NULL;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (n >= vector->nr_elements) return NULL;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return vector->data[n].p;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
long
|
|
Packit |
a38265 |
oggz_vector_nth_l (OggzVector * vector, int n)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
if (vector == NULL) return -1L;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (n >= vector->nr_elements) return -1L;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return vector->data[n].l;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
void *
|
|
Packit |
a38265 |
oggz_vector_find_p (OggzVector * vector, const void * data)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
void * d;
|
|
Packit |
a38265 |
int i;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (vector->compare == NULL) return NULL;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
for (i = 0; i < vector->nr_elements; i++) {
|
|
Packit |
a38265 |
d = vector->data[i].p;
|
|
Packit |
a38265 |
if (vector->compare (d, data, vector->compare_user_data))
|
|
Packit |
a38265 |
return d;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return NULL;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
int
|
|
Packit |
a38265 |
oggz_vector_find_index_p (OggzVector * vector, const void * data)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
void * d;
|
|
Packit |
a38265 |
int i;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (vector->compare == NULL) return -1;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
for (i = 0; i < vector->nr_elements; i++) {
|
|
Packit |
a38265 |
d = vector->data[i].p;
|
|
Packit |
a38265 |
if (vector->compare (d, data, vector->compare_user_data))
|
|
Packit |
a38265 |
return i;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return -1;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
void *
|
|
Packit |
a38265 |
oggz_vector_find_with (OggzVector * vector, OggzFindFunc func, long serialno)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
void * d;
|
|
Packit |
a38265 |
int i;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
for (i = 0; i < vector->nr_elements; i++) {
|
|
Packit |
a38265 |
d = vector->data[i].p;
|
|
Packit |
a38265 |
if (func (d, serialno))
|
|
Packit |
a38265 |
return d;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return NULL;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
int
|
|
Packit |
a38265 |
oggz_vector_foreach (OggzVector * vector, OggzFunc func)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
int i;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
for (i = 0; i < vector->nr_elements; i++) {
|
|
Packit |
a38265 |
func (vector->data[i].p);
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return 0;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
int
|
|
Packit |
a38265 |
oggz_vector_foreach1 (OggzVector * vector, OggzFunc1 func, void *arg)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
int i;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
for (i = 0; i < vector->nr_elements; i++) {
|
|
Packit |
a38265 |
func (vector->data[i].p, arg);
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return 0;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
static void
|
|
Packit |
a38265 |
_array_swap (oggz_data_t v[], int i, int j)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
void * t;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
t = v[i].p;
|
|
Packit |
a38265 |
v[i].p = v[j].p;
|
|
Packit |
a38265 |
v[j].p = t;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
/**
|
|
Packit |
a38265 |
* Helper function for oggz_vector_insert (). Sorts the vector by
|
|
Packit |
a38265 |
* insertion sort, assuming the tail element has just been added and the
|
|
Packit |
a38265 |
* rest of the vector is sorted.
|
|
Packit |
a38265 |
* \param vector An OggzVector
|
|
Packit |
a38265 |
* \pre The vector has just had a new element added to its tail
|
|
Packit |
a38265 |
* \pre All elements other than the tail element are already sorted.
|
|
Packit |
a38265 |
*/
|
|
Packit |
a38265 |
static void
|
|
Packit |
a38265 |
oggz_vector_tail_insertion_sort (OggzVector * vector)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
int i;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (vector->compare == NULL) return;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
for (i = vector->nr_elements-1; i > 0; i--) {
|
|
Packit |
a38265 |
if (vector->compare (vector->data[i-1].p, vector->data[i].p,
|
|
Packit |
a38265 |
vector->compare_user_data) > 0) {
|
|
Packit |
a38265 |
_array_swap (vector->data, i, i-1);
|
|
Packit |
a38265 |
} else {
|
|
Packit |
a38265 |
break;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
static OggzVector *
|
|
Packit |
a38265 |
oggz_vector_grow (OggzVector * vector)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
void * new_elements;
|
|
Packit |
a38265 |
int new_max_elements;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
vector->nr_elements++;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (vector->nr_elements > vector->max_elements) {
|
|
Packit |
a38265 |
if (vector->max_elements == 0) {
|
|
Packit |
a38265 |
new_max_elements = 1;
|
|
Packit |
a38265 |
} else {
|
|
Packit |
a38265 |
new_max_elements = vector->max_elements * 2;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
new_elements =
|
|
Packit |
a38265 |
oggz_realloc (vector->data, (size_t)new_max_elements * sizeof (oggz_data_t));
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (new_elements == NULL) {
|
|
Packit |
a38265 |
vector->nr_elements--;
|
|
Packit |
a38265 |
return NULL;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
vector->max_elements = new_max_elements;
|
|
Packit |
a38265 |
vector->data = new_elements;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return vector;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
void *
|
|
Packit |
a38265 |
oggz_vector_insert_p (OggzVector * vector, void * data)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
if (oggz_vector_grow (vector) == NULL)
|
|
Packit |
a38265 |
return NULL;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
vector->data[vector->nr_elements-1].p = data;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
oggz_vector_tail_insertion_sort (vector);
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return data;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
long
|
|
Packit |
a38265 |
oggz_vector_insert_l (OggzVector * vector, long ldata)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
if (oggz_vector_grow (vector) == NULL)
|
|
Packit |
a38265 |
return -1;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
vector->data[vector->nr_elements-1].l = ldata;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return ldata;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
static void
|
|
Packit |
a38265 |
oggz_vector_qsort (OggzVector * vector, int left, int right)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
int i, last;
|
|
Packit |
a38265 |
oggz_data_t * v = vector->data;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (left >= right) return;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
_array_swap (v, left, (left + right)/2);
|
|
Packit |
a38265 |
last = left;
|
|
Packit |
a38265 |
for (i = left+1; i <= right; i++) {
|
|
Packit |
a38265 |
if (vector->compare (v[i].p, v[left].p, vector->compare_user_data) < 0)
|
|
Packit |
a38265 |
_array_swap (v, ++last, i);
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
_array_swap (v, left, last);
|
|
Packit |
a38265 |
oggz_vector_qsort (vector, left, last-1);
|
|
Packit |
a38265 |
oggz_vector_qsort (vector, last+1, right);
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
int
|
|
Packit |
a38265 |
oggz_vector_set_cmp (OggzVector * vector, OggzCmpFunc compare,
|
|
Packit |
a38265 |
void * user_data)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
vector->compare = compare;
|
|
Packit |
a38265 |
vector->compare_user_data = user_data;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (compare) {
|
|
Packit |
a38265 |
oggz_vector_qsort (vector, 0, vector->nr_elements-1);
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return 0;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
static void *
|
|
Packit |
a38265 |
oggz_vector_remove_nth (OggzVector * vector, int n)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
int i;
|
|
Packit |
a38265 |
oggz_data_t * new_elements;
|
|
Packit |
a38265 |
int new_max_elements;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
vector->nr_elements--;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (vector->nr_elements == 0) {
|
|
Packit |
a38265 |
oggz_vector_clear (vector);
|
|
Packit |
a38265 |
} else {
|
|
Packit |
a38265 |
for (i = n; i < vector->nr_elements; i++) {
|
|
Packit |
a38265 |
vector->data[i] = vector->data[i+1];
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (vector->nr_elements < vector->max_elements/2) {
|
|
Packit |
a38265 |
new_max_elements = vector->max_elements/2;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
new_elements =
|
|
Packit |
a38265 |
oggz_realloc (vector->data,
|
|
Packit |
a38265 |
(size_t)new_max_elements * sizeof (oggz_data_t));
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (new_elements == NULL) {
|
|
Packit |
a38265 |
vector->data = NULL;
|
|
Packit |
a38265 |
return NULL;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
vector->max_elements = new_max_elements;
|
|
Packit |
a38265 |
vector->data = new_elements;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return vector;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
OggzVector *
|
|
Packit |
a38265 |
oggz_vector_remove_p (OggzVector * vector, void * data)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
int i;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
for (i = 0; i < vector->nr_elements; i++) {
|
|
Packit |
a38265 |
if (vector->data[i].p == data) {
|
|
Packit |
a38265 |
return oggz_vector_remove_nth (vector, i);
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return vector;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
OggzVector *
|
|
Packit |
a38265 |
oggz_vector_remove_l (OggzVector * vector, long ldata)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
int i;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
for (i = 0; i < vector->nr_elements; i++) {
|
|
Packit |
a38265 |
if (vector->data[i].l == ldata) {
|
|
Packit |
a38265 |
return oggz_vector_remove_nth (vector, i);
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return vector;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
void *
|
|
Packit |
a38265 |
oggz_vector_pop (OggzVector * vector)
|
|
Packit |
a38265 |
{
|
|
Packit |
a38265 |
void * data;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (vector == NULL || vector->data == NULL) return NULL;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
data = vector->data[0].p;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
oggz_vector_remove_nth (vector, 0);
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return data;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
}
|