1 /* GStreamer
2 * Copyright (C) <1999> Erik Walthinsen <omega@cse.ogi.edu>
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., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
18 */
20 #include <gst/gst.h>
22 #include "gstindexers.h"
24 #define GST_TYPE_MEM_INDEX \
25 (gst_index_get_type ())
26 #define GST_MEM_INDEX(obj) \
27 (G_TYPE_CHECK_INSTANCE_CAST ((obj), GST_TYPE_MEM_INDEX, GstMemIndex))
28 #define GST_MEM_INDEX_CLASS(klass) \
29 (G_TYPE_CHECK_CLASS_CAST ((klass), GST_TYPE_MEM_INDEX, GstMemIndexClass))
30 #define GST_IS_MEM_INDEX(obj) \
31 (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GST_TYPE_MEM_INDEX))
32 #define GST_IS_MEM_INDEX_CLASS(klass) \
33 (GST_TYPE_CHECK_CLASS_TYPE ((klass), GST_TYPE_MEM_INDEX))
35 /*
36 * Object model:
37 *
38 * All entries are simply added to a GList first. Then we build
39 * an index to each entry for each id/format
40 *
41 *
42 * memindex
43 * -----------------------------...
44 * ! !
45 * id1 id2
46 * ------------
47 * ! !
48 * format1 format2
49 * ! !
50 * GTree GTree
51 *
52 *
53 * The memindex creates a MemIndexId object for each writer id, a
54 * Hashtable is kept to map the id to the MemIndexId
55 *
56 * The MemIndexId keeps a MemIndexFormatIndex for each format the
57 * specific writer wants indexed.
58 *
59 * The MemIndexFormatIndex keeps all the values of the particular
60 * format in a GTree, The values of the GTree point back to the entry.
61 *
62 * Finding a value for an id/format requires locating the correct GTree,
63 * then do a lookup in the Tree to get the required value.
64 */
66 typedef struct
67 {
68 GstFormat format;
69 gint offset;
70 GTree *tree;
71 }
72 GstMemIndexFormatIndex;
74 typedef struct
75 {
76 gint id;
77 GHashTable *format_index;
78 }
79 GstMemIndexId;
81 typedef struct _GstMemIndex GstMemIndex;
82 typedef struct _GstMemIndexClass GstMemIndexClass;
84 struct _GstMemIndex
85 {
86 GstIndex parent;
88 GList *associations;
90 GHashTable *id_index;
91 };
93 struct _GstMemIndexClass
94 {
95 GstIndexClass parent_class;
96 };
98 /* Index signals and args */
99 enum
100 {
101 LAST_SIGNAL
102 };
104 enum
105 {
106 ARG_0,
107 /* FILL ME */
108 };
110 static void gst_mem_index_finalize (GObject * object);
112 static void gst_mem_index_add_entry (GstIndex * index, GstIndexEntry * entry);
113 static GstIndexEntry *gst_mem_index_get_assoc_entry (GstIndex * index, gint id,
114 GstIndexLookupMethod method, GstAssocFlags flags,
115 GstFormat format, gint64 value, GCompareDataFunc func, gpointer user_data);
117 #define CLASS(mem_index) GST_MEM_INDEX_CLASS (G_OBJECT_GET_CLASS (mem_index))
119 /*static guint gst_mem_index_signals[LAST_SIGNAL] = { 0 }; */
121 GType gst_mem_index_get_type (void);
123 G_DEFINE_TYPE (GstMemIndex, gst_mem_index, GST_TYPE_INDEX);
125 static void
126 gst_mem_index_class_init (GstMemIndexClass * klass)
127 {
128 GObjectClass *gobject_class;
129 GstIndexClass *gstindex_class;
131 gobject_class = (GObjectClass *) klass;
132 gstindex_class = (GstIndexClass *) klass;
134 gobject_class->finalize = gst_mem_index_finalize;
136 gstindex_class->add_entry = GST_DEBUG_FUNCPTR (gst_mem_index_add_entry);
137 gstindex_class->get_assoc_entry =
138 GST_DEBUG_FUNCPTR (gst_mem_index_get_assoc_entry);
139 }
141 static void
142 gst_mem_index_init (GstMemIndex * index)
143 {
144 GST_DEBUG ("created new mem index");
146 index->associations = NULL;
147 index->id_index = g_hash_table_new (g_int_hash, g_int_equal);
148 }
150 static void
151 gst_mem_index_free_format (gpointer key, gpointer value, gpointer user_data)
152 {
153 GstMemIndexFormatIndex *index = (GstMemIndexFormatIndex *) value;
155 if (index->tree) {
156 g_tree_destroy (index->tree);
157 }
159 g_slice_free (GstMemIndexFormatIndex, index);
160 }
162 static void
163 gst_mem_index_free_id (gpointer key, gpointer value, gpointer user_data)
164 {
165 GstMemIndexId *id_index = (GstMemIndexId *) value;
167 if (id_index->format_index) {
168 g_hash_table_foreach (id_index->format_index, gst_mem_index_free_format,
169 NULL);
170 g_hash_table_destroy (id_index->format_index);
171 id_index->format_index = NULL;
172 }
174 g_slice_free (GstMemIndexId, id_index);
175 }
177 static void
178 gst_mem_index_finalize (GObject * object)
179 {
180 GstMemIndex *memindex = GST_MEM_INDEX (object);
182 /* Delete the trees referencing the associations first */
183 if (memindex->id_index) {
184 g_hash_table_foreach (memindex->id_index, gst_mem_index_free_id, NULL);
185 g_hash_table_destroy (memindex->id_index);
186 memindex->id_index = NULL;
187 }
189 /* Then delete the associations themselves */
190 if (memindex->associations) {
191 g_list_foreach (memindex->associations, (GFunc) gst_index_entry_free, NULL);
192 g_list_free (memindex->associations);
193 memindex->associations = NULL;
194 }
196 G_OBJECT_CLASS (gst_mem_index_parent_class)->finalize (object);
197 }
199 static void
200 gst_mem_index_add_id (GstIndex * index, GstIndexEntry * entry)
201 {
202 GstMemIndex *memindex = GST_MEM_INDEX (index);
203 GstMemIndexId *id_index;
205 id_index = g_hash_table_lookup (memindex->id_index, &entry->id);
207 if (!id_index) {
208 id_index = g_slice_new0 (GstMemIndexId);
210 id_index->id = entry->id;
211 id_index->format_index = g_hash_table_new (g_int_hash, g_int_equal);
212 g_hash_table_insert (memindex->id_index, &id_index->id, id_index);
213 }
214 }
216 static gint
217 mem_index_compare (gconstpointer a, gconstpointer b, gpointer user_data)
218 {
219 GstMemIndexFormatIndex *index = user_data;
220 gint64 val1, val2;
221 gint64 diff;
223 val1 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *) a), index->offset);
224 val2 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *) b), index->offset);
226 diff = (val2 - val1);
228 return (diff == 0 ? 0 : (diff > 0 ? 1 : -1));
229 }
231 static void
232 gst_mem_index_index_format (GstMemIndexId * id_index, GstIndexEntry * entry,
233 gint assoc)
234 {
235 GstMemIndexFormatIndex *index;
236 GstFormat *format;
238 format = &GST_INDEX_ASSOC_FORMAT (entry, assoc);
240 index = g_hash_table_lookup (id_index->format_index, format);
242 if (!index) {
243 index = g_slice_new0 (GstMemIndexFormatIndex);
245 index->format = *format;
246 index->offset = assoc;
247 index->tree = g_tree_new_with_data (mem_index_compare, index);
249 g_hash_table_insert (id_index->format_index, &index->format, index);
250 }
252 g_tree_insert (index->tree, entry, entry);
253 }
255 static void
256 gst_mem_index_add_association (GstIndex * index, GstIndexEntry * entry)
257 {
258 GstMemIndex *memindex = GST_MEM_INDEX (index);
259 GstMemIndexId *id_index;
261 memindex->associations = g_list_prepend (memindex->associations, entry);
263 id_index = g_hash_table_lookup (memindex->id_index, &entry->id);
264 if (id_index) {
265 gint i;
267 for (i = 0; i < GST_INDEX_NASSOCS (entry); i++) {
268 gst_mem_index_index_format (id_index, entry, i);
269 }
270 }
271 }
273 static void
274 gst_mem_index_add_object (GstIndex * index, GstIndexEntry * entry)
275 {
276 }
278 static void
279 gst_mem_index_add_format (GstIndex * index, GstIndexEntry * entry)
280 {
281 }
283 static void
284 gst_mem_index_add_entry (GstIndex * index, GstIndexEntry * entry)
285 {
286 GST_LOG_OBJECT (index, "added this entry");
288 switch (entry->type) {
289 case GST_INDEX_ENTRY_ID:
290 gst_mem_index_add_id (index, entry);
291 break;
292 case GST_INDEX_ENTRY_ASSOCIATION:
293 gst_mem_index_add_association (index, entry);
294 break;
295 case GST_INDEX_ENTRY_OBJECT:
296 gst_mem_index_add_object (index, entry);
297 break;
298 case GST_INDEX_ENTRY_FORMAT:
299 gst_mem_index_add_format (index, entry);
300 break;
301 default:
302 break;
303 }
304 }
306 typedef struct
307 {
308 gint64 value;
309 GstMemIndexFormatIndex *index;
310 gboolean exact;
311 GstIndexEntry *lower;
312 gint64 low_diff;
313 GstIndexEntry *higher;
314 gint64 high_diff;
315 }
316 GstMemIndexSearchData;
318 static gint
319 mem_index_search (gconstpointer a, gconstpointer b)
320 {
321 GstMemIndexSearchData *data = (GstMemIndexSearchData *) b;
322 GstMemIndexFormatIndex *index = data->index;
323 gint64 val1, val2;
324 gint64 diff;
326 val1 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *) a), index->offset);
327 val2 = data->value;
329 diff = (val1 - val2);
330 if (diff == 0)
331 return 0;
333 /* exact matching, don't update low/high */
334 if (data->exact)
335 return (diff > 0 ? 1 : -1);
337 if (diff < 0) {
338 if (diff > data->low_diff) {
339 data->low_diff = diff;
340 data->lower = (GstIndexEntry *) a;
341 }
342 diff = -1;
343 } else {
344 if (diff < data->high_diff) {
345 data->high_diff = diff;
346 data->higher = (GstIndexEntry *) a;
347 }
348 diff = 1;
349 }
351 return diff;
352 }
354 static GstIndexEntry *
355 gst_mem_index_get_assoc_entry (GstIndex * index, gint id,
356 GstIndexLookupMethod method,
357 GstAssocFlags flags,
358 GstFormat format, gint64 value, GCompareDataFunc func, gpointer user_data)
359 {
360 GstMemIndex *memindex = GST_MEM_INDEX (index);
361 GstMemIndexId *id_index;
362 GstMemIndexFormatIndex *format_index;
363 GstIndexEntry *entry;
364 GstMemIndexSearchData data;
366 id_index = g_hash_table_lookup (memindex->id_index, &id);
367 if (!id_index)
368 return NULL;
370 format_index = g_hash_table_lookup (id_index->format_index, &format);
371 if (!format_index)
372 return NULL;
374 data.value = value;
375 data.index = format_index;
376 data.exact = (method == GST_INDEX_LOOKUP_EXACT);
378 /* setup data for low/high checks if we are not looking
379 * for an exact match */
380 if (!data.exact) {
381 data.low_diff = G_MININT64;
382 data.lower = NULL;
383 data.high_diff = G_MAXINT64;
384 data.higher = NULL;
385 }
387 entry = g_tree_search (format_index->tree, mem_index_search, &data);
389 /* get the low/high values if we're not exact */
390 if (entry == NULL && !data.exact) {
391 if (method == GST_INDEX_LOOKUP_BEFORE)
392 entry = data.lower;
393 else if (method == GST_INDEX_LOOKUP_AFTER) {
394 entry = data.higher;
395 }
396 }
398 if (entry && ((GST_INDEX_ASSOC_FLAGS (entry) & flags) != flags)) {
399 if (method != GST_INDEX_LOOKUP_EXACT) {
400 GList *l_entry = g_list_find (memindex->associations, entry);
402 entry = NULL;
404 while (l_entry) {
405 entry = (GstIndexEntry *) l_entry->data;
407 if (entry->id == id && (GST_INDEX_ASSOC_FLAGS (entry) & flags) == flags)
408 break;
410 if (method == GST_INDEX_LOOKUP_BEFORE)
411 l_entry = g_list_next (l_entry);
412 else if (method == GST_INDEX_LOOKUP_AFTER) {
413 l_entry = g_list_previous (l_entry);
414 }
415 }
416 } else {
417 entry = NULL;
418 }
419 }
421 return entry;
422 }
424 gboolean
425 gst_mem_index_plugin_init (GstPlugin * plugin)
426 {
427 GstIndexFactory *factory;
429 factory = gst_index_factory_new ("memindex",
430 "A index that stores entries in memory", gst_mem_index_get_type ());
432 if (factory == NULL) {
433 g_warning ("failed to create memindex factory");
434 return FALSE;
435 }
437 GST_PLUGIN_FEATURE (factory)->plugin_name = plugin->desc.name;
438 GST_PLUGIN_FEATURE (factory)->loaded = TRUE;
440 gst_registry_add_feature (gst_registry_get_default (),
441 GST_PLUGIN_FEATURE (factory));
443 return TRUE;
444 }