Fortified the tree of binary portions.

7 files changed, 200 insertions, 26 deletions

diff --git a/ChangeLog b/ChangeLog
index 62b87c6..7599fa5 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,18 @@
+17-01-14  Cyrille Bagard <nocbos@gmail.com>
+
+	* src/arch/vmpa.c:
+	* src/arch/vmpa.h:
+	Define extra comparisons for memory ranges.
+
+	* src/common/sort.c:
+	* src/common/sort.h:
+	Restore an assertion. Create a function to delete an indexed item from
+	a sorted array.
+
+	* src/glibext/gbinportion.c:
+	* src/glibext/gbinportion.h:
+	Fortify the tree of binary portions.
+
 17-01-10  Cyrille Bagard <nocbos@gmail.com>
 
 	* .gitignore:
diff --git a/src/arch/vmpa.c b/src/arch/vmpa.c
index 4f9b87f..c32c836 100644
--- a/src/arch/vmpa.c
+++ b/src/arch/vmpa.c
@@ -46,6 +46,14 @@ static char *_phys_t_to_string(phys_t, MemoryDataSize, char [VMPA_MAX_LEN], size
 
 
 
+/* ------------------------ DEFINITION D'UNE ZONE EN MEMOIRE ------------------------ */
+
+
+/* Compare une couverture mémoire avec une localisation simple. */
+static int _cmp_mrange_with_vmpa(const mrange_t *, const vmpa2t *, bool);
+
+
+
 /* ---------------------------------------------------------------------------------- */
 /*                        DEFINITION D'UNE POSITION EN MEMOIRE                        */
 /* ---------------------------------------------------------------------------------- */
@@ -874,8 +882,9 @@ int cmp_mrange(const mrange_t *a, const mrange_t *b)
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : a = première définition à analyser.                          *
-*                b = seconde définition à analyser.                           *
+*  Paramètres  : a   = première définition à analyser.                        *
+*                b   = seconde définition à analyser.                         *
+*                inc = indique si l'adresse peut être une fin de zone.        *
 *                                                                             *
 *  Description : Compare une couverture mémoire avec une localisation simple. *
 *                                                                             *
@@ -885,7 +894,7 @@ int cmp_mrange(const mrange_t *a, const mrange_t *b)
 *                                                                             *
 ******************************************************************************/
 
-int cmp_mrange_with_vmpa(const mrange_t *a, const vmpa2t *b)
+static int _cmp_mrange_with_vmpa(const mrange_t *a, const vmpa2t *b, bool inclusive)
 {
     int result;                             /* Bilan à retourner           */
     phys_t diff;                            /* Espace entre deux adresses  */
@@ -914,6 +923,9 @@ int cmp_mrange_with_vmpa(const mrange_t *a, const vmpa2t *b)
         else if (diff < a->length)
             result = 0;
 
+        else if (diff == a->length && inclusive)
+            result = 0;
+
         else
             result = 1;
 
@@ -926,6 +938,86 @@ int cmp_mrange_with_vmpa(const mrange_t *a, const vmpa2t *b)
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : a = première définition à analyser.                          *
+*                b = seconde définition à analyser.                           *
+*                                                                             *
+*  Description : Compare une couverture mémoire avec une localisation simple. *
+*                                                                             *
+*  Retour      : Bilan de la comparaison : -1, 0 ou 1 (-1 par défaut).        *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+int cmp_mrange_with_vmpa(const mrange_t *a, const vmpa2t *b)
+{
+    int result;                             /* Bilan à retourner           */
+
+    result = _cmp_mrange_with_vmpa(a, b, false);
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : a = première définition à analyser.                          *
+*                b = seconde définition à analyser.                           *
+*                                                                             *
+*  Description : Compare une couverture mémoire avec une localisation simple. *
+*                                                                             *
+*  Retour      : Bilan de la comparaison : -1, 0 ou 1 (-1 par défaut).        *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+int cmp_mrange_with_vmpa_inclusive(const mrange_t *a, const vmpa2t *b)
+{
+    int result;                             /* Bilan à retourner           */
+
+    result = _cmp_mrange_with_vmpa(a, b, true);
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : range = zone mémoire à consulter.                            *
+*                sub   = éventuelle sous-région à valider.                    *
+*                                                                             *
+*  Description : Indique si une zone en contient une autre ou non.            *
+*                                                                             *
+*  Retour      : Bilan de la comparaison : -1, 0 ou 1 (-1 par défaut).        *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+int mrange_includes_mrange(const mrange_t *range, const mrange_t *sub)
+{
+    int result;                             /* Bilan à retourner           */
+    vmpa2t end;                             /* Seconde extrémité           */
+
+    result = cmp_mrange_with_vmpa(range, get_mrange_addr(sub));
+
+    if (result == 0)
+    {
+        compute_mrange_end_addr(sub, &end);
+
+        result = cmp_mrange_with_vmpa_inclusive(range, &end);
+
+    }
+
+    return result;
+
+}
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : range = zone mémoire à consulter.                            *
 *                sub   = éventuelle sous-région à valider.                    *
 *                                                                             *
diff --git a/src/arch/vmpa.h b/src/arch/vmpa.h
index 996a7fb..6305f79 100644
--- a/src/arch/vmpa.h
+++ b/src/arch/vmpa.h
@@ -203,6 +203,12 @@ static inline int cmp_mrange_with_vmpa_swapped(const vmpa2t *k, const mrange_t *
     return cmp_mrange_with_vmpa(r, k);
 }
 
+/* Compare une couverture mémoire avec une localisation simple. */
+int cmp_mrange_with_vmpa_inclusive(const mrange_t *, const vmpa2t *);
+
+/* Indique si une zone en contient une autre ou non. */
+int mrange_includes_mrange(const mrange_t *, const mrange_t *);
+
 /* Indique si une zone en contient une autre ou non. */
 bool mrange_contains_mrange(const mrange_t *, const mrange_t *);
 
diff --git a/src/common/sort.c b/src/common/sort.c
index 750034b..7da9a29 100644
--- a/src/common/sort.c
+++ b/src/common/sort.c
@@ -194,7 +194,7 @@ void *qinsert(void *base, size_t *nmemb, size_t size, __compar_fn_t compar, void
 
 #ifndef NDEBUG
     found = bsearch_index(new, base, *nmemb, size, compar, &index);
-    //assert(!found); FIXME (portions)
+    assert(!found);
 #else
     bsearch_index(new, base, *nmemb, size, compar, &index);
 #endif
@@ -208,6 +208,37 @@ void *qinsert(void *base, size_t *nmemb, size_t size, __compar_fn_t compar, void
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : base  = adresse du tableau à parcourir.                      *
+*                nmem  = nombre d'éléments présents au total. [OUT]           *
+*                size  = taille de chaque élément du tableau.                 *
+*                inde  = indice du point de suppression.                      *
+*                                                                             *
+*  Description : Supprime un élément dans un tableau trié.                    *
+*                                                                             *
+*  Retour      : Nouvel emplacement du tableau rétréci.                       *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void *_qdelete(void *base, size_t *nmemb, size_t size, size_t index)
+{
+    void *result;                           /* Tableau trié à retourner    */
+
+    if ((index + 1) < *nmemb)
+        memmove((char *)base + index * size, (char *)base + (index + 1) * size, (*nmemb - index - 1) * size);
+
+    (*nmemb)--;
+
+    result = realloc(base, *nmemb * size);
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : base   = adresse du tableau à parcourir.                     *
 *                nmemb  = nombre d'éléments présents au total. [OUT]          *
 *                size   = taille de chaque élément du tableau.                *
@@ -237,12 +268,7 @@ void *qdelete(void *base, size_t *nmemb, size_t size, __compar_fn_t compar, void
     bsearch_index(target, base, *nmemb, size, compar, &index);
 #endif
 
-    if ((index + 1) < *nmemb)
-        memmove((char *)base + index * size, (char *)base + (index + 1) * size, (*nmemb - index - 1) * size);
-
-    (*nmemb)--;
-
-    result = realloc(base, *nmemb * size);
+    result = _qdelete(base, nmemb, size, index);
 
     return result;
 
diff --git a/src/common/sort.h b/src/common/sort.h
index 9fcc240..fb47a5e 100644
--- a/src/common/sort.h
+++ b/src/common/sort.h
@@ -43,6 +43,9 @@ void *_qinsert(void *, size_t *, size_t, void *, size_t);
 void *qinsert(void *, size_t *, size_t, __compar_fn_t, void *);
 
 /* Supprime un élément dans un tableau trié. */
+void *_qdelete(void *, size_t *, size_t, size_t);
+
+/* Supprime un élément dans un tableau trié. */
 void *qdelete(void *, size_t *, size_t, __compar_fn_t, void *);
 
 
diff --git a/src/glibext/gbinportion.c b/src/glibext/gbinportion.c
index 4849caa..e5dedd6 100644
--- a/src/glibext/gbinportion.c
+++ b/src/glibext/gbinportion.c
@@ -310,6 +310,30 @@ int g_binary_portion_compare(const GBinPortion **a, const GBinPortion **b)
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : a = premières informations à consulter.                      *
+*                b = secondes informations à consulter.                       *
+*                                                                             *
+*  Description : Détermine si une portion est comprise dans une autre.        *
+*                                                                             *
+*  Retour      : Bilan : -1 (a < b), 0 (b € a) ou 1 (a > b).                  *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+int g_binary_portion_is_included(const GBinPortion **a, const GBinPortion **b)
+{
+    int result;                             /* Bilan à retourner           */
+
+    result = mrange_includes_mrange(&(*b)->range, &(*a)->range);
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : portion = description de partie à mettre à jour.             *
 *                desc    = nom à donner à la partie.                          *
 *                                                                             *
@@ -654,12 +678,11 @@ void g_binary_portion_include(GBinPortion *portion, GBinPortion *sub)
 {
     bool found;                             /* Zone d'accueil trouvée ?    */
     size_t best;                            /* Meilleur point d'insertion  */
-    const mrange_t *prange;                 /* Emplacement de portion #1   */
-    const mrange_t *srange;                 /* Emplacement de portion #2   */
-    GBinPortion tmp;                        /* Sauvegarde temporaire       */
+    size_t i;                               /* Boucle de parcours          */
+    GBinPortion *tmp;                       /* Sauvegarde temporaire       */
 
-    found = bsearch_index(sub, portion->subs, portion->count, sizeof(GBinPortion *),
-                          (__compar_fn_t)g_binary_portion_compare, &best);
+    found = bsearch_index(&sub, portion->subs, portion->count, sizeof(GBinPortion *),
+                          (__compar_fn_t)g_binary_portion_is_included, &best);
 
     if (!found)
         portion->subs = qinsert(portion->subs, &portion->count, sizeof(GBinPortion *),
@@ -678,24 +701,30 @@ void g_binary_portion_include(GBinPortion *portion, GBinPortion *sub)
          * de zones mémoire.
          */
 
-        prange = g_binary_portion_get_range(portion->subs[best]);
-        srange = g_binary_portion_get_range(sub);
+        if (mrange_includes_mrange(&sub->range, &portion->subs[best]->range) == 0)
+        {
+            tmp = portion->subs[best];
 
-        if (mrange_contains_mrange(prange, srange))
-            g_binary_portion_include(portion->subs[best], sub);
+            for (i = portion->count; i > 0; i--)
+            {
+                tmp = portion->subs[i - 1];
 
-        else
-        {
-            assert(mrange_contains_mrange(srange, prange));
+                if (mrange_includes_mrange(&sub->range, &tmp->range) == 0)
+                {
+                    portion->subs = _qdelete(portion->subs, &portion->count, sizeof(GBinPortion *), i - 1);
+                    g_binary_portion_include(sub, tmp);
+                }
 
-            memcpy(&tmp, portion->subs[best], sizeof(GBinPortion));
-            memcpy(portion->subs[best], sub, sizeof(GBinPortion));
-            memcpy(sub, &tmp, sizeof(GBinPortion));
+            }
 
-            g_binary_portion_include(portion->subs[best], sub);
+            portion->subs = qinsert(portion->subs, &portion->count, sizeof(GBinPortion *),
+                                    (__compar_fn_t)g_binary_portion_compare, &sub);
 
         }
 
+        else
+            g_binary_portion_include(portion->subs[best], sub);
+
     }
 
 }
diff --git a/src/glibext/gbinportion.h b/src/glibext/gbinportion.h
index f05713e..a1ec105 100644
--- a/src/glibext/gbinportion.h
+++ b/src/glibext/gbinportion.h
@@ -84,6 +84,9 @@ GBinPortion *g_binary_portion_new(const char *, const vmpa2t *, phys_t);
 /* Etablit la comparaison ascendante entre deux portions. */
 int g_binary_portion_compare(const GBinPortion **, const GBinPortion **);
 
+/* Détermine si une portion est comprise dans une autre. */
+int g_binary_portion_is_included(const GBinPortion **, const GBinPortion **);
+
 /* Attribue une description humaine à une partie de code. */
 void g_binary_portion_set_desc(GBinPortion *, const char *);