gst/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  */
  19
  20 #include <gst/gst_private.h>
  21 #include <gst/gstversion.h>
  22 #include <gst/gstplugin.h>
  23 #include <gst/gstindex.h>
  24
  25 #define GST_TYPE_MEM_INDEX              \
  26   (gst_index_get_type ())
  27 #define GST_MEM_INDEX(obj)              \
  28   (G_TYPE_CHECK_INSTANCE_CAST ((obj), GST_TYPE_MEM_INDEX, GstMemIndex))
  29 #define GST_MEM_INDEX_CLASS(klass)      \
  30   (G_TYPE_CHECK_CLASS_CAST ((klass), GST_TYPE_MEM_INDEX, GstMemIndexClass))
  31 #define GST_IS_MEM_INDEX(obj)           \
  32   (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GST_TYPE_MEM_INDEX))
  33 #define GST_IS_MEM_INDEX_CLASS(obj)     \
  34   (GST_TYPE_CHECK_CLASS_TYPE ((klass), GST_TYPE_MEM_INDEX))
  35
  36 /*
  37  * Object model:
  38  *
  39  * All entries are simply added to a GList first. Then we build
  40  * an index to each entry for each id/format
  41  *
  42  *
  43  *  memindex
  44  *    -----------------------------...
  45  *    !                  !
  46  *   id1                 id2
  47  *    ------------
  48  *    !          !
  49  *   format1  format2
  50  *    !          !
  51  *   GTree      GTree
  52  *
  53  *
  54  * The memindex creates a MemIndexId object for each writer id, a
  55  * Hashtable is kept to map the id to the MemIndexId
  56  *
  57  * The MemIndexId keeps a MemIndexFormatIndex for each format the
  58  * specific writer wants indexed.
  59  *
  60  * The MemIndexFormatIndex keeps all the values of the particular
  61  * format in a GTree, The values of the GTree point back to the entry.
  62  *
  63  * Finding a value for an id/format requires locating the correct GTree,
  64  * then do a lookup in the Tree to get the required value.
  65  */
  66
  67 typedef struct {
  68   GstFormat      format;
  69   gint           offset;
  70   GTree         *tree;
  71 } GstMemIndexFormatIndex;
  72
  73 typedef struct {
  74   gint           id;
  75   GHashTable    *format_index;
  76 } GstMemIndexId;
  77
  78 typedef struct _GstMemIndex GstMemIndex;
  79 typedef struct _GstMemIndexClass GstMemIndexClass;
  80
  81 struct _GstMemIndex {
  82   GstIndex               parent;
  83
  84   GList                 *associations;
  85
  86   GHashTable            *id_index;
  87 };
  88
  89 struct _GstMemIndexClass {
  90   GstIndexClass parent_class;
  91 };
  92
  93 /* Index signals and args */
  94 enum {
  95   LAST_SIGNAL
  96 };
  97
  98 enum {
  99   ARG_0,
 100   /* FILL ME */
 101 };
 102
 103 static void             gst_mem_index_class_init        (GstMemIndexClass *klass);
 104 static void             gst_mem_index_init              (GstMemIndex *index);
 105 static void             gst_mem_index_dispose           (GObject *object);
 106
 107 static void             gst_mem_index_add_entry         (GstIndex *index, GstIndexEntry *entry);
 108 static GstIndexEntry*   gst_mem_index_get_assoc_entry   (GstIndex *index, gint id,
 109                                                          GstIndexLookupMethod method, GstAssocFlags flags,
 110                                                          GstFormat format, gint64 value,
 111                                                          GCompareDataFunc func,
 112                                                          gpointer user_data);
 113
 114 #define CLASS(mem_index)  GST_MEM_INDEX_CLASS (G_OBJECT_GET_CLASS (mem_index))
 115
 116 static GstIndex *parent_class = NULL;
 117 /*static guint gst_mem_index_signals[LAST_SIGNAL] = { 0 }; */
 118
 119 GType
 120 gst_mem_index_get_type(void) {
 121   static GType mem_index_type = 0;
 122
 123   if (!mem_index_type) {
 124     static const GTypeInfo mem_index_info = {
 125       sizeof(GstMemIndexClass),
 126       NULL,
 127       NULL,
 128       (GClassInitFunc)gst_mem_index_class_init,
 129       NULL,
 130       NULL,
 131       sizeof(GstMemIndex),
 132       1,
 133       (GInstanceInitFunc)gst_mem_index_init,
 134       NULL
 135     };
 136     mem_index_type = g_type_register_static(GST_TYPE_INDEX, "GstMemIndex", &mem_index_info, 0);
 137   }
 138   return mem_index_type;
 139 }
 140
 141 static void
 142 gst_mem_index_class_init (GstMemIndexClass *klass)
 143 {
 144   GObjectClass *gobject_class;
 145   GstIndexClass *gstindex_class;
 146
 147   gobject_class = (GObjectClass*)klass;
 148   gstindex_class = (GstIndexClass*)klass;
 149
 150   parent_class = g_type_class_ref(GST_TYPE_INDEX);
 151
 152   gobject_class->dispose = gst_mem_index_dispose;
 153
 154   gstindex_class->add_entry       = gst_mem_index_add_entry;
 155   gstindex_class->get_assoc_entry = gst_mem_index_get_assoc_entry;
 156 }
 157
 158 static void
 159 gst_mem_index_init (GstMemIndex *index)
 160 {
 161   GST_DEBUG(0, "created new mem index");
 162
 163   index->associations = NULL;
 164   index->id_index = g_hash_table_new (g_int_hash, g_int_equal);
 165 }
 166
 167 static void
 168 gst_mem_index_dispose (GObject *object)
 169 {
 170   //GstMemIndex *memindex = GST_MEM_INDEX (object);
 171
 172   G_OBJECT_CLASS (parent_class)->dispose (object);
 173 }
 174
 175 static void
 176 gst_mem_index_add_id (GstIndex *index, GstIndexEntry *entry)
 177 {
 178   GstMemIndex *memindex = GST_MEM_INDEX (index);
 179   GstMemIndexId *id_index;
 180
 181   id_index = g_hash_table_lookup (memindex->id_index, &entry->id);
 182
 183   if (!id_index) {
 184     id_index = g_new0 (GstMemIndexId, 1);
 185
 186     id_index->id = entry->id;
 187     id_index->format_index = g_hash_table_new (g_int_hash, g_int_equal);
 188     g_hash_table_insert (memindex->id_index, &entry->id, id_index);
 189   }
 190 }
 191
 192 static gint
 193 mem_index_compare (gconstpointer a,
 194                    gconstpointer b,
 195                    gpointer user_data)
 196 {
 197   GstMemIndexFormatIndex *index = user_data;
 198   gint64 val1, val2;
 199   gint64 diff;
 200
 201   val1 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *)a), index->offset);
 202   val2 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *)b), index->offset);
 203
 204   diff = (val2 - val1);
 205
 206   return (diff == 0 ? 0 : (diff > 0 ? 1 : -1));
 207 }
 208
 209 static void
 210 gst_mem_index_index_format (GstMemIndexId *id_index, GstIndexEntry *entry, gint assoc)
 211 {
 212   GstMemIndexFormatIndex *index;
 213   GstFormat *format;
 214
 215   format = &GST_INDEX_ASSOC_FORMAT (entry, assoc);
 216
 217   index = g_hash_table_lookup (id_index->format_index, format);
 218
 219   if (!index) {
 220     index = g_new0 (GstMemIndexFormatIndex, 1);
 221
 222     index->format = *format;
 223     index->offset = assoc;
 224     index->tree = g_tree_new_with_data (mem_index_compare, index);
 225
 226     g_hash_table_insert (id_index->format_index, format, index);
 227   }
 228
 229   g_tree_insert (index->tree, entry, entry);
 230 }
 231
 232 static void
 233 gst_mem_index_add_association (GstIndex *index, GstIndexEntry *entry)
 234 {
 235   GstMemIndex *memindex = GST_MEM_INDEX (index);
 236   GstMemIndexId *id_index;
 237
 238   memindex->associations = g_list_prepend (memindex->associations, entry);
 239
 240   id_index = g_hash_table_lookup (memindex->id_index, &entry->id);
 241   if (id_index) {
 242     gint i;
 243
 244     for (i = 0; i < GST_INDEX_NASSOCS (entry); i++) {
 245       gst_mem_index_index_format (id_index, entry, i);
 246     }
 247   }
 248 }
 249
 250 static void
 251 gst_mem_index_add_object (GstIndex *index, GstIndexEntry *entry)
 252 {
 253 }
 254
 255 static void
 256 gst_mem_index_add_format (GstIndex *index, GstIndexEntry *entry)
 257 {
 258 }
 259
 260 static void
 261 gst_mem_index_add_entry (GstIndex *index, GstIndexEntry *entry)
 262 {
 263   GstMemIndex *memindex = GST_MEM_INDEX (index);
 264
 265   GST_DEBUG (0, "adding entry %p\n", memindex);
 266
 267   switch (entry->type){
 268      case GST_INDEX_ENTRY_ID:
 269        gst_mem_index_add_id (index, entry);
 270        break;
 271      case GST_INDEX_ENTRY_ASSOCIATION:
 272        gst_mem_index_add_association (index, entry);
 273        break;
 274      case GST_INDEX_ENTRY_OBJECT:
 275        gst_mem_index_add_object (index, entry);
 276        break;
 277      case GST_INDEX_ENTRY_FORMAT:
 278        gst_mem_index_add_format (index, entry);
 279        break;
 280      default:
 281        break;
 282   }
 283 }
 284
 285 typedef struct {
 286   gint64                  value;
 287   GstMemIndexFormatIndex *index;
 288   gboolean                exact;
 289   GstIndexEntry          *lower;
 290   gint64                  low_diff;
 291   GstIndexEntry          *higher;
 292   gint64                  high_diff;
 293 } GstMemIndexSearchData;
 294
 295 static gint
 296 mem_index_search (gconstpointer a,
 297                   gconstpointer b)
 298 {
 299   GstMemIndexSearchData *data = (GstMemIndexSearchData *) b;
 300   GstMemIndexFormatIndex *index = data->index;
 301   gint64 val1, val2;
 302   gint64 diff;
 303
 304   val1 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *)a), index->offset);
 305   val2 = data->value;
 306
 307   diff = (val1 - val2);
 308   if (diff == 0)
 309     return 0;
 310
 311   /* exact matching, don't update low/high */
 312   if (data->exact)
 313     return (diff > 0 ? 1 : -1);
 314
 315   if (diff < 0) {
 316     if (diff > data->low_diff) {
 317       data->low_diff = diff;
 318       data->lower = (GstIndexEntry *) a;
 319     }
 320     diff = -1;
 321   }
 322   else {
 323     if (diff < data->high_diff) {
 324       data->high_diff = diff;
 325       data->higher = (GstIndexEntry *) a;
 326     }
 327     diff = 1;
 328   }
 329
 330   return diff;
 331 }
 332
 333 static GstIndexEntry*
 334 gst_mem_index_get_assoc_entry (GstIndex *index, gint id,
 335                                GstIndexLookupMethod method,
 336                                GstAssocFlags flags,
 337                                GstFormat format, gint64 value,
 338                                GCompareDataFunc func,
 339                                gpointer user_data)
 340 {
 341   GstMemIndex *memindex = GST_MEM_INDEX (index);
 342   GstMemIndexId *id_index;
 343   GstMemIndexFormatIndex *format_index;
 344   GstIndexEntry *entry;
 345   GstMemIndexSearchData data;
 346
 347   id_index = g_hash_table_lookup (memindex->id_index, &id);
 348   if (!id_index)
 349     return NULL;
 350
 351   format_index = g_hash_table_lookup (id_index->format_index, &format);
 352   if (!format_index)
 353     return NULL;
 354
 355   data.value = value;
 356   data.index = format_index;
 357   data.exact = (method == GST_INDEX_LOOKUP_EXACT);
 358
 359   /* setup data for low/high checks if we are not looking
 360    * for an exact match */
 361   if (!data.exact) {
 362     data.low_diff = G_MININT64;
 363     data.lower = NULL;
 364     data.high_diff = G_MAXINT64;
 365     data.higher = NULL;
 366   }
 367
 368   entry = g_tree_search (format_index->tree, mem_index_search, &data);
 369
 370   /* get the low/high values if we're not exact */
 371   if (entry == NULL && !data.exact) {
 372     if (method == GST_INDEX_LOOKUP_BEFORE)
 373       entry = data.lower;
 374     else if (method == GST_INDEX_LOOKUP_AFTER) {
 375       entry = data.higher;
 376     }
 377   }
 378
 379   if (entry) {
 380     if ((GST_INDEX_ASSOC_FLAGS (entry) & flags) != flags) {
 381       GList *l_entry = g_list_find (memindex->associations, entry);
 382
 383       entry = NULL;
 384
 385       while (l_entry) {
 386         entry = (GstIndexEntry *) l_entry->data;
 387
 388         if (entry->id == id &&
 389             (GST_INDEX_ASSOC_FLAGS (entry) & flags) == flags)
 390           break;
 391
 392         if (method == GST_INDEX_LOOKUP_BEFORE)
 393           l_entry = g_list_next (l_entry);
 394         else if (method == GST_INDEX_LOOKUP_AFTER) {
 395           l_entry = g_list_previous (l_entry);
 396         }
 397       }
 398     }
 399   }
 400
 401   return entry;
 402 }
 403
 404 gboolean
 405 gst_mem_index_plugin_init (GModule *module, GstPlugin *plugin)
 406 {
 407   GstIndexFactory *factory;
 408
 409   gst_plugin_set_longname (plugin, "A memory index");
 410
 411   factory = gst_index_factory_new ("memindex",
 412                                    "A index that stores entries in memory",
 413                                    gst_mem_index_get_type());
 414
 415   if (factory != NULL) {
 416     gst_plugin_add_feature (plugin, GST_PLUGIN_FEATURE (factory));
 417   }
 418   else {
 419     g_warning ("could not register memindex");
 420   }
 421   return TRUE;
 422 }