1 /* 2 * Copyright (C) 2000-2018 the xine project 3 * 4 * This file is part of xine, a free video player. 5 * 6 * xine is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation; either version 2 of the License, or 9 * (at your option) any later version. 10 * 11 * xine is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program; if not, write to the Free Software 18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110, USA 19 * 20 * Sorted array which grows automatically when you add elements. 21 * A binary search is used to find the position of a new element. 22 * 23 * Example: 24 * Let's create de comparison method for integers: 25 * 26 * int int_comparator(void *a, void *b) { 27 * if ((int)a < (int)b) { 28 * return -1; 29 * } else if ((int)a == (int)b) { 30 * return 0; 31 * } else { 32 * return 1; 33 * } 34 * } 35 * 36 * Create a sorted array for integers: 37 * xine_sarray_t *sarray = xine_sarray_new(10, int_comparator); 38 * 39 * Add elements: 40 * xine_sarray_add(sarray, (void*)4); 41 * xine_sarray_add(sarray, (void*)28); 42 * xine_sarray_add(sarray, (void*)7); 43 * 44 * Find an element: 45 * int pos = xine_sarray_binary_search(sarray, (void*)7); 46 * if (pos >= 0) 47 * FOUND 48 * else 49 * NOT FOUND 50 * 51 * Delete the array: 52 * xine_sarray_delete(sarray); 53 */ 54 #ifndef XINE_SORTED_ARRAY_H 55 #define XINE_SORTED_ARRAY_H 56 57 #include <stddef.h> /* size_t */ 58 #include <xine/attributes.h> 59 60 /* Array type */ 61 typedef struct xine_sarray_s xine_sarray_t; 62 63 /* Array element comparator */ 64 typedef int (*xine_sarray_comparator_t)(void*, void*); 65 66 /* Constructor */ 67 xine_sarray_t *xine_sarray_new(size_t initial_size, xine_sarray_comparator_t comparator) XINE_MALLOC XINE_PROTECTED; 68 69 /* Destructor */ 70 void xine_sarray_delete(xine_sarray_t *sarray) XINE_PROTECTED; 71 72 /* Set mode */ 73 /* For both add() and binary_search(): if there are multiple matching indices, 74 * select 1 of them randomly. That is, the order of matches does not matter, just be fast. */ 75 #define XINE_SARRAY_MODE_DEFAULT 0x00000000 76 /* select the first match. */ 77 #define XINE_SARRAY_MODE_FIRST 0x80000000 78 /* select the last match (+ 1 if found). */ 79 #define XINE_SARRAY_MODE_LAST 0x40000000 80 /* For add(): if there is a match already, dont add another copy, 81 * and return ~(found_index) instead. */ 82 #define XINE_SARRAY_MODE_UNIQUE 0x20000000 83 void xine_sarray_set_mode (xine_sarray_t *sarray, unsigned int mode) XINE_PROTECTED; 84 85 /* Returns the number of element stored in the array */ 86 size_t xine_sarray_size(const xine_sarray_t *sarray) XINE_PROTECTED; 87 88 /* Removes all elements from an array */ 89 void xine_sarray_clear(xine_sarray_t *sarray) XINE_PROTECTED; 90 91 /* Adds the element into the array 92 Returns the insertion position */ 93 int xine_sarray_add(xine_sarray_t *sarray, void *value) XINE_PROTECTED; 94 95 /* Removes one element from an array at the position specified */ 96 void xine_sarray_remove(xine_sarray_t *sarray, unsigned int position) XINE_PROTECTED; 97 98 /* Removes one element from an array by user pointer. 99 * Return the index it was found at, or ~0. */ 100 int xine_sarray_remove_ptr (xine_sarray_t *sarray, void *ptr) XINE_PROTECTED; 101 102 /* Get the element at the position specified */ 103 void *xine_sarray_get(xine_sarray_t *sarray, unsigned int position) XINE_PROTECTED; 104 105 /* Returns the index of the search key, if it is contained in the list. 106 Otherwise, (-(insertion point) - 1) or ~(insertion point). 107 The insertion point is defined as the point at which the key would be 108 inserted into the array. */ 109 int xine_sarray_binary_search(xine_sarray_t *sarray, void *key) XINE_PROTECTED; 110 111 #endif 112 113