Line data    Source code

       1             : /**
       2             :  * @file
       3             :  *
       4             :  * @brief
       5             :  *
       6             :  * @copyright BSD License (see LICENSE.md or https://www.libelektra.org)
       7             :  */
       8             : 
       9             : #include "xmltool.h"
      10             : 
      11             : #include <stdlib.h>
      12             : #include <string.h>
      13             : 
      14          14 : static Key * commonParent (Key * firstKey, Key * secondKey, size_t maxSize)
      15             : {
      16             :         // First we find the common prefix of the first two keys.
      17             :         // NOTE: a common prefix is not necessarily a common parent
      18             :         //   e.g. system:/abc/d is a common prefix of system:/abc/de and system:/abc/df,
      19             :         //   but the common parent would be system:/abc
      20             : 
      21          14 :         const char * firstName = keyName (firstKey);
      22          14 :         const char * secondName = keyName (secondKey);
      23             : 
      24          14 :         size_t commonLength = 0;
      25         208 :         for (size_t i = 0; i < maxSize; ++i)
      26             :         {
      27         208 :                 if (firstName[i] == '\0' || secondName[i] == '\0')
      28             :                 {
      29             :                         break;
      30             :                 }
      31             : 
      32         208 :                 if (firstName[i] != secondName[i])
      33             :                 {
      34             :                         break;
      35             :                 }
      36             : 
      37         194 :                 commonLength = i + 1;
      38             :         }
      39             : 
      40          14 :         if (commonLength == 0)
      41             :         {
      42             :                 return NULL;
      43             :         }
      44             : 
      45             :         // We now extract the common prefix ...
      46          10 :         char * commonPrefix = strndup (firstName, commonLength);
      47             : 
      48             :         // ... and adjust it to a common parent.
      49          10 :         Key * common = keyNew (commonPrefix, KEY_END);
      50          10 :         if (commonPrefix[commonLength - 1] != '/')
      51             :         {
      52           2 :                 keySetBaseName (common, NULL);
      53             :         }
      54             : 
      55          10 :         free (commonPrefix);
      56             : 
      57          10 :         if ((size_t) keyGetNameSize (common) > maxSize)
      58             :         {
      59           0 :                 keyDel (common);
      60           0 :                 return NULL;
      61             :         }
      62             : 
      63             :         return common;
      64             : }
      65             : 
      66             : 
      67             : /**
      68             :  * @internal
      69             :  *
      70             :  * Calculates the common parent to all keys in @p ks.
      71             :  *
      72             :  * This is a c-helper function, you need not implement it in bindings.
      73             :  *
      74             :  * Given the @p ks KeySet, calculates the parent name for all the keys.
      75             :  * So if @p ks contains these keys:
      76             :  *
      77             :  * @code
      78             :  *   system:/sw/xorg/Monitors/Monitor1/vrefresh
      79             :  *   system:/sw/xorg/Monitors/Monitor1/hrefresh
      80             :  *   system:/sw/xorg/Devices/Device1/driver
      81             :  *   system:/sw/xorg/Devices/Device1/mode
      82             :  * @endcode
      83             :  *
      84             :  * The common parent is @p system:/sw/xorg .
      85             :  *
      86             :  * On the other hand, if we have this KeySet:
      87             :  *
      88             :  * @code
      89             :  *   system:/some/thing
      90             :  *   system:/other/thing
      91             :  *   user:/unique/thing
      92             :  * @endcode
      93             :  *
      94             :  * No common parent is possible, so @p returnedCommonParent will contain nothing.
      95             :  *
      96             :  * @param working the Keyset to work with
      97             :  * @param returnedCommonParent a pre-allocated buffer that will receive the
      98             :  *        common parent, if found
      99             :  * @param maxSize size of the pre-allocated @p returnedCommonParent buffer
     100             :  * @return size in bytes of the parent name, or 0 if there is no common parent (with length <= maxSize)
     101             :  */
     102          14 : size_t ksGetCommonParentName (KeySet * working, char * returnedCommonParent, size_t maxSize)
     103             : {
     104          14 :         if (maxSize > SSIZE_MAX) return 0;
     105          14 :         if (ksGetSize (working) < 1) return 0;
     106             : 
     107          14 :         if (ksGetSize (working) == 1)
     108             :         {
     109           2 :                 return keyGetName (ksAtCursor (working, 0), returnedCommonParent, maxSize);
     110             :         }
     111             : 
     112             :         // Get common parent of first two keys in the KeySet.
     113             : 
     114          12 :         Key * common = commonParent (ksAtCursor (working, 0), ksAtCursor (working, 1), maxSize);
     115             : 
     116          12 :         if (common == NULL)
     117             :         {
     118           4 :                 *returnedCommonParent = '\0';
     119           4 :                 return 0;
     120             :         }
     121             : 
     122             :         // We then check if all keys in the KeySet are below the parent we found.
     123           8 :         KeySet * cut = ksCut (working, common);
     124             : 
     125          10 :         while (ksGetSize (working) != 0)
     126             :         {
     127             :                 // If not all keys match, we find the common prefix of common and the first non-matching key.
     128           2 :                 Key * nextKey = ksAtCursor (working, 0);
     129             : 
     130           2 :                 ksAppend (working, cut);
     131           2 :                 ksDel (cut);
     132             : 
     133           2 :                 Key * newCommon = commonParent (common, nextKey, maxSize);
     134             : 
     135           2 :                 keyDel (common);
     136           2 :                 common = newCommon;
     137             : 
     138           2 :                 if (common == NULL)
     139             :                 {
     140           0 :                         *returnedCommonParent = '\0';
     141           0 :                         return 0;
     142             :                 }
     143             : 
     144           2 :                 cut = ksCut (working, common);
     145             :         }
     146             : 
     147           8 :         ksAppend (working, cut);
     148           8 :         ksDel (cut);
     149             : 
     150           8 :         ssize_t ret = keyGetName (common, returnedCommonParent, maxSize);
     151           8 :         keyDel (common);
     152           8 :         return ret;
     153             : }