OSSP CVS Repository

ossp - Check-in [2667]
Not logged in 		[Honeypot]  [Browse]  [Home]  [Login]  [Reports] 
[Search]  [Ticket]  [Timeline] 
  [Patchset]  [Tagging/Branching] 

Check-in Number: 2667
Date: 2002-Oct-25 15:29:02 (local)
2002-Oct-25 13:29:02 (UTC)
User:mlelstv
Branch:
Comment: optimize al_splice to unlink/relink several chunks in a single step added necessary list macros to list.h

PR: Submitted by: Reviewed by: Approved by: Obtained from:

Tickets:
Inspections:
Files:
ossp-pkg/sio/al.c      1.31 -> 1.32     29 inserted, 9 deleted
ossp-pkg/sio/list.h      1.2 -> 1.3     33 inserted, 29 deleted
ossp-pkg/sio/al.c 1.31 -> 1.32 

--- al.c 2002/10/23 16:49:29     1.31
+++ al.c 2002/10/25 13:29:02     1.32
@@ -611,7 +611,7 @@
 al_splice(al_t *al, size_t off, size_t n, al_t *nal, al_t *tal)
 {
     al_rc_t rc;
-    al_chunk_t *cur, *next, *ins, *splitbuf;
+    al_chunk_t *cur, *start, *end, *next, *ins, *splitbuf;
     size_t pos, skip, len, step;
     int doinsert;
 
@@ -730,12 +730,14 @@
         }
         else {
             /*
-             * the whole chunk has to be moved, simply move it
-             * to the target chain
+             * the whole chunk has to be moved,
+             *
+             * scan ahead for more such chunks to unlink
+             * and relink a whole chain in a single operation
+             *
+             * move the chunks to the target chain
              * manual accounting for total size
              */
-            step = len;
-            REMOVE(al, chunks, cur);
 
             /*
              * when the insertion chunk is removed, we have to adjust
@@ -745,14 +747,32 @@
              * next pointer and the insertion method switches to append
              * mode
              */
+
+            step  = len;
+            start = cur;
+            end   = cur;
+
             if (cur == ins)
                 ins = next;
 
+            while (next && step + (len = AL_CHUNK_LEN(next)) <= n) {
+                step += len;
+                end  = next;
+                next = NEXT(next, chunks);
+                if (end == ins)
+                    ins = next;
+            }
+            REMOVE2(al, chunks, start, end);
+
             al->bytes -= step;
-            if (tal == NULL)
-                dispose_chunk(al, cur);
-            else {
-                ADDTAIL(tal, chunks, cur);
+            if (tal == NULL) {
+                do {
+                    cur = start;
+                    start = NEXT(cur, chunks);
+                    dispose_chunk(al, cur);
+                } while (cur != end);
+            } else {
+                ADDTAIL2(tal, chunks, start, end);
                 tal->bytes += step;
             }
         }

ossp-pkg/sio/list.h 1.2 -> 1.3 

--- list.h       2002/10/18 10:21:41     1.2
+++ list.h       2002/10/25 13:29:02     1.3
@@ -56,31 +56,33 @@
     PREV(n,l) = NULL; \
 } while(0)
 
-#define ADDTAIL(q,l,n) \
+#define ADDTAIL2(q,l,n1,n2) \
 do { \
     if (TAIL(q,l)) { \
-        NEXT(TAIL(q,l),l) = (n); \
-        PREV(n,l) = TAIL(q,l); \
+        NEXT(TAIL(q,l),l) = (n1); \
+        PREV(n1,l) = TAIL(q,l); \
     } else { \
-        PREV(n,l) = NULL; \
-        HEAD(q,l) = (n); \
+        HEAD(q,l) = (n1); \
+        PREV(n1,l) = NULL; \
     } \
-    TAIL(q,l) = (n); \
-    NEXT(n,l) = NULL; \
+    TAIL(q,l) = (n2); \
+    NEXT(n2,l) = NULL; \
 } while (0)
+#define ADDTAIL(q,l,n) ADDTAIL2(q,l,n,n)
 
-#define ADDHEAD(q,l,n) \
+#define ADDHEAD2(q,l,n1,n2) \
 do { \
     if (HEAD(q,l)) { \
-        PREV(HEAD(q,l),l) = (n); \
-        NEXT(n,l) = HEAD(q,l); \
+        PREV(HEAD(q,l),l) = (n2); \
+        NEXT(n2,l) = HEAD(q,l); \
     } else { \
-        NEXT(n,l) = NULL; \
-        TAIL(q,l) = (n); \
+        TAIL(q,l) = (n2); \
+        NEXT(n2,l) = NULL; \
     } \
-    HEAD(q,l) = (n); \
-    PREV(n,l) = NULL; \
+    HEAD(q,l) = (n1); \
+    PREV(n1,l) = NULL; \
 } while (0)
+#define ADDHEAD(q,l,n) ADDHEAD2(q,l,n,n)
 
 #define REMHEAD(q,l,n) \
 do { \
@@ -106,31 +108,33 @@
     } \
 } while(0)
 
-#define REMOVE(q,l,n) \
+#define REMOVE2(q,l,n1,n2) \
 do { \
-    if (PREV(n,l)) \
-        NEXT(PREV(n,l),l) = NEXT(n,l); \
+    if (PREV(n1,l)) \
+        NEXT(PREV(n1,l),l) = NEXT(n2,l); \
     else \
-        HEAD(q,l) = NEXT(n,l); \
-    if (NEXT(n,l)) \
-        PREV(NEXT(n,l),l) = PREV(n,l); \
+        HEAD(q,l) = NEXT(n2,l); \
+    if (NEXT(n2,l)) \
+        PREV(NEXT(n2,l),l) = PREV(n1,l); \
     else \
-        TAIL(q,l) = PREV(n,l); \
-    NEXT(n,l) = NULL; \
-    PREV(n,l) = NULL; \
+        TAIL(q,l) = PREV(n1,l); \
+    NEXT(n2,l) = NULL; \
+    PREV(n1,l) = NULL; \
 } while (0)
+#define REMOVE(q,l,n) REMOVE2(q,l,n,n)
 
-#define INSERT(q,l,i,n) \
+#define INSERT2(q,l,i,n1,n2) \
 do { \
     if (PREV(i,l)) { \
-        NEXT(PREV(i,l),l) = (n); \
+        NEXT(PREV(i,l),l) = (n1); \
     } else { \
-        HEAD(q,l) = (n); \
+        HEAD(q,l) = (n1); \
     } \
-    PREV(n,l) = PREV(i,l); \
-    PREV(i,l) = (n); \
-    NEXT(n,l) = (i); \
+    PREV(n1,l) = PREV(i,l); \
+    PREV(i,l) = (n2); \
+    NEXT(n2,l) = (i); \
 } while (0)
+#define INSERT(q,l,i,n) INSERT2(q,l,i,n,n)
 
 #define APPENDLIST(q1,l,q2) \
 do { \

CVSTrac 2.0.1