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  */
  19
  20 #include <gst/gst.h>
  21
  22 #include "gstindexers.h"
  23
  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))
  34
  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  */
  65
  66 typedef struct
  67 {
  68   GstFormat format;
  69   gint offset;
  70   GTree *tree;
  71 }
  72 GstMemIndexFormatIndex;
  73
  74 typedef struct
  75 {
  76   gint id;
  77   GHashTable *format_index;
  78 }
  79 GstMemIndexId;
  80
  81 typedef struct _GstMemIndex GstMemIndex;
  82 typedef struct _GstMemIndexClass GstMemIndexClass;
  83
  84 struct _GstMemIndex
  85 {
  86   GstIndex parent;
  87
  88   GList *associations;
  89
  90   GHashTable *id_index;
  91 };
  92
  93 struct _GstMemIndexClass
  94 {
  95   GstIndexClass parent_class;
  96 };
  97
  98 /* Index signals and args */
  99 enum
 100 {
 101   LAST_SIGNAL
 102 };
 103
 104 enum
 105 {
 106   ARG_0,
 107   /* FILL ME */
 108 };
 109
 110 static void gst_mem_index_finalize (GObject * object);
 111
 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);
 116
 117 #define CLASS(mem_index)  GST_MEM_INDEX_CLASS (G_OBJECT_GET_CLASS (mem_index))
 118
 119 /*static guint gst_mem_index_signals[LAST_SIGNAL] = { 0 }; */
 120
 121 GType gst_mem_index_get_type (void);
 122
 123 G_DEFINE_TYPE (GstMemIndex, gst_mem_index, GST_TYPE_INDEX);
 124
 125 static void
 126 gst_mem_index_class_init (GstMemIndexClass * klass)
 127 {
 128   GObjectClass *gobject_class;
 129   GstIndexClass *gstindex_class;
 130
 131   gobject_class = (GObjectClass *) klass;
 132   gstindex_class = (GstIndexClass *) klass;
 133
 134   gobject_class->finalize = gst_mem_index_finalize;
 135
 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 }
 140
 141 static void
 142 gst_mem_index_init (GstMemIndex * index)
 143 {
 144   GST_DEBUG ("created new mem index");
 145
 146   index->associations = NULL;
 147   index->id_index = g_hash_table_new (g_int_hash, g_int_equal);
 148 }
 149
 150 static void
 151 gst_mem_index_free_format (gpointer key, gpointer value, gpointer user_data)
 152 {
 153   GstMemIndexFormatIndex *index = (GstMemIndexFormatIndex *) value;
 154
 155   if (index->tree) {
 156     g_tree_destroy (index->tree);
 157   }
 158
 159   g_slice_free (GstMemIndexFormatIndex, index);
 160 }
 161
 162 static void
 163 gst_mem_index_free_id (gpointer key, gpointer value, gpointer user_data)
 164 {
 165   GstMemIndexId *id_index = (GstMemIndexId *) value;
 166
 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   }
 173
 174   g_slice_free (GstMemIndexId, id_index);
 175 }
 176
 177 static void
 178 gst_mem_index_finalize (GObject * object)
 179 {
 180   GstMemIndex *memindex = GST_MEM_INDEX (object);
 181
 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   }
 188
 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   }
 195
 196   G_OBJECT_CLASS (gst_mem_index_parent_class)->finalize (object);
 197 }
 198
 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;
 204
 205   id_index = g_hash_table_lookup (memindex->id_index, &entry->id);
 206
 207   if (!id_index) {
 208     id_index = g_slice_new0 (GstMemIndexId);
 209
 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 }
 215
 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;
 222
 223   val1 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *) a), index->offset);
 224   val2 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *) b), index->offset);
 225
 226   diff = (val2 - val1);
 227
 228   return (diff == 0 ? 0 : (diff > 0 ? 1 : -1));
 229 }
 230
 231 static void
 232 gst_mem_index_index_format (GstMemIndexId * id_index, GstIndexEntry * entry,
 233     gint assoc)
 234 {
 235   GstMemIndexFormatIndex *index;
 236   GstFormat *format;
 237
 238   format = &GST_INDEX_ASSOC_FORMAT (entry, assoc);
 239
 240   index = g_hash_table_lookup (id_index->format_index, format);
 241
 242   if (!index) {
 243     index = g_slice_new0 (GstMemIndexFormatIndex);
 244
 245     index->format = *format;
 246     index->offset = assoc;
 247     index->tree = g_tree_new_with_data (mem_index_compare, index);
 248
 249     g_hash_table_insert (id_index->format_index, &index->format, index);
 250   }
 251
 252   g_tree_insert (index->tree, entry, entry);
 253 }
 254
 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;
 260
 261   memindex->associations = g_list_prepend (memindex->associations, entry);
 262
 263   id_index = g_hash_table_lookup (memindex->id_index, &entry->id);
 264   if (id_index) {
 265     gint i;
 266
 267     for (i = 0; i < GST_INDEX_NASSOCS (entry); i++) {
 268       gst_mem_index_index_format (id_index, entry, i);
 269     }
 270   }
 271 }
 272
 273 static void
 274 gst_mem_index_add_object (GstIndex * index, GstIndexEntry * entry)
 275 {
 276 }
 277
 278 static void
 279 gst_mem_index_add_format (GstIndex * index, GstIndexEntry * entry)
 280 {
 281 }
 282
 283 static void
 284 gst_mem_index_add_entry (GstIndex * index, GstIndexEntry * entry)
 285 {
 286   GST_LOG_OBJECT (index, "added this entry");
 287
 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 }
 305
 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;
 317
 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;
 325
 326   val1 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *) a), index->offset);
 327   val2 = data->value;
 328
 329   diff = (val1 - val2);
 330   if (diff == 0)
 331     return 0;
 332
 333   /* exact matching, don't update low/high */
 334   if (data->exact)
 335     return (diff > 0 ? 1 : -1);
 336
 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   }
 350
 351   return diff;
 352 }
 353
 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;
 365
 366   id_index = g_hash_table_lookup (memindex->id_index, &id);
 367   if (!id_index)
 368     return NULL;
 369
 370   format_index = g_hash_table_lookup (id_index->format_index, &format);
 371   if (!format_index)
 372     return NULL;
 373
 374   data.value = value;
 375   data.index = format_index;
 376   data.exact = (method == GST_INDEX_LOOKUP_EXACT);
 377
 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   }
 386
 387   entry = g_tree_search (format_index->tree, mem_index_search, &data);
 388
 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   }
 397
 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);
 401
 402       entry = NULL;
 403
 404       while (l_entry) {
 405         entry = (GstIndexEntry *) l_entry->data;
 406
 407         if (entry->id == id && (GST_INDEX_ASSOC_FLAGS (entry) & flags) == flags)
 408           break;
 409
 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   }
 420
 421   return entry;
 422 }
 423
 424 gboolean
 425 gst_mem_index_plugin_init (GstPlugin * plugin)
 426 {
 427   GstIndexFactory *factory;
 428
 429   factory = gst_index_factory_new ("memindex",
 430       "A index that stores entries in memory", gst_mem_index_get_type ());
 431
 432   if (factory == NULL) {
 433     g_warning ("failed to create memindex factory");
 434     return FALSE;
 435   }
 436
 437   GST_PLUGIN_FEATURE (factory)->plugin_name = plugin->desc.name;
 438   GST_PLUGIN_FEATURE (factory)->loaded = TRUE;
 439
 440   gst_registry_add_feature (gst_registry_get_default (),
 441       GST_PLUGIN_FEATURE (factory));
 442
 443   return TRUE;
 444 }