formats/xmlformat_compare.c

   1 /*
   2  * xmlformat_compare - comparsion logic of xmlformat
   3  * Copyright (C) 2006  Daniel Friedrich <daniel.friedrich@opensync.org>
   4  * Copyright (C) 2007  Daniel Gollub <dgollub@suse.de>
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
  19  *
  20  */
  21
  22 #include "xmlformat.h"
  23
  24 #include <libxml/xmlstring.h>
  25 #include <libxml/tree.h>
  26
  27 #include "opensync/xmlformat/opensync_xmlformat_internals.h"
  28
  29
  30 #include "opensync/xmlformat/opensync_xmlfield_private.h"       /* FIXME: direct include of private header */
  31
  32
  33 /**
  34  * @brief Search for the points in the sorted OSyncXMLPoints array for a given fieldname.
  35  * @param points The sorted points array
  36  * @param cur_pos Pointer to the actual line in the points array
  37  * @param basic_points Points which should be returned if fieldname will not found in the points array
  38  * @param fieldname The name of the field for which the points should be returned
  39  * @returns The points for the fieldname
  40  */
  41 int xmlformat_get_points(OSyncXMLPoints *points, int* cur_pos, int basic_points, const char* fieldname)
  42 {
  43   for(; points[(*cur_pos)].fieldname; (*cur_pos)++) {
  44     int res = strcmp(points[(*cur_pos)].fieldname, fieldname);
  45     if(res == 0)
  46       return points[(*cur_pos)].points;
  47     if(res > 0)
  48       return basic_points;
  49   }
  50
  51   return basic_points;
  52 }
  53
  54 /**
  55  * @brief Search for the points in the sorted OSyncXMLPoints array for the fieldname of xmlfield and handle ignored fields.
  56  *
  57  *  This uses xmlformat_get_points() but handle the case if the field needs to be ignored.
  58  *  Ignored fields doesn't have influence on the compare result. This is needed to keep the compare
  59  *  result SAME if an ignored fields are the only differences between the entries.
  60  *
  61  *  0 Points got returned for ignored fields to avoid influence of the collected_points value and let
  62  *  collected_points not raise over the threshold value. This could change the compare result to SIMILAR,
  63  *  even if the entry should  MISMATCH, this should be avoided. This happens when the number of ignored fiels
  64  *  is the greather equal as the thresold value.
  65  *
  66  * @param xmlfield Pointer to xmlfield
  67  * @param points The sorted points array
  68  * @param cur_pos Pointer to the actual line in the points array. Gets incremented if the xmlfield requires this!
  69  * @param basic_points Points which should be returned if fieldname will not found in the points array
  70  * @param same Pointer ot the compare result flag SAME, which got not set to FALSE if the fields should be ignored.
  71  * @returns The points for the fieldname. If the field should be ignored 0 points got retunred.
  72  */
  73 static int xmlformat_subtract_points(OSyncXMLField *xmlfield, OSyncXMLPoints *points, int *cur_pos, int basic_points, int *same) {
  74   int p = 0;
  75   osync_trace(TRACE_ENTRY, "%s(%p, %p, %p, %i, %p)", __func__, xmlfield, points, cur_pos, basic_points, same);
  76   p = xmlformat_get_points(points, cur_pos, basic_points, osync_xmlfield_get_name(xmlfield));
  77
  78   /* Stay with SAME as compare result and don't substract any points - if fields should be ignored */
  79   if (p != -1) {
  80     osync_trace(TRACE_INTERNAL, "Not same anymore - \"%s\" field differs!", osync_xmlfield_get_name(xmlfield));
  81     *same = FALSE;
  82   } else {
  83     osync_trace(TRACE_INTERNAL, "Ignored field: %s", osync_xmlfield_get_name(xmlfield));
  84     p = 0;
  85   }
  86
  87   osync_trace(TRACE_EXIT, "%s: %i", __func__, p);
  88   return p;
  89 }
  90
  91 /**
  92  * @brief Help method which return the content of a xmlNode
  93  * @param node The pointer to a xmlNode
  94  * @return The value of the xmlNode or a empty string
  95  */
  96 static xmlChar *xml_node_get_content(xmlNodePtr node)
  97 {
  98   if (node->children && node->children->content)
  99     return node->children->content;
 100
 101   return (xmlChar *)"";
 102 }
 103
 104 /**
 105  * @brief Compares two xmlfield objects with each other
 106  * @param xmlfield1 The pointer to a xmlformat object
 107  * @param xmlfield2 The pointer to a xmlformat object
 108  * @return TRUE if both xmlfield objects are the same otherwise FALSE
 109  */
 110 osync_bool xmlfield_compare(OSyncXMLField *xmlfield1, OSyncXMLField *xmlfield2)
 111 {
 112   int i;
 113   osync_bool same;
 114   xmlNodePtr key1 = NULL;
 115   xmlNodePtr key2 = NULL;
 116
 117
 118   osync_trace(TRACE_ENTRY, "%s(%p, %p)", __func__, xmlfield1, xmlfield2);
 119   osync_assert(xmlfield1);
 120   osync_assert(xmlfield2);
 121
 122   if(strcmp(osync_xmlfield_get_name(xmlfield1), osync_xmlfield_get_name(xmlfield2))) {
 123     osync_trace(TRACE_EXIT, "%s: %i", __func__, FALSE);
 124     return FALSE;
 125   }
 126
 127   same = TRUE;
 128   key1 = xmlfield1->node->children;
 129   key2 = xmlfield2->node->children;
 130
 131   while(same)
 132     {
 133       GSList *keylist1 = NULL;
 134       GSList *keylist2 = NULL;
 135       const char *curkeyname = NULL;
 136
 137       if(key1 == NULL && key2 == NULL) {
 138         break;
 139       }
 140
 141       if(key1 == NULL || key2 == NULL) {
 142         same = FALSE;
 143         break;
 144       }
 145
 146       curkeyname = (const char *)key1->name;
 147       do {
 148         keylist1 = g_slist_prepend(keylist1, key1);
 149         key1 = key1->next;
 150         if(key1 == NULL)
 151           break;
 152         i = strcmp((const char *)key1->name, curkeyname);
 153       } while(i == 0);
 154
 155       do {
 156         keylist2 = g_slist_prepend(keylist2, key2);
 157         key2 = key2->next;
 158         if(key2 == NULL)
 159           break;
 160         i = strcmp((const char *)key2->name, curkeyname);
 161       } while(i == 0);
 162
 163       do{
 164         GSList *cur_list1 = NULL;
 165         GSList *cur_list2 = NULL;
 166
 167         /* both lists must have the same length */
 168         if(g_slist_length(keylist1) != g_slist_length(keylist2)) {
 169           osync_trace(TRACE_INTERNAL, "It's not the same anymore...");
 170           same = FALSE;
 171           break;
 172         }
 173
 174         do {
 175           cur_list1 = keylist1;
 176           cur_list2 = keylist2;
 177
 178           do {
 179             if(!xmlStrcmp(xml_node_get_content(cur_list1->data), xml_node_get_content(cur_list2->data)))
 180               break;
 181             cur_list2 = g_slist_next(cur_list2);
 182             if(cur_list2 == NULL) {
 183               same = FALSE;
 184               break;
 185             }
 186           }while(1);
 187
 188           if(same) {
 189             keylist1 = g_slist_delete_link(keylist1, cur_list1);
 190             keylist2 = g_slist_delete_link(keylist2, cur_list2);
 191           }else
 192             break;
 193
 194         }while(keylist1 != NULL);
 195       }while(0);
 196
 197       if(keylist1)
 198         g_slist_free(keylist1);
 199       if(keylist2)
 200         g_slist_free(keylist2);
 201     }
 202
 203   /* now we check if the attributes are equal */
 204   do {
 205     int i1 = 0, i2 = 0;
 206     if(!same)
 207       break;
 208
 209     i1 =osync_xmlfield_get_attr_count(xmlfield1);
 210     i2 =osync_xmlfield_get_attr_count(xmlfield2);
 211
 212     if(i1 != i2) {
 213       same = FALSE;
 214       break;
 215     }
 216
 217     for(i=0; i < i1; i++) {
 218       const char *attrvalue = osync_xmlfield_get_attr(xmlfield2, osync_xmlfield_get_nth_attr_name(xmlfield1, i));
 219       if( attrvalue == NULL ||
 220           strcmp(attrvalue, osync_xmlfield_get_nth_attr_value(xmlfield1, i))) {
 221         same = FALSE;
 222         break;
 223       }
 224     }
 225   } while(0);
 226   osync_trace(TRACE_EXIT, "%s: %i", __func__, same);
 227   return same;
 228 }
 229
 230 /**
 231  * @brief Compares two xmlfield objects with each other of similarity
 232  * @param xmlfield1 The pointer to a xmlformat object
 233  * @param xmlfield2 The pointer to a xmlformat object
 234  * @param keys OSyncXMLPoints::keys
 235  * @return TRUE if both xmlfield objects are the similar otherwise FALSE
 236  */
 237 osync_bool xmlfield_compare_similar(OSyncXMLField *xmlfield1, OSyncXMLField *xmlfield2, char* keys[])
 238 {
 239   osync_bool res = TRUE;
 240   xmlNodePtr node1, node2;
 241   int i;
 242   osync_trace(TRACE_ENTRY, "%s(%p, %p, %p)", __func__, xmlfield1, xmlfield2, keys);
 243   osync_assert(xmlfield1);
 244   osync_assert(xmlfield2);
 245
 246   if(strcmp((const char *) osync_xmlfield_get_name(xmlfield1), (const char *) osync_xmlfield_get_name(xmlfield2)) != 0)
 247     res = FALSE;
 248
 249   node1 = xmlfield1->node->children;
 250   node2 = xmlfield2->node->children;
 251
 252   for(i=0; keys[i]; i++) {
 253     GSList *list1;
 254     GSList *list2;
 255     GSList *cur_list1;
 256     GSList *cur_list2;
 257
 258     list1 = NULL;
 259     list2 = NULL;
 260
 261     while(node1 != NULL) {
 262       if(strcmp(keys[i], (const char *)node1->name) == 0)
 263         list1 = g_slist_prepend(list1, node1);
 264       node1 = node1->next;
 265     };
 266
 267     while(node2 != NULL) {
 268       if(strcmp(keys[i], (const char *)node2->name) == 0)
 269         list2 = g_slist_prepend(list2, node2);
 270       node2 = node2->next;
 271     };
 272
 273     while(list1 != NULL)
 274       {
 275         cur_list1 = list1;
 276         cur_list2 = list2;
 277
 278         if(cur_list2 == NULL) {
 279           res = FALSE;
 280           break;
 281         }
 282
 283         while(xmlStrcmp(xml_node_get_content((xmlNodePtr)cur_list1->data),
 284                         xml_node_get_content((xmlNodePtr)cur_list2->data))) {
 285           cur_list2 = g_slist_next(cur_list2);
 286           if(cur_list2 == NULL) {
 287             res = FALSE;
 288             break;
 289           }
 290         }
 291
 292         if(res) {
 293           list1 = g_slist_delete_link(list1, cur_list1);
 294           list2 = g_slist_delete_link(list2, cur_list2);
 295         }else
 296           break;
 297       }
 298     if(list2 != NULL)
 299       res = FALSE;
 300
 301     if(!res) {
 302       if(list1 != NULL)
 303         g_slist_free(list1);
 304       if(list2 != NULL)
 305         g_slist_free(list2);
 306     }
 307   }
 308   osync_trace(TRACE_EXIT, "%s: %i", __func__, res);
 309   return res;
 310 }
 311
 312
 313 /**
 314  * @brief Compares two xmlformat objects with each other
 315  * @param xmlformat1 The pointer to a xmlformat object
 316  * @param xmlformat2 The pointer to a xmlformat object
 317  * @param points The sorted points array
 318  * @param basic_points Points which should be used if a xmlfield name is not found in the points array
 319  * @param threshold If the two xmlformats are not the same, then this value will decide if the two xmlformats are similar
 320  * @return One of the values of the OSyncConvCmpResult enumeration
 321  */
 322 OSyncConvCmpResult xmlformat_compare(OSyncXMLFormat *xmlformat1, OSyncXMLFormat *xmlformat2, OSyncXMLPoints points[], int basic_points, int threshold)
 323 {
 324   int res, collected_points, cur_pos;
 325   OSyncXMLField *xmlfield1 = NULL;
 326   OSyncXMLField *xmlfield2 = NULL;
 327   osync_bool same = TRUE;
 328
 329   osync_trace(TRACE_ENTRY, "%s(%p, %p, %p, %i, %i)", __func__, xmlformat1, xmlformat2, points, basic_points, threshold);
 330
 331   xmlfield1 = osync_xmlformat_get_first_field(xmlformat1);
 332   xmlfield2 = osync_xmlformat_get_first_field(xmlformat2);
 333
 334   cur_pos = 0;
 335   collected_points = 0;
 336
 337   while(xmlfield1 != NULL || xmlfield2 != NULL)
 338     {
 339
 340       /* subtract points for xmlfield2*/
 341       if(xmlfield1 == NULL) {
 342         collected_points -= xmlformat_subtract_points(xmlfield2, points, &cur_pos, basic_points, &same);
 343         xmlfield2 = osync_xmlfield_get_next(xmlfield2);
 344         continue;
 345       }
 346
 347       /* subtract points for xmlfield1*/
 348       if(xmlfield2 == NULL) {
 349         collected_points -= xmlformat_subtract_points(xmlfield1, points, &cur_pos, basic_points, &same);
 350         xmlfield1 = osync_xmlfield_get_next(xmlfield1);
 351         continue;
 352       }
 353
 354       res = strcmp(osync_xmlfield_get_name(xmlfield1), osync_xmlfield_get_name(xmlfield2));
 355       osync_trace(TRACE_INTERNAL, "result of strcmp(): %i (%s || %s)", res, osync_xmlfield_get_name(xmlfield1), osync_xmlfield_get_name(xmlfield2));
 356
 357       /* subtract points for xmlfield1*/
 358       if(res < 0) {
 359         collected_points -= xmlformat_subtract_points(xmlfield1, points, &cur_pos, basic_points, &same);
 360         xmlfield1 = osync_xmlfield_get_next(xmlfield1);
 361         continue;
 362       }
 363
 364       /* subtract points for xmlfield2*/
 365       if(res > 0) {
 366         collected_points -= xmlformat_subtract_points(xmlfield2, points, &cur_pos, basic_points, &same);
 367         xmlfield2 = osync_xmlfield_get_next(xmlfield2);
 368         continue;
 369       }
 370
 371       /* make lists and compare */
 372       if(res == 0)
 373         {
 374           GSList *fieldlist1 = NULL;
 375           GSList *fieldlist2 = NULL;
 376
 377           const char *curfieldname = osync_xmlfield_get_name(xmlfield1);
 378
 379           /* get the points*/
 380           int p = xmlformat_get_points(points, &cur_pos, basic_points, curfieldname);
 381
 382           /* don't compare both fields if they should be ignore to avoid influence of the compare result */
 383           if (p == -1) {
 384             xmlfield1 = osync_xmlfield_get_next(xmlfield1);
 385             xmlfield2 = osync_xmlfield_get_next(xmlfield2);
 386             continue;
 387           }
 388
 389           do {
 390             fieldlist1 = g_slist_prepend(fieldlist1, xmlfield1);
 391             xmlfield1 = osync_xmlfield_get_next(xmlfield1);
 392             if(xmlfield1 == NULL)
 393               break;
 394             res = strcmp(osync_xmlfield_get_name(xmlfield1), curfieldname);
 395           } while(res == 0);
 396
 397           do {
 398             fieldlist2 = g_slist_prepend(fieldlist2, xmlfield2);
 399             xmlfield2 = osync_xmlfield_get_next(xmlfield2);
 400             if(xmlfield2 == NULL)
 401               break;
 402             res = strcmp(osync_xmlfield_get_name(xmlfield2), curfieldname);
 403           } while(res == 0);
 404
 405           do {
 406
 407             /* if same then compare and give points*/
 408             do {
 409               GSList *cur_list1;
 410               GSList *cur_list2;
 411
 412               if(!same)
 413                 break;
 414
 415               /* both lists must have the same length */
 416               if(g_slist_length(fieldlist1) != g_slist_length(fieldlist2)) {
 417                 same = FALSE;
 418                 osync_trace(TRACE_INTERNAL, "both list don't have the same length");
 419                 break;
 420               }
 421
 422               do {
 423                 cur_list1 = fieldlist1;
 424                 cur_list2 = fieldlist2;
 425
 426                 do {
 427                   if(xmlfield_compare((OSyncXMLField *)cur_list1->data, (OSyncXMLField *)cur_list2->data) == TRUE)
 428                     break;
 429                   cur_list2 = g_slist_next(cur_list2);
 430                   if(cur_list2 == NULL) {
 431                     same = FALSE;
 432                     osync_trace(TRACE_INTERNAL, "one field is alone: %s", osync_xmlfield_get_name(cur_list1->data));
 433                     break;
 434                   }
 435                 }while(1);
 436
 437                 if(same) {
 438                   /* add the points */
 439                   osync_trace(TRACE_INTERNAL, "add %i point(s) for same fields: %s", p, curfieldname);
 440                   collected_points += p;
 441                   fieldlist1 = g_slist_delete_link(fieldlist1, cur_list1);
 442                   fieldlist2 = g_slist_delete_link(fieldlist2, cur_list2);
 443                 }else
 444                   break;
 445
 446               }while(fieldlist1 != NULL);
 447             } while(0);
 448
 449             /* if similar then compare and give points*/
 450             do {
 451               GSList *cur_list1;
 452               GSList *cur_list2;
 453               osync_bool found;
 454               int subtracted_count;
 455
 456               if(same)
 457                 break;
 458               /* if no points to add or to subtract we need no compair of similarity */
 459               if(!p) {
 460                 g_slist_free(fieldlist1);
 461                 g_slist_free(fieldlist2);
 462                 fieldlist1 = NULL;
 463                 fieldlist2 = NULL;
 464                 break;
 465               }
 466
 467               subtracted_count = 0;
 468               do {
 469                 found = FALSE;
 470                 cur_list1 = fieldlist1;
 471                 cur_list2 = fieldlist2;
 472
 473                 while(cur_list2) {
 474
 475                   if(xmlfield_compare_similar((OSyncXMLField *)cur_list1->data,
 476                                                 (OSyncXMLField *)cur_list2->data,
 477                                                 points[cur_pos].keys) == TRUE) {
 478                     found = TRUE;
 479                     break;
 480                   }
 481
 482                   cur_list2 = g_slist_next(cur_list2);
 483                 }
 484
 485                 /* add or subtract the points */
 486                 if(found) {
 487                   /* add the points */
 488                   osync_trace(TRACE_INTERNAL, "add %i point(s) for similiar field: %s", p, curfieldname);
 489                   collected_points += p;
 490                   fieldlist1 = g_slist_delete_link(fieldlist1, cur_list1);
 491                   fieldlist2 = g_slist_delete_link(fieldlist2, cur_list2);
 492                 }else{
 493                   /* subtract the points */
 494                   osync_trace(TRACE_INTERNAL, "subtracting %i point(s) for missing field: %s", p, curfieldname);
 495                   collected_points -= p;
 496                   subtracted_count++;
 497                   fieldlist1 = g_slist_delete_link(fieldlist1, cur_list1);
 498                 }
 499               }while(fieldlist1 != NULL);
 500
 501               /* subtract the points for the remaining elements in the list2 */
 502               while(fieldlist2) {
 503                 /* subtract the points */
 504                 if(subtracted_count > 0) {
 505                   subtracted_count--;
 506                 } else {
 507                   osync_trace(TRACE_INTERNAL, "subtracting %i point(s) for remaining field: %s", p, curfieldname);
 508                   collected_points -= p;
 509                 }
 510                 fieldlist2 = g_slist_delete_link(fieldlist2, fieldlist2);
 511               }
 512
 513             }while(0);
 514
 515           }while(0);
 516
 517           /* the lists should not exist */
 518           g_assert(!fieldlist1);
 519           g_assert(!fieldlist2);
 520         }
 521     };
 522
 523   osync_trace(TRACE_INTERNAL, "Result is: %i, Treshold is: %i", collected_points, threshold);
 524   if (same) {
 525     osync_trace(TRACE_EXIT, "%s: SAME", __func__);
 526     return OSYNC_CONV_DATA_SAME;
 527   }
 528   if (collected_points >= threshold) {
 529     osync_trace(TRACE_EXIT, "%s: SIMILAR", __func__);
 530     return OSYNC_CONV_DATA_SIMILAR;
 531   }
 532   osync_trace(TRACE_EXIT, "%s: MISMATCH", __func__);
 533   return OSYNC_CONV_DATA_MISMATCH;
 534 }
 535