1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
/*
* 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110, USA
*/
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#include <stdlib.h>
#include <string.h>
#include "attributes.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(const 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;
}
|
