gst/flv/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., 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 typedef GstMemIndex GstFlvDemuxMemIndex;
 108 typedef GstMemIndexClass GstFlvDemuxMemIndexClass;
 109 G_DEFINE_TYPE (GstFlvDemuxMemIndex, gst_mem_index, GST_TYPE_INDEX);
 110
 111 static void
 112 gst_mem_index_class_init (GstMemIndexClass * klass)
 113 {
 114   GObjectClass *gobject_class;
 115   GstIndexClass *gstindex_class;
 116
 117   gobject_class = (GObjectClass *) klass;
 118   gstindex_class = (GstIndexClass *) klass;
 119
 120   gobject_class->finalize = gst_mem_index_finalize;
 121
 122   gstindex_class->add_entry = GST_DEBUG_FUNCPTR (gst_mem_index_add_entry);
 123   gstindex_class->get_assoc_entry =
 124       GST_DEBUG_FUNCPTR (gst_mem_index_get_assoc_entry);
 125 }
 126
 127 static void
 128 gst_mem_index_init (GstMemIndex * index)
 129 {
 130   GST_DEBUG ("created new mem index");
 131
 132   index->associations = NULL;
 133   index->id_index = g_hash_table_new (g_int_hash, g_int_equal);
 134 }
 135
 136 static void
 137 gst_mem_index_free_format (gpointer key, gpointer value, gpointer user_data)
 138 {
 139   GstMemIndexFormatIndex *index = (GstMemIndexFormatIndex *) value;
 140
 141   if (index->tree) {
 142     g_tree_destroy (index->tree);
 143   }
 144
 145   g_slice_free (GstMemIndexFormatIndex, index);
 146 }
 147
 148 static void
 149 gst_mem_index_free_id (gpointer key, gpointer value, gpointer user_data)
 150 {
 151   GstMemIndexId *id_index = (GstMemIndexId *) value;
 152
 153   if (id_index->format_index) {
 154     g_hash_table_foreach (id_index->format_index, gst_mem_index_free_format,
 155         NULL);
 156     g_hash_table_destroy (id_index->format_index);
 157     id_index->format_index = NULL;
 158   }
 159
 160   g_slice_free (GstMemIndexId, id_index);
 161 }
 162
 163 static void
 164 gst_mem_index_finalize (GObject * object)
 165 {
 166   GstMemIndex *memindex = GST_MEM_INDEX (object);
 167
 168   /* Delete the trees referencing the associations first */
 169   if (memindex->id_index) {
 170     g_hash_table_foreach (memindex->id_index, gst_mem_index_free_id, NULL);
 171     g_hash_table_destroy (memindex->id_index);
 172     memindex->id_index = NULL;
 173   }
 174
 175   /* Then delete the associations themselves */
 176   if (memindex->associations) {
 177     g_list_foreach (memindex->associations, (GFunc) gst_index_entry_free, NULL);
 178     g_list_free (memindex->associations);
 179     memindex->associations = NULL;
 180   }
 181
 182   G_OBJECT_CLASS (gst_mem_index_parent_class)->finalize (object);
 183 }
 184
 185 static void
 186 gst_mem_index_add_id (GstIndex * index, GstIndexEntry * entry)
 187 {
 188   GstMemIndex *memindex = GST_MEM_INDEX (index);
 189   GstMemIndexId *id_index;
 190
 191   id_index = g_hash_table_lookup (memindex->id_index, &entry->id);
 192
 193   if (!id_index) {
 194     id_index = g_slice_new0 (GstMemIndexId);
 195
 196     id_index->id = entry->id;
 197     id_index->format_index = g_hash_table_new (g_int_hash, g_int_equal);
 198     g_hash_table_insert (memindex->id_index, &id_index->id, id_index);
 199   }
 200 }
 201
 202 static gint
 203 mem_index_compare (gconstpointer a, gconstpointer b, gpointer user_data)
 204 {
 205   GstMemIndexFormatIndex *index = user_data;
 206   gint64 val1, val2;
 207   gint64 diff;
 208
 209   val1 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *) a), index->offset);
 210   val2 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *) b), index->offset);
 211
 212   diff = (val2 - val1);
 213
 214   return (diff == 0 ? 0 : (diff > 0 ? 1 : -1));
 215 }
 216
 217 static void
 218 gst_mem_index_index_format (GstMemIndexId * id_index, GstIndexEntry * entry,
 219     gint assoc)
 220 {
 221   GstMemIndexFormatIndex *index;
 222   GstFormat *format;
 223
 224   format = &GST_INDEX_ASSOC_FORMAT (entry, assoc);
 225
 226   index = g_hash_table_lookup (id_index->format_index, format);
 227
 228   if (!index) {
 229     index = g_slice_new0 (GstMemIndexFormatIndex);
 230
 231     index->format = *format;
 232     index->offset = assoc;
 233     index->tree = g_tree_new_with_data (mem_index_compare, index);
 234
 235     g_hash_table_insert (id_index->format_index, &index->format, index);
 236   }
 237
 238   g_tree_insert (index->tree, entry, entry);
 239 }
 240
 241 static void
 242 gst_mem_index_add_association (GstIndex * index, GstIndexEntry * entry)
 243 {
 244   GstMemIndex *memindex = GST_MEM_INDEX (index);
 245   GstMemIndexId *id_index;
 246
 247   memindex->associations = g_list_prepend (memindex->associations, entry);
 248
 249   id_index = g_hash_table_lookup (memindex->id_index, &entry->id);
 250   if (id_index) {
 251     gint i;
 252
 253     for (i = 0; i < GST_INDEX_NASSOCS (entry); i++) {
 254       gst_mem_index_index_format (id_index, entry, i);
 255     }
 256   }
 257 }
 258
 259 static void
 260 gst_mem_index_add_object (GstIndex * index, GstIndexEntry * entry)
 261 {
 262 }
 263
 264 static void
 265 gst_mem_index_add_format (GstIndex * index, GstIndexEntry * entry)
 266 {
 267 }
 268
 269 static void
 270 gst_mem_index_add_entry (GstIndex * index, GstIndexEntry * entry)
 271 {
 272   GST_LOG_OBJECT (index, "added this entry");
 273
 274   switch (entry->type) {
 275     case GST_INDEX_ENTRY_ID:
 276       gst_mem_index_add_id (index, entry);
 277       break;
 278     case GST_INDEX_ENTRY_ASSOCIATION:
 279       gst_mem_index_add_association (index, entry);
 280       break;
 281     case GST_INDEX_ENTRY_OBJECT:
 282       gst_mem_index_add_object (index, entry);
 283       break;
 284     case GST_INDEX_ENTRY_FORMAT:
 285       gst_mem_index_add_format (index, entry);
 286       break;
 287     default:
 288       break;
 289   }
 290 }
 291
 292 typedef struct
 293 {
 294   gint64 value;
 295   GstMemIndexFormatIndex *index;
 296   gboolean exact;
 297   GstIndexEntry *lower;
 298   gint64 low_diff;
 299   GstIndexEntry *higher;
 300   gint64 high_diff;
 301 }
 302 GstMemIndexSearchData;
 303
 304 static gint
 305 mem_index_search (gconstpointer a, gconstpointer b)
 306 {
 307   GstMemIndexSearchData *data = (GstMemIndexSearchData *) b;
 308   GstMemIndexFormatIndex *index = data->index;
 309   gint64 val1, val2;
 310   gint64 diff;
 311
 312   val1 = GST_INDEX_ASSOC_VALUE (((GstIndexEntry *) a), index->offset);
 313   val2 = data->value;
 314
 315   diff = (val1 - val2);
 316   if (diff == 0)
 317     return 0;
 318
 319   /* exact matching, don't update low/high */
 320   if (data->exact)
 321     return (diff > 0 ? 1 : -1);
 322
 323   if (diff < 0) {
 324     if (diff > data->low_diff) {
 325       data->low_diff = diff;
 326       data->lower = (GstIndexEntry *) a;
 327     }
 328     diff = -1;
 329   } else {
 330     if (diff < data->high_diff) {
 331       data->high_diff = diff;
 332       data->higher = (GstIndexEntry *) a;
 333     }
 334     diff = 1;
 335   }
 336
 337   return diff;
 338 }
 339
 340 static GstIndexEntry *
 341 gst_mem_index_get_assoc_entry (GstIndex * index, gint id,
 342     GstIndexLookupMethod method,
 343     GstIndexAssociationFlags flags,
 344     GstFormat format, gint64 value, GCompareDataFunc func, gpointer user_data)
 345 {
 346   GstMemIndex *memindex = GST_MEM_INDEX (index);
 347   GstMemIndexId *id_index;
 348   GstMemIndexFormatIndex *format_index;
 349   GstIndexEntry *entry;
 350   GstMemIndexSearchData data;
 351
 352   id_index = g_hash_table_lookup (memindex->id_index, &id);
 353   if (!id_index)
 354     return NULL;
 355
 356   format_index = g_hash_table_lookup (id_index->format_index, &format);
 357   if (!format_index)
 358     return NULL;
 359
 360   data.value = value;
 361   data.index = format_index;
 362   data.exact = (method == GST_INDEX_LOOKUP_EXACT);
 363
 364   /* setup data for low/high checks if we are not looking
 365    * for an exact match */
 366   if (!data.exact) {
 367     data.low_diff = G_MININT64;
 368     data.lower = NULL;
 369     data.high_diff = G_MAXINT64;
 370     data.higher = NULL;
 371   }
 372
 373   entry = g_tree_search (format_index->tree, mem_index_search, &data);
 374
 375   /* get the low/high values if we're not exact */
 376   if (entry == NULL && !data.exact) {
 377     if (method == GST_INDEX_LOOKUP_BEFORE)
 378       entry = data.lower;
 379     else if (method == GST_INDEX_LOOKUP_AFTER) {
 380       entry = data.higher;
 381     }
 382   }
 383
 384   if (entry && ((GST_INDEX_ASSOC_FLAGS (entry) & flags) != flags)) {
 385     if (method != GST_INDEX_LOOKUP_EXACT) {
 386       GList *l_entry = g_list_find (memindex->associations, entry);
 387
 388       entry = NULL;
 389
 390       while (l_entry) {
 391         entry = (GstIndexEntry *) l_entry->data;
 392
 393         if (entry->id == id && (GST_INDEX_ASSOC_FLAGS (entry) & flags) == flags)
 394           break;
 395
 396         if (method == GST_INDEX_LOOKUP_BEFORE)
 397           l_entry = g_list_next (l_entry);
 398         else if (method == GST_INDEX_LOOKUP_AFTER) {
 399           l_entry = g_list_previous (l_entry);
 400         }
 401       }
 402     } else {
 403       entry = NULL;
 404     }
 405   }
 406
 407   return entry;
 408 }
 409
 410 #if 0
 411 gboolean
 412 gst_mem_index_plugin_init (GstPlugin * plugin)
 413 {
 414   GstIndexFactory *factory;
 415
 416   factory = gst_index_factory_new ("memindex",
 417       "A index that stores entries in memory", gst_mem_index_get_type ());
 418
 419   if (factory == NULL) {
 420     g_warning ("failed to create memindex factory");
 421     return FALSE;
 422   }
 423
 424   GST_PLUGIN_FEATURE (factory)->plugin_name = plugin->desc.name;
 425   GST_PLUGIN_FEATURE (factory)->loaded = TRUE;
 426
 427   gst_registry_add_feature (gst_registry_get_default (),
 428       GST_PLUGIN_FEATURE (factory));
 429
 430   return TRUE;
 431 }
 432 #endif