diff options
| -rw-r--r-- | src/xine-utils/array.c | 127 | ||||
| -rw-r--r-- | src/xine-utils/array.h | 59 | ||||
| -rw-r--r-- | src/xine-utils/list.h | 102 | ||||
| -rw-r--r-- | src/xine-utils/sorted_array.c | 118 | ||||
| -rw-r--r-- | src/xine-utils/sorted_array.h | 97 |
5 files changed, 503 insertions, 0 deletions
diff --git a/src/xine-utils/array.c b/src/xine-utils/array.c new file mode 100644 index 000000000..5d55cb8df --- /dev/null +++ b/src/xine-utils/array.c @@ -0,0 +1,127 @@ +/* + * Copyright (C) 2000-2006 the xine project + * + * This file is part of xine, a free video player. + * + * xine 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 2 of the License, or + * (at your option) any later version. + * + * xine 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, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA + * + * $Id: array.c,v 1.1 2006/01/16 08:04:44 tmattern Exp $ + * + */ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <stdlib.h> +#include "array.h" + +#define MIN_CHUNK_SIZE 32 + +/* Array internal struct */ +struct xine_array_s { + void **chunk; + size_t chunk_size; + size_t size; +}; + +static void xine_array_ensure_chunk_size(xine_array_t *array, size_t size) { + if (size > array->chunk_size) { + /* realloc */ + size_t new_size = 2 * array->chunk_size; + + array->chunk = (void**)realloc(array->chunk, sizeof(void *) * new_size); + array->chunk_size = new_size; + } +} + +/* Constructor */ +xine_array_t *xine_array_new(size_t initial_size) { + xine_array_t *new_array; + + new_array = (xine_array_t *)malloc(sizeof(xine_array_t)); + if (!new_array) + return NULL; + + if (initial_size < MIN_CHUNK_SIZE) + initial_size = MIN_CHUNK_SIZE; + + new_array->chunk = (void**)malloc(sizeof(void*) * initial_size); + if (!new_array->chunk) { + free(new_array); + return NULL; + } + new_array->chunk_size = initial_size; + new_array->size = 0; + + return new_array; +} + +/* Destructor */ +void xine_array_delete(xine_array_t *array) { + if (array->chunk) { + free(array->chunk); + } + free(array); +} + +size_t xine_array_size(xine_array_t *array) { + return array->size; +} + +void xine_array_clear(xine_array_t *array) { + array->size = 0; +} + +void xine_array_add(xine_array_t *array, void *value) { + xine_array_ensure_chunk_size(array, array->size + 1); + array->chunk[array->size] = value; + array->size++; +} + +void xine_array_insert(xine_array_t *array, unsigned int position, void *value) { + if (position < array->size) { + xine_array_ensure_chunk_size(array, array->size + 1); + memmove(&array->chunk[position + 1], + &array->chunk[position], + sizeof(void *) * (array->size - position)); + array->chunk[position] = value; + array->size++; + } else { + xine_array_add(array, value); + } +} + +void xine_array_remove(xine_array_t *array, unsigned int position) { + if (array->size > 0) { + if (position < array->size) { + memmove(&array->chunk[position], + &array->chunk[position + 1], + sizeof(void *) * (array->size - (position + 1))); + } + array->size--; + } +} + +void *xine_array_get(xine_array_t *array, unsigned int position) { + if (position < array->size) + return array->chunk[position]; + else + return NULL; +} + +void xine_array_set(xine_array_t *array, unsigned int position, void *value) { + if (position < array->size) + array->chunk[position] = value; +} diff --git a/src/xine-utils/array.h b/src/xine-utils/array.h new file mode 100644 index 000000000..f0e0bb521 --- /dev/null +++ b/src/xine-utils/array.h @@ -0,0 +1,59 @@ +/* + * Copyright (C) 2000-2006 the xine project + * + * This file is part of xine, a free video player. + * + * xine 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 2 of the License, or + * (at your option) any later version. + * + * xine 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, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA + * + * $Id: array.h,v 1.1 2006/01/16 08:04:44 tmattern Exp $ + * + * Array that can grow automatically when you add elements. + * Inserting an element in the middle of the array implies memory moves. + */ +#ifndef XINE_ARRAY_H +#define XINE_ARRAY_H + +/* Array type */ +typedef struct xine_array_s xine_array_t; + +/* Constructor */ +xine_array_t *xine_array_new(size_t initial_size); + +/* Destructor */ +void xine_array_delete(xine_array_t *array); + +/* Returns the number of element stored in the array */ +size_t xine_array_size(xine_array_t *array); + +/* Removes all elements from an array */ +void xine_array_clear(xine_array_t *array); + +/* Adds the element at the end of the array */ +void xine_array_add(xine_array_t *array, void *value); + +/* Inserts an element into an array at the position specified */ +void xine_array_insert(xine_array_t *array, unsigned int position, void *value); + +/* Removes one element from an array at the position specified */ +void xine_array_remove(xine_array_t *array, unsigned int position); + +/* Get the element at the position specified */ +void *xine_array_get(xine_array_t *array, unsigned int position); + +/* Set the element at the position specified */ +void xine_array_set(xine_array_t *array, unsigned int position, void *value); + +#endif + diff --git a/src/xine-utils/list.h b/src/xine-utils/list.h new file mode 100644 index 000000000..388de88cc --- /dev/null +++ b/src/xine-utils/list.h @@ -0,0 +1,102 @@ +/* + * Copyright (C) 2000-2006 the xine project + * + * This file is part of xine, a free video player. + * + * xine 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 2 of the License, or + * (at your option) any later version. + * + * xine 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, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA + * + * $Id: list.h,v 1.1 2006/01/16 08:04:44 tmattern Exp $ + * + * Doubly-linked linked list. + * + * Exemples: + * + * Create a list: + * xine_list_t *list = xine_list_new(); + * + * Delete a list: + * xine_list_delete(list); + * + * Walk thru a list: + * xine_list_iterator_t ite = xine_list_front(list); + * while (ite) { + * _useful code here_ + * ite = xine_list_iterator_next(ite); + * } + * + * The list elements are managed using memory chunks and a free list. The first + * chunk contains 32 elements, each following chunk is two time as big as the + * previous one, with a limit of 64K elements. + */ +#ifndef XINE_LIST_H +#define XINE_LIST_H + +/* Doubly-linked list type */ +typedef struct xine_list_s xine_list_t; + +/* List iterator */ +typedef void* xine_list_iterator_t; + +/* Constructor */ +xine_list_t *xine_list_new(); + +/* Destructor */ +void xine_list_delete(xine_list_t *list); + +/* Returns the number of element stored in the list */ +unsigned int xine_list_size(xine_list_t *list); + +/* Returns true if the number of elements is zero, false otherwise */ +unsigned int xine_list_empty(xine_list_t *list); + +/* Adds the element at the beginning of the list */ +void xine_list_push_front(xine_list_t *list, void *value); + +/* Adds the element at the end of the list */ +void xine_list_push_back(xine_list_t *list, void *value); + +/* Remove all elements from a list */ +void xine_list_clear(xine_list_t *list); + +/* Insert the element elem into the list at the position specified by the + iterator (before the element, if any, that was previously at the iterator's + position). The return value is an iterator that specifies the position of + the inserted element. */ +xine_list_iterator_t xine_list_insert(xine_list_t *list, + xine_list_iterator_t position, + void *value); + +/* Remove one element from a list.*/ +void xine_list_remove(xine_list_t *list, xine_list_iterator_t position); + +/* Returns an iterator that references the first element of the list */ +xine_list_iterator_t xine_list_front(xine_list_t *list); + +/* Returns an iterator that references the last element of the list */ +xine_list_iterator_t xine_list_back(xine_list_t *list); + +/* Increments the iterator's value, so it specifies the next element in the list + or NULL at the end of the list */ +xine_list_iterator_t xine_list_iterator_next(xine_list_iterator_t ite); + +/* Increments the iterator's value, so it specifies the previous element in the list + or NULL at the beginning of the list */ +xine_list_iterator_t xine_list_iterator_prev(xine_list_iterator_t ite); + +/* Returns the element at the position specified by the iterator */ +void *xine_list_iterator_value(xine_list_iterator_t ite); + +#endif + diff --git a/src/xine-utils/sorted_array.c b/src/xine-utils/sorted_array.c new file mode 100644 index 000000000..3046969f5 --- /dev/null +++ b/src/xine-utils/sorted_array.c @@ -0,0 +1,118 @@ +/* + * Copyright (C) 2000-2006 the xine project + * + * This file is part of xine, a free video player. + * + * xine 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 2 of the License, or + * (at your option) any later version. + * + * xine 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, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA + * + * $Id: sorted_array.c,v 1.1 2006/01/16 08:04:44 tmattern Exp $ + * + */ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <stdlib.h> +#include <string.h> +#include "sorted_array.h" + +/* Array internal struct */ +struct xine_sarray_s { + xine_array_t *array; + xine_sarray_comparator_t comparator; +}; + +/* Constructor */ +xine_sarray_t *xine_sarray_new(size_t initial_size, xine_sarray_comparator_t comparator) { + xine_sarray_t *new_sarray; + + new_sarray = (xine_sarray_t *)malloc(sizeof(xine_sarray_t)); + if (!new_sarray) + return NULL; + + new_sarray->array = xine_array_new(initial_size); + new_sarray->comparator = comparator; + + return new_sarray; +} + +/* Destructor */ +void xine_sarray_delete(xine_sarray_t *sarray) { + if (sarray->array) { + xine_array_delete(sarray->array); + } + free(sarray); +} + +size_t xine_sarray_size(xine_sarray_t *sarray) { + return xine_array_size(sarray->array); +} + +void xine_sarray_clear(xine_sarray_t *sarray) { + xine_array_clear(sarray->array); +} + +int xine_sarray_add(xine_sarray_t *sarray, void *value) { + int pos; + + pos = xine_sarray_binary_search(sarray, value); + if (pos < 0) + pos = ~pos; + xine_array_insert(sarray->array, pos, value); + + return pos; +} + +void xine_sarray_remove(xine_sarray_t *sarray, unsigned int position) { + xine_array_remove(sarray->array, position); +} + +void *xine_sarray_get(xine_sarray_t *sarray, unsigned int position) { + return xine_array_get(sarray->array, position); +} + +int xine_sarray_binary_search(xine_sarray_t *sarray, void *key) { + int low, high, mid, pos; + int comp; + + if (xine_array_size(sarray->array) > 0) { + low = 0; + high = xine_array_size(sarray->array) - 1; + + while ((high - low ) > 1) { + mid = low + (high - low) / 2; + if (sarray->comparator(key, xine_array_get(sarray->array, mid)) < 0) { + high = mid; + } else { + low = mid; + } + } + + if ((comp = sarray->comparator(key, xine_array_get(sarray->array, low))) < 0) { + pos = ~low; /* not found */ + } else if (comp == 0) { + pos = low; /* found */ + } else if ((comp = sarray->comparator(key, xine_array_get(sarray->array, high))) < 0) { + pos = ~high; /* not found */ + } else if (comp == 0) { + pos = high; /* found */ + } else { + pos = ~(high + 1); /* not found */ + } + } else { + pos = ~0; /* not found */ + } + return pos; +} diff --git a/src/xine-utils/sorted_array.h b/src/xine-utils/sorted_array.h new file mode 100644 index 000000000..c5fe1b413 --- /dev/null +++ b/src/xine-utils/sorted_array.h @@ -0,0 +1,97 @@ +/* + * Copyright (C) 2000-2006 the xine project + * + * This file is part of xine, a free video player. + * + * xine 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 2 of the License, or + * (at your option) any later version. + * + * xine 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, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA + * + * $Id: sorted_array.h,v 1.1 2006/01/16 08:04:44 tmattern Exp $ + * + * Sorted array which grows automatically when you add elements. + * A binary search is used to find the position of a new element. + * + * Example: + * Let's create de comparison method for integers: + * + * int int_comparator(void *a, void *b) { + * if ((int)a < (int)b) { + * return -1; + * } else if ((int)a == (int)b) { + * return 0; + * } else { + * return 1; + * } + * } + * + * Create a sorted array for integers: + * xine_sarray_t *sarray = xine_sarray_new(10, int_comparator); + * + * Add elements: + * xine_sarray_add(sarray, (void*)4); + * xine_sarray_add(sarray, (void*)28); + * xine_sarray_add(sarray, (void*)7); + * + * Find an element: + * int pos = xine_sarray_binary_search(sarray, (void*)7); + * if (pos >= 0) + * FOUND + * else + * NOT FOUND + * + * Delete the array: + * xine_sarray_delete(sarray); + * + */ +#ifndef XINE_SORTED_ARRAY_H +#define XINE_SORTED_ARRAY_H + +#include "array.h" + +/* Array type */ +typedef struct xine_sarray_s xine_sarray_t; + +/* Array element comparator */ +typedef int (*xine_sarray_comparator_t)(void*, void*); + +/* Constructor */ +xine_sarray_t *xine_sarray_new(size_t initial_size, xine_sarray_comparator_t comparator); + +/* Destructor */ +void xine_sarray_delete(xine_sarray_t *sarray); + +/* Returns the number of element stored in the array */ +size_t xine_sarray_size(xine_sarray_t *sarray); + +/* Removes all elements from an array */ +void xine_sarray_clear(xine_sarray_t *sarray); + +/* Adds the element into the array + Returns the insertion position */ +int xine_sarray_add(xine_sarray_t *sarray, void *value); + +/* Removes one element from an array at the position specified */ +void xine_sarray_remove(xine_sarray_t *sarray, unsigned int position); + +/* Get the element at the position specified */ +void *xine_sarray_get(xine_sarray_t *sarray, unsigned int position); + +/* Returns the index of the search key, if it is contained in the list. + Otherwise, (-(insertion point) - 1) or ~(insertion point). + The insertion point is defined as the point at which the key would be + inserted into the array. */ +int xine_sarray_binary_search(xine_sarray_t *sarray, void *key); + +#endif + |