bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: diffseq: Introduce EQUAL_IDX for comparing indexes instead of elemen


From: Bruno Haible
Subject: Re: diffseq: Introduce EQUAL_IDX for comparing indexes instead of elements
Date: Mon, 19 Apr 2010 00:04:54 +0200
User-agent: KMail/1.9.9

Hi Andreas,

> > patch has a historic 
> > feature called "plan B" for when only little memory is available; it then
> > doesn't load the entire patch and file to be patched into memory.  To
> >  support this, the file and patch are accessed through functions rather
> >  than directly as arrays. ...
> > 
> > Is this change acceptable?

Hmm. It's ok to accommodate more general use-cases of the existing code.
But I'm not happy
  1) about the use of local variables 'xv', 'yv' in a macro that is defined
     outside of functions,
  2) about the use of '#ifdef EQUAL' as a trigger to the storage of some
     variables in the context. It looks odd, like a misnomer.

I'm applying this instead. It should be trivial for you to update
patch/src/merge.c accordingly.


2010-04-18  Andreas Gruenbacher  <address@hidden>
            Bruno Haible  <address@hidden>

        diffseq: Accommodate use-case with abstract arrays.
        * lib/diffseq.h (struct context): Remove xvec, yvec fields if ELEMENT
        is not defined.
        (diag, compareseq): Remove local variables xv, yv if ELEMENT is not
        defined. Use local macro XREF_YREF_EQUAL instead of EQUAL.

--- lib/diffseq.h.orig  Sun Apr 18 23:55:29 2010
+++ lib/diffseq.h       Sun Apr 18 23:53:39 2010
@@ -53,6 +53,14 @@
                              early abort of the computation.
      USE_HEURISTIC           (Optional) Define if you want to support the
                              heuristic for large vectors.
+   It is also possible to you this file with abstract arrays.  In this case,
+   xvec and yvec are not represented in memory.  They only exist conceptually.
+   In this case, the list of defines above is amended as follows:
+     ELEMENT                 Undefined.
+     EQUAL                   Undefined.
+     XVECREF_YVECREF_EQUAL(ctxt, xoff, yoff)
+                             A three-argument macro: References xvec[xoff] and
+                             yvec[yoff] and tests these elements for equality.
    Before including this file, you also need to include:
      #include <limits.h>
      #include <stdbool.h>
@@ -92,9 +100,11 @@
  */
 struct context
 {
+  #ifdef ELEMENT
   /* Vectors being compared.  */
   ELEMENT const *xvec;
   ELEMENT const *yvec;
+  #endif
 
   /* Extra fields.  */
   EXTRA_CONTEXT_FIELDS
@@ -170,8 +180,13 @@
 {
   OFFSET *const fd = ctxt->fdiag;       /* Give the compiler a chance. */
   OFFSET *const bd = ctxt->bdiag;       /* Additional help for the compiler. */
+#ifdef ELEMENT
   ELEMENT const *const xv = ctxt->xvec; /* Still more help for the compiler. */
   ELEMENT const *const yv = ctxt->yvec; /* And more and more . . . */
+  #define XREF_YREF_EQUAL(x,y)  EQUAL (xv[x], yv[y])
+#else
+  #define XREF_YREF_EQUAL(x,y)  XVECREF_YVECREF_EQUAL (ctxt, x, y)
+#endif
   const OFFSET dmin = xoff - ylim;      /* Minimum valid diagonal. */
   const OFFSET dmax = xlim - yoff;      /* Maximum valid diagonal. */
   const OFFSET fmid = xoff - yoff;      /* Center diagonal of top-down search. 
*/
@@ -210,7 +225,7 @@
           OFFSET x0 = tlo < thi ? thi : tlo + 1;
 
           for (x = x0, y = x0 - d;
-               x < xlim && y < ylim && EQUAL (xv[x], yv[y]);
+               x < xlim && y < ylim && XREF_YREF_EQUAL (x, y);
                x++, y++)
             continue;
           if (x - x0 > SNAKE_LIMIT)
@@ -243,7 +258,7 @@
           OFFSET x0 = tlo < thi ? tlo : thi - 1;
 
           for (x = x0, y = x0 - d;
-               xoff < x && yoff < y && EQUAL (xv[x - 1], yv[y - 1]);
+               xoff < x && yoff < y && XREF_YREF_EQUAL (x - 1, y - 1);
                x--, y--)
             continue;
           if (x0 - x > SNAKE_LIMIT)
@@ -292,7 +307,7 @@
                            that it end with a significant snake.  */
                         int k;
 
-                        for (k = 1; EQUAL (xv[x - k], yv[y - k]); k++)
+                        for (k = 1; XREF_YREF_EQUAL (x - k, y - k); k++)
                           if (k == SNAKE_LIMIT)
                             {
                               best = v;
@@ -331,7 +346,7 @@
                            that it end with a significant snake.  */
                         int k;
 
-                        for (k = 0; EQUAL (xv[x + k], yv[y + k]); k++)
+                        for (k = 0; XREF_YREF_EQUAL (x + k, y + k); k++)
                           if (k == SNAKE_LIMIT - 1)
                             {
                               best = v;
@@ -415,6 +430,7 @@
           return;
         }
     }
+  #undef XREF_YREF_EQUAL
 }
 
 
@@ -438,18 +454,23 @@
 compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
             bool find_minimal, struct context *ctxt)
 {
+#ifdef ELEMENT
   ELEMENT const *xv = ctxt->xvec; /* Help the compiler.  */
   ELEMENT const *yv = ctxt->yvec;
+  #define XREF_YREF_EQUAL(x,y)  EQUAL (xv[x], yv[y])
+#else
+  #define XREF_YREF_EQUAL(x,y)  XVECREF_YVECREF_EQUAL (ctxt, x, y)
+#endif
 
   /* Slide down the bottom initial diagonal.  */
-  while (xoff < xlim && yoff < ylim && EQUAL (xv[xoff], yv[yoff]))
+  while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xoff, yoff))
     {
       xoff++;
       yoff++;
     }
 
   /* Slide up the top initial diagonal. */
-  while (xoff < xlim && yoff < ylim && EQUAL (xv[xlim - 1], yv[ylim - 1]))
+  while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xlim - 1, ylim - 1))
     {
       xlim--;
       ylim--;
@@ -487,6 +508,7 @@
     }
 
   return false;
+  #undef XREF_YREF_EQUAL
 }
 
 #undef ELEMENT
@@ -497,4 +519,5 @@
 #undef NOTE_INSERT
 #undef EARLY_ABORT
 #undef USE_HEURISTIC
+#undef XVECREF_YVECREF_EQUAL
 #undef OFFSET_MAX




reply via email to

[Prev in Thread] Current Thread [Next in Thread]