summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/xine-utils/array.c127
-rw-r--r--src/xine-utils/array.h59
-rw-r--r--src/xine-utils/list.h102
-rw-r--r--src/xine-utils/sorted_array.c118
-rw-r--r--src/xine-utils/sorted_array.h97
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
+
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-22 11:38:41 +0000