Changeset 116

Timestamp:

01/11/05 19:33:39 (4 years ago)

Author:

ehabkost

Message:

- Refactored the path search function:

• Made it try to use non-lossy converters and not change objtypes, added tests for these cases
• Made it call the converters to get the converted data only if it is necessary to run a detector on the data

Location:

trunk

Files:

• plugins/evolution2_sync/src (modified) (1 prop)
• src/opensync_convert.c (modified) (8 diffs)
• tests/check_conv.c (modified) (2 diffs)

trunk/plugins/evolution2_sync/src

@@ -5 +5 @@
 .libs
 .deps
+evolution_sync.loT

@@ -5 +5 @@
 .libs
 .deps
+evolution_sync.loT

trunk/src/opensync_convert.c

@@ -567 +567 @@
         char *origdata;
         size_t origsize;
+        osync_debug("OSFRM", 4, "Invoking converter to cheap conversion: %s -> %s",
+                        converter->source_format->name, converter->target_format->name);
+
         /* Duplicate the data, if the converter will take it to himself */
         if (converter->flags & CONV_TAKEOVER) {
                 if (!converter->source_format->copy_func) {
-                        osync_debug("OSFRM", 0, "Converter %s->%s is CONV_TAKEOVER, but no copy_func", converter->source_format, converter->target_format);
+                        osync_debug("OSFRM", 0, "Converter %s->%s is CONV_TAKEOVER, but no copy_func", converter->source_format->name, converter->target_format->name);
                         return FALSE;
                 }
@@ -661 +664 @@
 }
 
-typedef struct edge {
+typedef struct vertice {
         OSyncObjFormat *format;
 
@@ -675 +678 @@
         /** @} */
 
-        /* Keep reference counts because
+        /** The converter that needs to be run
+         * on previous->data to get the
+         * vertice data
+         */
+        OSyncFormatConverter *converter;
+
+        /** Keep reference counts because
          * the data returned by converters
          * can be references to other data,
          * and we can't free them too early
+         */
+        size_t references;
+
+        /** A reference to the previous vertice
+         * on the path
          *
+         * Used when a conversion is necessary
+         */
+        struct vertice *previous;
+
+        /** The path of converters */
+        GList *path;
+
+        /** Distance data
          * @{
          */
-        struct edge *referenced_data;
-        size_t references;
+        unsigned losses;
+        unsigned objtype_changes;
+        unsigned conversions;
         /** @} */
 
-        /** The path of converters */
-        GList *path;
-
-} edge;
+} vertice;
+
+/** Compare the distance of two vertices
+ *
+ * First, try to minimize the losses. Then,
+ * try to minimize the conversions between
+ * different objtypes. Then, try to minimize
+ * the total number of conversions.
+ */
+int compare_vertice_distance(const void *a, const void *b)
+{
+        const vertice *va = a;
+        const vertice *vb = b;
+        if (va->losses < vb->losses)
+                return -1;
+        else if (va->losses > vb->losses)
+                return 1;
+        else if (va->objtype_changes < vb->objtype_changes)
+                return -1;
+        else if (va->objtype_changes > vb->objtype_changes)
+                return 1;
+        else if (va->conversions < vb->conversions)
+                return -1;
+        else if (va->conversions > vb->conversions)
+                return 1;
+        else
+                return 0;
+}
 
 typedef struct conv_tree {
@@ -701 +748 @@
 } conv_tree;
 
