[Qemu-devel] [PULL 14/36] range: Eliminate direct Range member access

From: "Michael S. Tsirkin" <mst@redhat.com>
To: qemu-devel@nongnu.org
Cc: Peter Maydell <peter.maydell@linaro.org>,
	Markus Armbruster <armbru@redhat.com>,
	Eric Blake <eblake@redhat.com>,
	Igor Mammedov <imammedo@redhat.com>,
	Paolo Bonzini <pbonzini@redhat.com>,
	Richard Henderson <rth@twiddle.net>,
	Eduardo Habkost <ehabkost@redhat.com>,
	Marcel Apfelbaum <marcel@redhat.com>,
	Michael Roth <mdroth@linux.vnet.ibm.com>
Subject: [Qemu-devel] [PULL 14/36] range: Eliminate direct Range member access
Date: Mon, 4 Jul 2016 19:46:58 +0300	[thread overview]
Message-ID: <20160704194658-mutt-send-email-mst@redhat.com> (raw)
In-Reply-To: <1467650742-17580-1-git-send-email-mst@redhat.com>

From: Markus Armbruster <armbru@redhat.com>

Users of struct Range mess liberally with its members, which makes
refactoring hard.  Create a set of methods, and convert all users to
call them instead of accessing members.  The methods have carefully
worded contracts, and use assertions to check them.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
Reviewed-by: Michael S. Tsirkin <mst@redhat.com>
Reviewed-by: Michael S. Tsirkin <mst@redhat.com>
Signed-off-by: Michael S. Tsirkin <mst@redhat.com>
---
 include/qemu/range.h         | 85 ++++++++++++++++++++++++++++++++++++++++++--
 hw/i386/acpi-build.c         | 35 +++++++++---------
 hw/pci-host/piix.c           | 26 +++++++++-----
 hw/pci-host/q35.c            | 41 +++++++++++++--------
 hw/pci/pci.c                 | 17 ++++-----
 qapi/string-input-visitor.c  | 20 +++++------
 qapi/string-output-visitor.c | 18 +++++-----
 util/log.c                   |  5 ++-
 util/range.c                 |  3 +-
 9 files changed, 176 insertions(+), 74 deletions(-)

diff --git a/include/qemu/range.h b/include/qemu/range.h
index 3970f00..c8c46a9 100644
--- a/include/qemu/range.h
+++ b/include/qemu/range.h
@@ -36,12 +36,91 @@ struct Range {
     uint64_t end;   /* 1 + the last byte. 0 if range empty or ends at ~0x0LL. */
 };
 
