Debian Codegraph @

libs/gst/base/gstmemindex.c

raw
1 /* GStreamer
2 * Copyright (C) <1999> Erik Walthinsen <[email protected]>
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Library General Public License for more details.
13 *
14 * You should have received a copy of the GNU Library General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 */
19
20 #include <gst/gst.h>
21
22 #define GST_TYPE_MEM_INDEX \
23 (gst_index_get_type ())
24 #define GST_MEM_INDEX(obj) \
25 (G_TYPE_CHECK_INSTANCE_CAST ((obj), GST_TYPE_MEM_INDEX, GstMemIndex))
26 #define GST_MEM_INDEX_CLASS(klass) \
27 (G_TYPE_CHECK_CLASS_CAST ((klass), GST_TYPE_MEM_INDEX, GstMemIndexClass))
28 #define GST_IS_MEM_INDEX(obj) \
29 (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GST_TYPE_MEM_INDEX))
30 #define GST_IS_MEM_INDEX_CLASS(klass) \
31 (GST_TYPE_CHECK_CLASS_TYPE ((klass), GST_TYPE_MEM_INDEX))
32
33 /*
34 * Object model:
35 *
36 * All entries are simply added to a GList first. Then we build
37 * an index to each entry for each id/format
38 *
39 *
40 * memindex
41 * -----------------------------...
42 * ! !
43 * id1 id2
44 * ------------
45 * ! !
46 * format1 format2
47 * ! !
48 * GTree GTree
49 *
50 *
51 * The memindex creates a MemIndexId object for each writer id, a
52 * Hashtable is kept to map the id to the MemIndexId
53 *
54 * The MemIndexId keeps a MemIndexFormatIndex for each format the
55 * specific writer wants indexed.
56 *
57 * The MemIndexFormatIndex keeps all the values of the particular
58 * format in a GTree, The values of the GTree point back to the entry.
59 *
60 * Finding a value for an id/format requires locating the correct GTree,
61 * then do a lookup in the Tree to get the required value.
62 */
63
64 typedef struct
65 {
66 GstFormat format;
67 gint offset;
68 GTree *tree;
69 }
70 GstMemIndexFormatIndex;
71
72 typedef struct
73 {
74 gint id;
75 GHashTable *format_index;
76 }
77 GstMemIndexId;
78
79 typedef struct _GstMemIndex GstMemIndex;
80 typedef struct _GstMemIndexClass GstMemIndexClass;
81
82 struct _GstMemIndex
83 {
84 GstIndex parent;
85
86 GList *associations;
87
88 GHashTable *id_index;
89 };
90
91 struct _GstMemIndexClass
92 {
93 GstIndexClass parent_class;
94 };
95
96 static void gst_mem_index_finalize (GObject * object);
97
98 static void gst_mem_index_add_entry (GstIndex * index, GstIndexEntry * entry);
99 static GstIndexEntry *gst_mem_index_get_assoc_entry (GstIndex * index, gint id,
100 GstIndexLookupMethod method, GstIndexAssociationFlags flags,
101 GstFormat format, gint64 value, GCompareDataFunc func, gpointer user_data);
102
103 #define CLASS(mem_index) GST_MEM_INDEX_CLASS (G_OBJECT_GET_CLASS (mem_index))
104
105 static GType gst_mem_index_get_type (void);
106
107 G_DEFINE_TYPE (GstMemIndex, gst_mem_index, GST_TYPE_INDEX);
108
109 static void
110 gst_mem_index_class_init (GstMemIndexClass * klass)
111 {
112 GObjectClass *gobject_class;
113 GstIndexClass *gstindex_class;
114
115 gobject_class = (GObjectClass *) klass;
116 gstindex_class = (GstIndexClass *) klass;
117
118 gobject_class->finalize = gst_mem_index_finalize;
119
120 gstindex_class->add_entry = GST_DEBUG_FUNCPTR (gst_mem_index_add_entry);
121 gstindex_class->get_assoc_entry =
122 GST_DEBUG_FUNCPTR (gst_mem_index_get_assoc_entry);
123 }
124
125 static void
126 gst_mem_index_init (GstMemIndex * index)
127 {
128 GST_DEBUG ("created new mem index");
129
130 index->associations = NULL;
131 index->id_index = g_hash_table_new (g_int_hash, g_int_equal);
132 }
133
134 static void
135 gst_mem_index_free_format (gpointer key, gpointer value, gpointer user_data)
136 {
137 GstMemIndexFormatIndex *index = (GstMemIndexFormatIndex *) value;
138
139 if (index->tree) {
140 g_tree_destroy (index->tree);
141 }
142
143 g_free (index);
144 }
145
146 static void
147 gst_mem_index_free_id (gpointer key, gpointer value, gpointer user_data)
148 {
149 GstMemIndexId *id_index = (GstMemIndexId *) value;
150
151 if (id_index->format_index) {
152 g_hash_table_foreach (id_index->format_index, gst_mem_index_free_format,
153 NULL);
154 g_hash_table_destroy (id_index->format_index);
155 id_index->format_index = NULL;
156 }
157
158 g_free (id_index);
159 }
160
161 static void
162 gst_mem_index_finalize (GObject * object)
163 {
164 GstMemIndex *memindex = GST_MEM_INDEX (object);
165
166 /* Delete the trees referencing the associations first */
167 if (memindex->id_index) {
168 g_hash_table_foreach (memindex->id_index, gst_mem_index_free_id, NULL);
169 g_hash_table_destroy (memindex->id_index);
170 memindex->id_index = NULL;
171 }
172
173 /* Then delete the associations themselves */
174 if (memindex->associations) {
175 g_list_foreach (memindex->associations, (GFunc) gst_index_entry_free, NULL);
176 g_list_free (memindex->associations);
177 memindex->associations = NULL;
178 }
179
180 G_OBJECT_CLASS (gst_mem_index_parent_class)->finalize (object);
181 }
182
183 static void
184 gst_mem_index_add_id (GstIndex * index, GstIndexEntry * entry)
185 {
186 GstMemIndex *memindex = GST_MEM_INDEX (index);
187 GstMemIndexId *id_index;
188
189 id_index = g_hash_table_lookup (memindex->id_index, &entry->id);
190
191 if (!id_index) {
192 id_index = g_new0 (GstMemIndexId, 1);
193
194 id_index->id = entry->id;
195 id_index->format_index = g_hash_table_new (g_int_hash, g_int_equal);
196 g_hash_table_insert (memindex->id_index, &id_index->id, id_index);
197 }
198 }
199
200 static gint
201 mem_index_compare (gconstpointer a, gconstpointer b, gpointer user_data)
202 {
203 GstMemIndexFormatIndex *index = user_data;
204 gint64 val1, val2;
205 gint64 diff;
206
207 val1 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *) a), index->offset);
208 val2 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *) b), index->offset);
209
210 diff = (val2 - val1);
211
212 return (diff == 0 ? 0 : (diff > 0 ? 1 : -1));
213 }
214
215 static void
216 gst_mem_index_index_format (GstMemIndexId * id_index, GstIndexEntry * entry,
217 gint assoc)
218 {
219 GstMemIndexFormatIndex *index;
220 GstFormat *format;
221
222 format = &GST_INDEX_ASSOC_FORMAT (entry, assoc);
223
224 index = g_hash_table_lookup (id_index->format_index, format);
225
226 if (!index) {
227 index = g_new0 (GstMemIndexFormatIndex, 1);
228
229 index->format = *format;
230 index->offset = assoc;
231 index->tree = g_tree_new_with_data (mem_index_compare, index);
232
233 g_hash_table_insert (id_index->format_index, &index->format, index);
234 }
235
236 g_tree_insert (index->tree, entry, entry);
237 }
238
239 static void
240 gst_mem_index_add_association (GstIndex * index, GstIndexEntry * entry)
241 {
242 GstMemIndex *memindex = GST_MEM_INDEX (index);
243 GstMemIndexId *id_index;
244
245 memindex->associations = g_list_prepend (memindex->associations, entry);
246
247 id_index = g_hash_table_lookup (memindex->id_index, &entry->id);
248 if (id_index) {
249 gint i;
250
251 for (i = 0; i < GST_INDEX_NASSOCS (entry); i++) {
252 gst_mem_index_index_format (id_index, entry, i);
253 }
254 }
255 }
256
257 static void
258 gst_mem_index_add_object (GstIndex * index, GstIndexEntry * entry)
259 {
260 }
261
262 static void
263 gst_mem_index_add_format (GstIndex * index, GstIndexEntry * entry)
264 {
265 }
266
267 static void
268 gst_mem_index_add_entry (GstIndex * index, GstIndexEntry * entry)
269 {
270 GST_LOG_OBJECT (index, "added this entry");
271
272 switch (entry->type) {
273 case GST_INDEX_ENTRY_ID:
274 gst_mem_index_add_id (index, entry);
275 break;
276 case GST_INDEX_ENTRY_ASSOCIATION:
277 gst_mem_index_add_association (index, entry);
278 break;
279 case GST_INDEX_ENTRY_OBJECT:
280 gst_mem_index_add_object (index, entry);
281 break;
282 case GST_INDEX_ENTRY_FORMAT:
283 gst_mem_index_add_format (index, entry);
284 break;
285 default:
286 break;
287 }
288 }
289
290 typedef struct
291 {
292 gint64 value;
293 GstMemIndexFormatIndex *index;
294 gboolean exact;
295 GstIndexEntry *lower;
296 gint64 low_diff;
297 GstIndexEntry *higher;
298 gint64 high_diff;
299 }
300 GstMemIndexSearchData;
301
302 static gint
303 mem_index_search (gconstpointer a, gconstpointer b)
304 {
305 GstMemIndexSearchData *data = (GstMemIndexSearchData *) b;
306 GstMemIndexFormatIndex *index = data->index;
307 gint64 val1, val2;
308 gint64 diff;
309
310 val1 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *) a), index->offset);
311 val2 = data->value;
312
313 diff = (val1 - val2);
314 if (diff == 0)
315 return 0;
316
317 /* exact matching, don't update low/high */
318 if (data->exact)
319 return (diff > 0 ? 1 : -1);
320
321 if (diff < 0) {
322 if (diff > data->low_diff) {
323 data->low_diff = diff;
324 data->lower = (GstIndexEntry *) a;
325 }
326 diff = -1;
327 } else {
328 if (diff < data->high_diff) {
329 data->high_diff = diff;
330 data->higher = (GstIndexEntry *) a;
331 }
332 diff = 1;
333 }
334
335 return diff;
336 }
337
338 static GstIndexEntry *
339 gst_mem_index_get_assoc_entry (GstIndex * index, gint id,
340 GstIndexLookupMethod method,
341 GstIndexAssociationFlags flags,
342 GstFormat format, gint64 value, GCompareDataFunc func, gpointer user_data)
343 {
344 GstMemIndex *memindex = GST_MEM_INDEX (index);
345 GstMemIndexId *id_index;
346 GstMemIndexFormatIndex *format_index;
347 GstIndexEntry *entry;
348 GstMemIndexSearchData data;
349
350 id_index = g_hash_table_lookup (memindex->id_index, &id);
351 if (!id_index)
352 return NULL;
353
354 format_index = g_hash_table_lookup (id_index->format_index, &format);
355 if (!format_index)
356 return NULL;
357
358 data.value = value;
359 data.index = format_index;
360 data.exact = (method == GST_INDEX_LOOKUP_EXACT);
361
362 /* setup data for low/high checks if we are not looking
363 * for an exact match */
364 if (!data.exact) {
365 data.low_diff = G_MININT64;
366 data.lower = NULL;
367 data.high_diff = G_MAXINT64;
368 data.higher = NULL;
369 }
370
371 entry = g_tree_search (format_index->tree, mem_index_search, &data);
372
373 /* get the low/high values if we're not exact */
374 if (entry == NULL && !data.exact) {
375 if (method == GST_INDEX_LOOKUP_BEFORE)
376 entry = data.lower;
377 else if (method == GST_INDEX_LOOKUP_AFTER) {
378 entry = data.higher;
379 }
380 }
381
382 if (entry && ((GST_INDEX_ASSOC_FLAGS (entry) & flags) != flags)) {
383 if (method != GST_INDEX_LOOKUP_EXACT) {
384 GList *l_entry = g_list_find (memindex->associations, entry);
385
386 entry = NULL;
387
388 while (l_entry) {
389 entry = (GstIndexEntry *) l_entry->data;
390
391 if (entry->id == id && (GST_INDEX_ASSOC_FLAGS (entry) & flags) == flags)
392 break;
393
394 if (method == GST_INDEX_LOOKUP_BEFORE)
395 l_entry = g_list_next (l_entry);
396 else if (method == GST_INDEX_LOOKUP_AFTER) {
397 l_entry = g_list_previous (l_entry);
398 }
399 }
400 } else {
401 entry = NULL;
402 }
403 }
404
405 return entry;
406 }
407
408 #if 0
409 gboolean
410 gst_mem_index_plugin_init (GstPlugin * plugin)
411 {
412 GstIndexFactory *factory;
413
414 factory = gst_index_factory_new ("memindex",
415 "A index that stores entries in memory", gst_mem_index_get_type ());
416
417 if (factory == NULL) {
418 g_warning ("failed to create memindex factory");
419 return FALSE;
420 }
421
422 GST_PLUGIN_FEATURE (factory)->plugin_name = plugin->desc.name;
423 GST_PLUGIN_FEATURE (factory)->loaded = TRUE;
424
425 gst_registry_add_feature (gst_registry_get_default (),
426 GST_PLUGIN_FEATURE (factory));
427
428 return TRUE;
429 }
430 #endif