-edge *get_next_edge_neighbour(OSyncFormatEnv *env, conv_tree *tree, edge *me)
+
+/** Increment a vertice reference count */
+static void ref_vertice(vertice *v)
+{
+        v->references++;
+}
+
+/** Dereference an vertice
+ */
+static void deref_vertice(vertice *vertice)
+{
+        /* Decrement the reference count,
+         * and just return if we still
+         * have a reference
+         */
+        if (--vertice->references > 0)
+                return;
+
+        g_list_free(vertice->path);
+        if (vertice->free_data) {
+                if (!vertice->format->destroy_func)
+                        osync_debug("OSFRM", 1, "Memory leak: can't free data of type %s", vertice->format->name);
+                else {
+                        osync_debug("OSFRM", 4, "Freeing data of type %s", vertice->format->name);
+                        vertice->format->destroy_func(vertice->data, vertice->datasize);
+                }
+        }
+        /* Drop the v->previous reference */
+        if (vertice->previous)
+                deref_vertice(vertice->previous);
+        g_free(vertice);
+}
+
+osync_bool calc_vertice_data(vertice *v)
+{
+        g_assert(v);
+
+        /* The data was already calculated */
+        if (v->data) return TRUE;
+
+        /* Ask the previous vertice to calculate its data, too.
+         *
+         * FIXME: Remove recursive call. It doesn't do too much harm,
+         * but it is better to avoid it
+         */
+        calc_vertice_data(v->previous);
+
+        /* Convert the data, trying to keep references, not copies */
+        osync_cheap_convert(v->converter, v->previous->data, v->previous->datasize, &v->data, &v->datasize, &v->free_data);
+
+        /* Keep references to old data, if we have done a 'nocopy'
+         * conversion.
+         *
+         * free_data == 0 means that the returned data is a reference
+         * to the original data.
+         *
+         * So, the reference on v->previous will be kept, if
+         * free_data == 0. Otherwise, drop the reference.
+         */
+        if (v->free_data) {
+                deref_vertice(v->previous);
+                v->previous = NULL;
+        }
+
+        return TRUE;
+}
+
+/** Returns a neighbour of the vertice ve
+ *
+ * Returns a new reference to te vertice. The reference
+ * should be dropped using deref_vertice(), later.
+ */
+vertice *get_next_vertice_neighbour(OSyncFormatEnv *env, conv_tree *tree, vertice *ve)
 {
         GList *c = NULL;
         OSyncObjFormat *detected_fmt = NULL;
-        if (me->format->detect_func)
-                me->format->detect_func(env, me->data, me->datasize, &detected_fmt);
+
+        if (ve->format->detect_func) {
+                calc_vertice_data(ve);
+                ve->format->detect_func(env, ve->data, ve->datasize, &detected_fmt);
+        }
                 
         for (c = tree->unused; c; c = c->next) {
@@ -713 +835 @@
                 
                 /* Check only valid converters, from the right format */
-                if (strcmp(converter->source_format->name, me->format->name))
+                if (strcmp(converter->source_format->name, ve->format->name))
                         continue;
 
@@ -734 +856 @@
                                 }
                                 /* Call the detector, and don't use the converter, if it returns FALSE */
-                                if (!det->detect_func(env, me->data, me->datasize))
+                                calc_vertice_data(ve);
+                                if (!det->detect_func(env, ve->data, ve->datasize))
                                         continue;
                         } else {
@@ -744 +867 @@
                         }
                 }
+
+
+                /* From this point, we already found an edge (i.e. a converter) that may
+                 * be used
+                 */
+
+                /* Remove the converter from the unused list */
                 tree->unused = g_list_remove(tree->unused, converter);
-                edge *neighbour = g_malloc0(sizeof(edge));
+
+                /* Allocate the new neighbour */
+                vertice *neigh = g_malloc0(sizeof(vertice));
                 /* Start with a reference count = 1 */
-                neighbour->references = 1;
-                neighbour->format = fmt_target;
-                neighbour->path = g_list_copy(me->path);
-                neighbour->path = g_list_append(neighbour->path, converter);
-
-                /* Convert the data, trying to keep references, not copies */
-                /*FIXME: we may convert only if we need to run a detector */
-                osync_cheap_convert(converter, me->data, me->datasize, &neighbour->data, &neighbour->datasize, &neighbour->free_data);
-                /* Keep references to old data, to avoid
-                 * destroying the edges that have
-                 * references to their data
+                neigh->references = 1;
+                neigh->converter = converter;
+                neigh->format = fmt_target;
+                neigh->path = g_list_copy(ve->path);
+                neigh->path = g_list_append(neigh->path, converter);
+
+                /* Distance calculation */
+                neigh->conversions = ve->conversions + 1;
+                neigh->losses = ve->losses;
+                if (!(converter->flags & CONV_NOTLOSSY))
+                        neigh->losses++;
+                neigh->objtype_changes = ve->objtype_changes;
+                if (converter->source_format->objtype != converter->target_format->objtype)
+                        neigh->objtype_changes++;
+
+                /* Keep the reference to the previous vertice, as we may need
+                 * its data later
                  */
-                if (!neighbour->free_data) {
-                        /* !free_data means that the returned data is a reference */
-                        me->references++;
-                        neighbour->referenced_data = me;
-                }
-                return neighbour;
+                ref_vertice(ve);
+                neigh->previous = ve;
+
+                return neigh;
         }
         return NULL;
 }
 