+static inline void range_invariant(Range *range)
+{
+    assert((!range->begin && !range->end) /* empty */
+           || range->begin <= range->end - 1); /* non-empty */
+}
+
+/* Compound literal encoding the empty range */
+#define range_empty ((Range){ .begin = 0, .end = 0 })
+
+/* Is @range empty? */
+static inline bool range_is_empty(Range *range)
+{
+    range_invariant(range);
+    return !range->begin && !range->end;
+}
+
+/* Does @range contain @val? */
+static inline bool range_contains(Range *range, uint64_t val)
+{
+    return !range_is_empty(range)
+        && val >= range->begin && val <= range->end - 1;
+}
+
+/* Initialize @range to the empty range */
+static inline void range_make_empty(Range *range)
+{
+    *range = range_empty;
+    assert(range_is_empty(range));
+}
+
+/*
+ * Initialize @range to span the interval [@lob,@upb].
+ * Both bounds are inclusive.
+ * The interval must not be empty, i.e. @lob must be less than or
+ * equal @upb.
+ * The interval must not be [0,UINT64_MAX], because Range can't
+ * represent that.
+ */
+static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb)
+{
+    assert(lob <= upb);
+    range->begin = lob;
+    range->end = upb + 1;       /* may wrap to zero, that's okay */
+    assert(!range_is_empty(range));
+}
+
+/*
+ * Initialize @range to span the interval [@lob,@upb_plus1).
+ * The lower bound is inclusive, the upper bound is exclusive.
+ * Zero @upb_plus1 is special: if @lob is also zero, set @range to the
+ * empty range.  Else, set @range to [@lob,UINT64_MAX].
+ */
+static inline void range_set_bounds1(Range *range,
+                                     uint64_t lob, uint64_t upb_plus1)
+{
+    range->begin = lob;
+    range->end = upb_plus1;
+    range_invariant(range);
+}
+
+/* Return @range's lower bound.  @range must not be empty. */
+static inline uint64_t range_lob(Range *range)
+{
+    assert(!range_is_empty(range));
+    return range->begin;
+}
+
+/* Return @range's upper bound.  @range must not be empty. */
+static inline uint64_t range_upb(Range *range)
+{
+    assert(!range_is_empty(range));
+    return range->end - 1;
+}
+
+/*
+ * Extend @range to the smallest interval that includes @extend_by, too.
+ * This must not extend @range to cover the interval [0,UINT64_MAX],
+ * because Range can't represent that.
+ */
 static inline void range_extend(Range *range, Range *extend_by)
 {
-    if (!extend_by->begin && !extend_by->end) {
+    if (range_is_empty(extend_by)) {
         return;
     }
-    if (!range->begin && !range->end) {
+    if (range_is_empty(range)) {
         *range = *extend_by;
         return;
     }
@@ -52,6 +131,8 @@ static inline void range_extend(Range *range, Range *extend_by)
     if (range->end - 1 < extend_by->end - 1) {
         range->end = extend_by->end;
     }
+    /* Must not extend to { .begin = 0, .end = 0 }: */
+    assert(!range_is_empty(range));
 }
 
 /* Get last byte of a range from offset + length.
diff --git a/hw/i386/acpi-build.c b/hw/i386/acpi-build.c
index 576c7af..fbba461 100644
--- a/hw/i386/acpi-build.c
+++ b/hw/i386/acpi-build.c
@@ -236,18 +236,20 @@ static void acpi_get_pci_holes(Range *hole, Range *hole64)
     pci_host = acpi_get_i386_pci_host();
     g_assert(pci_host);
 
-    hole->begin = object_property_get_int(pci_host,
-                                          PCI_HOST_PROP_PCI_HOLE_START,
-                                          NULL);
-    hole->end = object_property_get_int(pci_host,
-                                        PCI_HOST_PROP_PCI_HOLE_END,
-                                        NULL);
-    hole64->begin = object_property_get_int(pci_host,
-                                            PCI_HOST_PROP_PCI_HOLE64_START,
-                                            NULL);
-    hole64->end = object_property_get_int(pci_host,
-                                          PCI_HOST_PROP_PCI_HOLE64_END,
-                                          NULL);
+    range_set_bounds1(hole,
+                      object_property_get_int(pci_host,
+                                              PCI_HOST_PROP_PCI_HOLE_START,
+                                              NULL),
+                      object_property_get_int(pci_host,
+                                              PCI_HOST_PROP_PCI_HOLE_END,
+                                              NULL));
+    range_set_bounds1(hole64,
+                      object_property_get_int(pci_host,
+                                              PCI_HOST_PROP_PCI_HOLE64_START,
+                                              NULL),
+                      object_property_get_int(pci_host,
+                                              PCI_HOST_PROP_PCI_HOLE64_END,
+                                              NULL));
 }
 
 #define ACPI_PORT_SMI_CMD           0x00b2 /* TODO: this is APM_CNT_IOPORT */
@@ -2047,7 +2049,8 @@ build_dsdt(GArray *table_data, BIOSLinker *linker,
                          0, 0x000A0000, 0x000BFFFF, 0, 0x00020000));
 
     crs_replace_with_free_ranges(mem_ranges,
-                                 pci_hole->begin, pci_hole->end - 1);
+                                 range_lob(pci_hole),
+                                 range_upb(pci_hole));
     for (i = 0; i < mem_ranges->len; i++) {
         entry = g_ptr_array_index(mem_ranges, i);
         aml_append(crs,
@@ -2057,12 +2060,12 @@ build_dsdt(GArray *table_data, BIOSLinker *linker,
                              0, entry->limit - entry->base + 1));
     }
 
