GNOME Bugzilla – Bug 347293
GstValueList comparison is flawed
Last modified: 2006-07-31 16:34:50 UTC
Looking at the code in gstvalue.c, it seems that GstValueLists are considered equal if a) they are the same length b) All items in list A exist in list B. This is faulty if list A contains duplicates. A better algorithm might be: 1. If lists are not the same length, return UNORDERED 2. Copy list B -> B' 3. For each item I in list A: 3a. If I does not exist in B', return UNORDERED 3b. Remove I from B' 4. If B' is not empty, return UNORDERED 5. Return EQUAL
Something like this? /* Do an unordered compare of the contents of a list */ static int gst_value_compare_list (const GValue * value1, const GValue * value2) { guint i, j; GArray *array1 = value1->data[0].v_pointer; GArray *array2 = value2->data[0].v_pointer; GValue *v1; GValue *v2; gint len, to_remove; guint8 *removed; /* get length and do initial length check. */ len = array1->len; if (len != array2->len) return GST_VALUE_UNORDERED; /* place to mark removed value indices of array2 */ removed = g_newa (guint8, len); memset (removed, 0, len); to_remove = len; /* loop over array1, all items should be in array2. When we find an * item in array2, remove it from array2 by marking it as removed */ for (i = 0; i < len; i++) { v1 = &g_array_index (array1, GValue, i); for (j = 0; j < len; j++) { /* item is removed, we can skip it */ if (removed[j]) continue; v2 = &g_array_index (array2, GValue, j); if (gst_value_compare (v1, v2) == GST_VALUE_EQUAL) { /* mark item as removed now that we found it in array2 and * decrement the number of remaining items in array2. */ removed[j] = 1; to_remove--; break; } } /* item in array1 and not in array2, UNORDERED */ if (j == len) return GST_VALUE_UNORDERED; } /* if not all items were removed, array2 contained something not in array1 */ if (to_remove != 0) return GST_VALUE_UNORDERED; /* arrays are equal */ return GST_VALUE_EQUAL; }
* gst/gstvalue.c: (gst_value_compare_list): Fix GstValueList comparison code. Fixes #347293. * tests/check/gst/gstvalue.c: (GST_START_TEST): Check to test GstValueList comparison.