-/** Dereference an edge
- */
-void put_edge(edge *edge)
-{
-        /* Decrement the reference count,
-         * and just return if we still
-         * have a reference
-         */
-        if (--edge->references > 0)
-                return;
-
-        g_list_free(edge->path);
-        if (edge->free_data) {
-                if (!edge->format->destroy_func)
-                        osync_debug("OSFRM", 1, "Memory leak: can't free data of type %s", edge->format->name);
-                else {
-                        osync_debug("OSFRM", 4, "Freeing data of type %s", edge->format->name);
-                        edge->format->destroy_func(edge->data, edge->datasize);
-                }
-        }
-        if (edge->referenced_data)
-                /* We are not referencing the data of another edge, anymore */
-                put_edge(edge->referenced_data);
-        g_free(edge);
-}
-
+/*TODO: make the path search function work in a
+ * find-path-to-objtype mode, that will be used for detection:
+ * The only change is: instead of using osync_conv_fmt_in_list(current->format, targets),
+ * stop when the objtype of the vertice is different than the original
+ * objtype.
+ *
+ * Maybe we can have a validate_vertice_fn parameter, a function that would 
+ * be called to check if a vertice is 'final' or not.
+ */
 osync_bool osync_conv_find_shortest_path(OSyncFormatEnv *env, GList *vertices, OSyncChange *start, GList/*OSyncObjFormat * */ *targets, GList **retlist)
 {       
@@ -800 +919 @@
         osync_bool ret = FALSE;
         conv_tree *tree = g_malloc0(sizeof(conv_tree));
+
         tree->unused = g_list_copy(vertices);
-        edge *current = g_malloc0(sizeof(edge));
-
-        edge *neighbour = NULL;
-        current->format = osync_change_get_objformat(start);
-        current->path = NULL;
-        current->data = start->data;
-        current->datasize = start->size;
-        current->free_data = FALSE;
-        current->references = 1;
-        
-        while (g_list_length(tree->unused) || g_list_length(tree->search)) {
-                osync_debug("OSFRM", 4, "Searching %s neighbours", current->format->name);
-                while ((neighbour = get_next_edge_neighbour(env, tree, current))) {
+
+        vertice *result = NULL;
+        vertice *begin = g_malloc0(sizeof(vertice));
+        begin->format = osync_change_get_objformat(start);
+        begin->path = NULL;
+        begin->data = start->data;
+        begin->datasize = start->size;
+        begin->free_data = FALSE;
+        begin->references = 1;
+        
+        tree->search = g_list_append(NULL, begin);
+        while (g_list_length(tree->search)) {
+                vertice *neighbour;
+
+                /* Get the first vertice,
+                 * and remove it from the queue
+                 */
+                vertice *current = g_list_first(tree->search)->data;
+                tree->search = g_list_delete_link(tree->search, g_list_first(tree->search));
+
+                osync_debug("OSFRM", 4, "Searching %s. distance: (l: %d, oc: %d, c: %d).", current->format->name,
+                                current->losses, current->objtype_changes, current->conversions);
+                /* Check if we have reached a target format */
+                if (osync_conv_fmt_in_list(current->format, targets)) {
+                        /* Done. return the result */
+                        result = current;
+                        /* Note: the reference to 'current' will be dropped
+                         * after getting the path from 'result' at
+                         * the end of the function.
+                         */
+                        break;
+                }
+                osync_debug("OSFRM", 4, "Looking %s neighbours.", current->format->name);
+                while ((neighbour = get_next_vertice_neighbour(env, tree, current))) {
                         osync_debug("OSFRM", 4, "%s neighbour: %s", current->format->name, neighbour->format->name);
-                        /* Check if we have reached a target format */
-                        if (osync_conv_fmt_in_list(neighbour->format, targets)) {
-                                //We are done!
-                                *retlist = neighbour->path;
-                                ret = TRUE;
-                                goto reply;
-                        }
                         osync_debug("OSFRM", 4, "Adding %s to queue", neighbour->format->name);
-                        tree->search = g_list_append(tree->search, neighbour);
-                }
-                if (!tree->search)
-                        goto reply;
-                put_edge(current);
-
-                /* Get the next item on the queue */
-                /*TODO: Use a priority queue to get the
-                 * nearest vertices first
-                 * (i.e. try to use less lossy converters)
-                 */
-                current = g_list_first(tree->search)->data;
-                tree->search = g_list_remove(tree->search, current);
-
-        }
-        
-        reply:
-        g_list_foreach(tree->search, (GFunc)put_edge, NULL);
-        
-        if (neighbour)
-                g_free(neighbour);
-        if (current)
-                put_edge(current);
+                        tree->search = g_list_insert_sorted(tree->search, neighbour, compare_vertice_distance);
+                }
+                /* Done, drop the reference to the vertice */
+                deref_vertice(current);
+        }
+        
+        /* Remove the references on the search queue */
+        g_list_foreach(tree->search, (GFunc)deref_vertice, NULL);
+        
+        if (result) {
+                /* Found it. Copy the conversion path */
+                *retlist = g_list_copy(result->path);
+                /* Drop the reference to the result vertice */
+                deref_vertice(result);
+                ret = TRUE;
+        }
         
         g_list_free(tree->unused);

trunk/tests/check_conv.c

@@ -592 +592 @@
   format = change->format;
   fail_unless(format == format1, NULL);
+}
+END_TEST
+
+START_TEST(conv_prefer_not_lossy)
+{
+  /* Test if the converter is getting the path that have no
+   * lossy detectors
+   *
+   * F1 -- F2 -- F3 -- F5
+   *   \              /
+   *     --- F4 -----
+   *
+   * All converters are not lossy, except F1->F4.
+   * The result path should be: F1 -> F2 -> F3 -> F5
+   */
+  OSyncFormatEnv *env = osync_conv_env_new();
+  OSyncObjType *type = osync_conv_register_objtype(env, "O1");
+  
+  OSyncObjFormat *format1 = osync_conv_register_objformat(env, "O1", "F1");
+  osync_conv_register_objformat(env, "O1", "F2");
+  osync_conv_register_objformat(env, "O1", "F3");
+  osync_conv_register_objformat(env, "O1", "F4");
+  OSyncObjFormat *format5 = osync_conv_register_objformat(env, "O1", "F5");
+
+  osync_conv_register_converter(env, CONVERTER_DESENCAP, "F1", "F2", convert_addtest, CONV_NOTLOSSY);
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F2", "F3", convert_addtest, CONV_NOTLOSSY);
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F3", "F5", convert_addtest, CONV_NOTLOSSY);
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F1", "F4", convert_addtest2, 0); /* Lossy converter */
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F4", "F5", convert_addtest2, CONV_NOTLOSSY);
+  mark_point();
+
+  OSyncChange *change = osync_change_new();
+  osync_change_set_objformat(change, format1);
+  osync_change_set_data(change, "data", 5, TRUE);
+  
+  mark_point();
+
+  fail_unless(osync_conv_detect_and_convert(env, change, g_list_append(NULL, format5)), NULL);
+  mark_point();
+  char *data = osync_change_get_data(change);
+  fail_unless(!strcmp(data, "datatesttesttest"), NULL);
+
+  fail_unless(change->objtype == type, NULL);
+  fail_unless(change->format == format5, NULL);
+}
+END_TEST
+
+START_TEST(conv_prefer_same_objtype)
+{
+  /* Test if the converter is getting the path
+   * that doesn't change the objtype, even
+   * if it is longer.
+   *
+   * Objtypes: F and G
+   *
+   * F1 -- F2 -- F3 -- F5 -- F6
+   *   \
+   *     --- G1
+   *
+   * The target list will be [ F6, G1 ].
+   *
+   * The result should be F6.
+   */
+  OSyncFormatEnv *env = osync_conv_env_new();
+  OSyncObjType *typef = osync_conv_register_objtype(env, "F");
+  osync_conv_register_objtype(env, "G");
+  
+  OSyncObjFormat *f1 = osync_conv_register_objformat(env, "F", "F1");
+  osync_conv_register_objformat(env, "F", "F2");
+  osync_conv_register_objformat(env, "F", "F3");
+  osync_conv_register_objformat(env, "F", "F4");
+  osync_conv_register_objformat(env, "F", "F5");
+  OSyncObjFormat *f6 = osync_conv_register_objformat(env, "F", "F6");
+
+  OSyncObjFormat *g1 = osync_conv_register_objformat(env, "G", "G1");
+
+  osync_conv_register_converter(env, CONVERTER_DESENCAP, "F1", "F2", convert_addtest, CONV_NOTLOSSY);
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F2", "F3", convert_addtest, CONV_NOTLOSSY);
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F3", "F4", convert_addtest, CONV_NOTLOSSY);
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F4", "F5", convert_addtest, CONV_NOTLOSSY);
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F5", "F6", convert_addtest, CONV_NOTLOSSY);
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F1", "G1", convert_addtest2, CONV_NOTLOSSY);
+  mark_point();
+
+  OSyncChange *change = osync_change_new();
+  osync_change_set_objformat(change, f1);
+  osync_change_set_data(change, "data", 5, TRUE);
+  
+  mark_point();
+
+  GList *targets = g_list_append(NULL, g1);
+  targets = g_list_append(targets, f6);
+  fail_unless(osync_conv_detect_and_convert(env, change, targets), NULL);
+  mark_point();
+  char *data = osync_change_get_data(change);
+  fail_unless(!strcmp(data, "datatesttesttesttesttest"), NULL);
+
+  fail_unless(change->objtype == typef, NULL);
+  fail_unless(change->format == f6, NULL);
+}
+END_TEST
+
+START_TEST(conv_prefer_not_lossy_objtype_change)
+{
+  /* Test if the converter is getting the path
+   * that have no lossy converters, even if
+   * the objtype is being changed.
+   *
+   * Objtypes: F and G
+   *
+   * F1 -- F2 -- F3 -- F5 -- F6
+   *   \
+   *     --- G1
+   *
+   * The target list will be [ F6, G1 ].
+   *
+   * The converter F2 -> F3 is lossy.
+   *
+   * The result should be G1.
+   */
+  OSyncFormatEnv *env = osync_conv_env_new();
+  osync_conv_register_objtype(env, "F");
+  OSyncObjType *typeg = osync_conv_register_objtype(env, "G");
+  
+  OSyncObjFormat *f1 = osync_conv_register_objformat(env, "F", "F1");
+  osync_conv_register_objformat(env, "F", "F2");
+  osync_conv_register_objformat(env, "F", "F3");
+  osync_conv_register_objformat(env, "F", "F4");
+  osync_conv_register_objformat(env, "F", "F5");
+  OSyncObjFormat *f6 = osync_conv_register_objformat(env, "F", "F6");
+
+  OSyncObjFormat *g1 = osync_conv_register_objformat(env, "G", "G1");
+
+  osync_conv_register_converter(env, CONVERTER_DESENCAP, "F1", "F2", convert_addtest, CONV_NOTLOSSY);
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F2", "F3", convert_addtest, 0); /* Lossy */
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F3", "F4", convert_addtest, CONV_NOTLOSSY);
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F4", "F5", convert_addtest, CONV_NOTLOSSY);
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F5", "F6", convert_addtest, CONV_NOTLOSSY);
+  osync_conv_register_converter(env, CONVERTER_ENCAP, "F1", "G1", convert_addtest2, CONV_NOTLOSSY);
+  mark_point();
+
+  OSyncChange *change = osync_change_new();
+  osync_change_set_objformat(change, f1);
+  osync_change_set_data(change, "data", 5, TRUE);
+  
+  mark_point();
+
+  GList *targets = g_list_append(NULL, g1);
+  targets = g_list_append(targets, f6);
+  fail_unless(osync_conv_detect_and_convert(env, change, targets), NULL);
+  mark_point();
+  char *data = osync_change_get_data(change);
+  fail_unless(!strcmp(data, "datatest2"), NULL);
+
+  fail_unless(change->objtype == typeg, NULL);
+  fail_unless(change->format == g1, NULL);
 }
 END_TEST
@@ -657 +813 @@
         tcase_add_test(tc_convert, conv_env_convert_desenc);
         tcase_add_test(tc_convert, conv_env_convert_desenc_complex);
+        tcase_add_test(tc_convert, conv_prefer_not_lossy);
+        tcase_add_test(tc_convert, conv_prefer_same_objtype);
+        tcase_add_test(tc_convert, conv_prefer_not_lossy_objtype_change);
         tcase_add_test(tc_detect, conv_env_detect_and_convert);
         tcase_add_test(tc_detect, conv_env_detect_false);

@@ -5 +5 @@
 .libs
 .deps
+evolution_sync.loT