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