-    if (pci_hole64->begin) {
+    if (!range_is_empty(pci_hole64)) {
         aml_append(crs,
             aml_qword_memory(AML_POS_DECODE, AML_MIN_FIXED, AML_MAX_FIXED,
                              AML_CACHEABLE, AML_READ_WRITE,
-                             0, pci_hole64->begin, pci_hole64->end - 1, 0,
-                             pci_hole64->end - pci_hole64->begin));
+                             0, range_lob(pci_hole64), range_upb(pci_hole64), 0,
+                             range_upb(pci_hole64) + 1 - range_lob(pci_hole64)));
     }
 
     if (misc->tpm_version != TPM_VERSION_UNSPEC) {
diff --git a/hw/pci-host/piix.c b/hw/pci-host/piix.c
index b1bfc59..f9218aa 100644
--- a/hw/pci-host/piix.c
+++ b/hw/pci-host/piix.c
@@ -221,8 +221,12 @@ static void i440fx_pcihost_get_pci_hole_start(Object *obj, Visitor *v,
                                               Error **errp)
 {
     I440FXState *s = I440FX_PCI_HOST_BRIDGE(obj);
-    uint32_t value = s->pci_hole.begin;
+    uint64_t val64;
+    uint32_t value;
 
+    val64 = range_is_empty(&s->pci_hole) ? 0 : range_lob(&s->pci_hole);
+    value = val64;
+    assert(value == val64);
     visit_type_uint32(v, name, &value, errp);
 }
 
@@ -231,8 +235,12 @@ static void i440fx_pcihost_get_pci_hole_end(Object *obj, Visitor *v,
                                             Error **errp)
 {
     I440FXState *s = I440FX_PCI_HOST_BRIDGE(obj);
-    uint32_t value = s->pci_hole.end;
+    uint64_t val64;
+    uint32_t value;
 
+    val64 = range_is_empty(&s->pci_hole) ? 0 : range_upb(&s->pci_hole) + 1;
+    value = val64;
+    assert(value == val64);
     visit_type_uint32(v, name, &value, errp);
 }
 
@@ -242,10 +250,11 @@ static void i440fx_pcihost_get_pci_hole64_start(Object *obj, Visitor *v,
 {
     PCIHostState *h = PCI_HOST_BRIDGE(obj);
     Range w64;
+    uint64_t value;
 
     pci_bus_get_w64_range(h->bus, &w64);
-
-    visit_type_uint64(v, name, &w64.begin, errp);
+    value = range_is_empty(&w64) ? 0 : range_lob(&w64);
+    visit_type_uint64(v, name, &value, errp);
 }
 
 static void i440fx_pcihost_get_pci_hole64_end(Object *obj, Visitor *v,
@@ -254,10 +263,11 @@ static void i440fx_pcihost_get_pci_hole64_end(Object *obj, Visitor *v,
 {
     PCIHostState *h = PCI_HOST_BRIDGE(obj);
     Range w64;
+    uint64_t value;
 
     pci_bus_get_w64_range(h->bus, &w64);
-
-    visit_type_uint64(v, name, &w64.end, errp);
+    value = range_is_empty(&w64) ? 0 : range_upb(&w64) + 1;
+    visit_type_uint64(v, name, &value, errp);
 }
 
 static void i440fx_pcihost_initfn(Object *obj)
@@ -344,8 +354,8 @@ PCIBus *i440fx_init(const char *host_type, const char *pci_type,
     f->ram_memory = ram_memory;
 
     i440fx = I440FX_PCI_HOST_BRIDGE(dev);
-    i440fx->pci_hole.begin = below_4g_mem_size;
-    i440fx->pci_hole.end = IO_APIC_DEFAULT_ADDRESS;
+    range_set_bounds(&i440fx->pci_hole, below_4g_mem_size,
+                     IO_APIC_DEFAULT_ADDRESS - 1);
 
     /* setup pci memory mapping */
     pc_pci_as_mapping_init(OBJECT(f), f->system_memory,
diff --git a/hw/pci-host/q35.c b/hw/pci-host/q35.c
index f908ba3..344f77b 100644
--- a/hw/pci-host/q35.c
+++ b/hw/pci-host/q35.c
@@ -74,8 +74,13 @@ static void q35_host_get_pci_hole_start(Object *obj, Visitor *v,
                                         Error **errp)
 {
     Q35PCIHost *s = Q35_HOST_DEVICE(obj);
-    uint32_t value = s->mch.pci_hole.begin;
+    uint64_t val64;
+    uint32_t value;
 
+    val64 = range_is_empty(&s->mch.pci_hole)
+        ? 0 : range_lob(&s->mch.pci_hole);
+    value = val64;
+    assert(value == val64);
     visit_type_uint32(v, name, &value, errp);
 }
 
@@ -84,8 +89,13 @@ static void q35_host_get_pci_hole_end(Object *obj, Visitor *v,
                                       Error **errp)
 {
     Q35PCIHost *s = Q35_HOST_DEVICE(obj);
-    uint32_t value = s->mch.pci_hole.end;
+    uint64_t val64;
+    uint32_t value;
 
+    val64 = range_is_empty(&s->mch.pci_hole)
+        ? 0 : range_upb(&s->mch.pci_hole) + 1;
+    value = val64;
+    assert(value == val64);
     visit_type_uint32(v, name, &value, errp);
 }
 
@@ -95,10 +105,11 @@ static void q35_host_get_pci_hole64_start(Object *obj, Visitor *v,
 {
     PCIHostState *h = PCI_HOST_BRIDGE(obj);
     Range w64;
+    uint64_t value;
 
     pci_bus_get_w64_range(h->bus, &w64);
-
-    visit_type_uint64(v, name, &w64.begin, errp);
+    value = range_is_empty(&w64) ? 0 : range_lob(&w64);
+    visit_type_uint64(v, name, &value, errp);
 }
 
 static void q35_host_get_pci_hole64_end(Object *obj, Visitor *v,
@@ -107,10 +118,11 @@ static void q35_host_get_pci_hole64_end(Object *obj, Visitor *v,
 {
     PCIHostState *h = PCI_HOST_BRIDGE(obj);
     Range w64;
+    uint64_t value;
 
     pci_bus_get_w64_range(h->bus, &w64);
-
-    visit_type_uint64(v, name, &w64.end, errp);
+    value = range_is_empty(&w64) ? 0 : range_upb(&w64) + 1;
+    visit_type_uint64(v, name, &value, errp);
 }
 
 static void q35_host_get_mmcfg_size(Object *obj, Visitor *v, const char *name,
@@ -205,9 +217,9 @@ static void q35_host_initfn(Object *obj)
      * it's not a power of two, which means an MTRR
      * can't cover it exactly.
      */
-    s->mch.pci_hole.begin = MCH_HOST_BRIDGE_PCIEXBAR_DEFAULT +
-        MCH_HOST_BRIDGE_PCIEXBAR_MAX;
-    s->mch.pci_hole.end = IO_APIC_DEFAULT_ADDRESS;
+    range_set_bounds(&s->mch.pci_hole,
+            MCH_HOST_BRIDGE_PCIEXBAR_DEFAULT + MCH_HOST_BRIDGE_PCIEXBAR_MAX,
+            IO_APIC_DEFAULT_ADDRESS - 1);
 }
 
 static const TypeInfo q35_host_info = {
@@ -275,10 +287,7 @@ static void mch_update_pciexbar(MCHPCIState *mch)
         break;
     case MCH_HOST_BRIDGE_PCIEXBAR_LENGTH_RVD:
     default:
-        enable = 0;
-        length = 0;
         abort();
-        break;
     }
     addr = pciexbar & addr_mask;
     pcie_host_mmcfg_update(pehb, enable, addr, length);
@@ -288,9 +297,13 @@ static void mch_update_pciexbar(MCHPCIState *mch)
      * which means an MTRR can't cover it exactly.
      */
     if (enable) {
-        mch->pci_hole.begin = addr + length;
+        range_set_bounds(&mch->pci_hole,
+                         addr + length,
+                         IO_APIC_DEFAULT_ADDRESS - 1);
     } else {
-        mch->pci_hole.begin = MCH_HOST_BRIDGE_PCIEXBAR_DEFAULT;
+        range_set_bounds(&mch->pci_hole,
+                         MCH_HOST_BRIDGE_PCIEXBAR_DEFAULT,
+                         IO_APIC_DEFAULT_ADDRESS - 1);
     }
 }
 
diff --git a/hw/pci/pci.c b/hw/pci/pci.c
index 8c2f6ed..149994b 100644
--- a/hw/pci/pci.c
+++ b/hw/pci/pci.c
@@ -2533,13 +2533,13 @@ static void pci_dev_get_w64(PCIBus *b, PCIDevice *dev, void *opaque)
 
         if (limit >= base) {
             Range pref_range;
-            pref_range.begin = base;
-            pref_range.end = limit + 1;
+            range_set_bounds(&pref_range, base, limit);
             range_extend(range, &pref_range);
         }
     }
     for (i = 0; i < PCI_NUM_REGIONS; ++i) {
         PCIIORegion *r = &dev->io_regions[i];
+        pcibus_t lob, upb;
         Range region_range;
 
         if (!r->size ||
@@ -2547,16 +2547,17 @@ static void pci_dev_get_w64(PCIBus *b, PCIDevice *dev, void *opaque)
             !(r->type & PCI_BASE_ADDRESS_MEM_TYPE_64)) {
             continue;
         }
-        region_range.begin = pci_bar_address(dev, i, r->type, r->size);
-        region_range.end = region_range.begin + r->size;
 
-        if (region_range.begin == PCI_BAR_UNMAPPED) {
+        lob = pci_bar_address(dev, i, r->type, r->size);
+        upb = lob + r->size - 1;
+        if (lob == PCI_BAR_UNMAPPED) {
             continue;
         }
 
-        region_range.begin = MAX(region_range.begin, 0x1ULL << 32);
+        lob = MAX(lob, 0x1ULL << 32);
 
-        if (region_range.end - 1 >= region_range.begin) {
+        if (upb >= lob) {
+            range_set_bounds(&region_range, lob, upb);
             range_extend(range, &region_range);
         }
     }
@@ -2564,7 +2565,7 @@ static void pci_dev_get_w64(PCIBus *b, PCIDevice *dev, void *opaque)
 
 void pci_bus_get_w64_range(PCIBus *bus, Range *range)
 {
-    range->begin = range->end = 0;
+    range_make_empty(range);
     pci_for_each_device_under_bus(bus, pci_dev_get_w64, range);
 }
 
diff --git a/qapi/string-input-visitor.c b/qapi/string-input-visitor.c
index b546e5f..0690abb 100644
--- a/qapi/string-input-visitor.c
+++ b/qapi/string-input-visitor.c
@@ -59,8 +59,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp)
         if (errno == 0 && endptr > str) {
             if (*endptr == '\0') {
                 cur = g_malloc0(sizeof(*cur));
-                cur->begin = start;
-                cur->end = start + 1;
+                range_set_bounds(cur, start, start);
                 siv->ranges = range_list_insert(siv->ranges, cur);
                 cur = NULL;
                 str = NULL;
@@ -73,16 +72,14 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp)
                      end < start + 65536)) {
                     if (*endptr == '\0') {
                         cur = g_malloc0(sizeof(*cur));
-                        cur->begin = start;
-                        cur->end = end + 1;
+                        range_set_bounds(cur, start, end);
                         siv->ranges = range_list_insert(siv->ranges, cur);
                         cur = NULL;
                         str = NULL;
                     } else if (*endptr == ',') {
                         str = endptr + 1;
                         cur = g_malloc0(sizeof(*cur));
-                        cur->begin = start;
-                        cur->end = end + 1;
+                        range_set_bounds(cur, start, end);
                         siv->ranges = range_list_insert(siv->ranges, cur);
                         cur = NULL;
                     } else {
@@ -94,8 +91,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp)
             } else if (*endptr == ',') {
                 str = endptr + 1;
                 cur = g_malloc0(sizeof(*cur));
-                cur->begin = start;
-                cur->end = start + 1;
+                range_set_bounds(cur, start, start);
                 siv->ranges = range_list_insert(siv->ranges, cur);
                 cur = NULL;
             } else {
@@ -134,7 +130,7 @@ start_list(Visitor *v, const char *name, GenericList **list, size_t size,
     if (siv->cur_range) {
         Range *r = siv->cur_range->data;
         if (r) {
-            siv->cur = r->begin;
+            siv->cur = range_lob(r);
         }
         *list = g_malloc0(size);
     } else {
@@ -156,7 +152,7 @@ static GenericList *next_list(Visitor *v, GenericList *tail, size_t size)
         return NULL;
     }
 
-    if (siv->cur < r->begin || siv->cur >= r->end) {
+    if (!range_contains(r, siv->cur)) {
         siv->cur_range = g_list_next(siv->cur_range);
         if (!siv->cur_range) {
             return NULL;
@@ -165,7 +161,7 @@ static GenericList *next_list(Visitor *v, GenericList *tail, size_t size)
         if (!r) {
             return NULL;
         }
-        siv->cur = r->begin;
+        siv->cur = range_lob(r);
     }
 
     tail->next = g_malloc0(size);
@@ -208,7 +204,7 @@ static void parse_type_int64(Visitor *v, const char *name, int64_t *obj,
             goto error;
         }
 
-        siv->cur = r->begin;
+        siv->cur = range_lob(r);
     }
 
     *obj = siv->cur;
diff --git a/qapi/string-output-visitor.c b/qapi/string-output-visitor.c
index 5ea395a..c6f01f9 100644
--- a/qapi/string-output-visitor.c
+++ b/qapi/string-output-visitor.c
@@ -83,8 +83,8 @@ static void string_output_set(StringOutputVisitor *sov, char *string)
 static void string_output_append(StringOutputVisitor *sov, int64_t a)
 {
     Range *r = g_malloc0(sizeof(*r));
-    r->begin = a;
-    r->end = a + 1;
+
+    range_set_bounds(r, a, a);
     sov->ranges = range_list_insert(sov->ranges, r);
 }
 
@@ -92,28 +92,28 @@ static void string_output_append_range(StringOutputVisitor *sov,
                                        int64_t s, int64_t e)
 {
     Range *r = g_malloc0(sizeof(*r));
-    r->begin = s;
-    r->end = e + 1;
+
+    range_set_bounds(r, s, e);
     sov->ranges = range_list_insert(sov->ranges, r);
 }
 
 static void format_string(StringOutputVisitor *sov, Range *r, bool next,
                           bool human)
 {
-    if (r->end - r->begin > 1) {
+    if (range_lob(r) != range_upb(r)) {
         if (human) {
             g_string_append_printf(sov->string, "0x%" PRIx64 "-0x%" PRIx64,
-                                   r->begin, r->end - 1);
+                                   range_lob(r), range_upb(r));
 
         } else {
             g_string_append_printf(sov->string, "%" PRId64 "-%" PRId64,
-                                   r->begin, r->end - 1);
+                                   range_lob(r), range_upb(r));
         }
     } else {
         if (human) {
-            g_string_append_printf(sov->string, "0x%" PRIx64, r->begin);
+            g_string_append_printf(sov->string, "0x%" PRIx64, range_lob(r));
         } else {
-            g_string_append_printf(sov->string, "%" PRId64, r->begin);
+            g_string_append_printf(sov->string, "%" PRId64, range_lob(r));
         }
     }
     if (next) {
diff --git a/util/log.c b/util/log.c
index f811d61..4da635c 100644
--- a/util/log.c
+++ b/util/log.c
@@ -132,7 +132,7 @@ bool qemu_log_in_addr_range(uint64_t addr)
         int i = 0;
         for (i = 0; i < debug_regions->len; i++) {
             Range *range = &g_array_index(debug_regions, Range, i);
-            if (addr >= range->begin && addr <= range->end - 1) {
+            if (range_contains(range, addr)) {
                 return true;
             }
         }
@@ -208,8 +208,7 @@ void qemu_set_dfilter_ranges(const char *filter_spec, Error **errp)
             error_setg(errp, "Invalid range");
             goto out;
         }
-        range.begin = lob;
-        range.end = upb + 1;
+        range_set_bounds(&range, lob, upb);
         g_array_append_val(debug_regions, range);
     }
 out:
diff --git a/util/range.c b/util/range.c
index e90c988..e5f2e71 100644
--- a/util/range.c
+++ b/util/range.c
@@ -46,8 +46,7 @@ GList *range_list_insert(GList *list, Range *data)
 {
     GList *l;
 
-    /* Range lists require no empty ranges */
-    assert(data->begin < data->end || (data->begin && !data->end));
+    assert(!range_is_empty(data));
 
     /* Skip all list elements strictly less than data */
     for (l = list; l && range_compare(l->data, data) < 0; l = l->next) {
-- 
MST
