gststructure: early out when we know a value cannot be a subset
[glsdk/gstreamer0-10.git] / plugins / indexers / gstmemindex.c
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
101   LAST_SIGNAL
102 };
104 enum
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)
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);
141 static void
142 gst_mem_index_init (GstMemIndex * index)
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);
150 static void
151 gst_mem_index_free_format (gpointer key, gpointer value, gpointer user_data)
153   GstMemIndexFormatIndex *index = (GstMemIndexFormatIndex *) value;
155   if (index->tree) {
156     g_tree_destroy (index->tree);
157   }
159   g_slice_free (GstMemIndexFormatIndex, index);
162 static void
163 gst_mem_index_free_id (gpointer key, gpointer value, gpointer user_data)
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);
177 static void
178 gst_mem_index_finalize (GObject * object)
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);
199 static void
200 gst_mem_index_add_id (GstIndex * index, GstIndexEntry * entry)
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   }
216 static gint
217 mem_index_compare (gconstpointer a, gconstpointer b, gpointer user_data)
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));
231 static void
232 gst_mem_index_index_format (GstMemIndexId * id_index, GstIndexEntry * entry,
233     gint assoc)
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);
255 static void
256 gst_mem_index_add_association (GstIndex * index, GstIndexEntry * entry)
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   }
273 static void
274 gst_mem_index_add_object (GstIndex * index, GstIndexEntry * entry)
278 static void
279 gst_mem_index_add_format (GstIndex * index, GstIndexEntry * entry)
283 static void
284 gst_mem_index_add_entry (GstIndex * index, GstIndexEntry * entry)
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   }
306 typedef struct
308   gint64 value;
309   GstMemIndexFormatIndex *index;
310   gboolean exact;
311   GstIndexEntry *lower;
312   gint64 low_diff;
313   GstIndexEntry *higher;
314   gint64 high_diff;
316 GstMemIndexSearchData;
318 static gint
319 mem_index_search (gconstpointer a, gconstpointer b)
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;
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)
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;
424 gboolean
425 gst_mem_index_plugin_init (GstPlugin * plugin)
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;