lynx-dev another optimization for large html (patch2)

[Leonid Pauzner]

This is a simple optimization for generating a list page.

Files affected:  LYList.c, GridText.[c,h]


* optimization for large html files - with thousands of links -
  remove quadratic complexity when generating a 'l'ist page,
  now traverse once (linear). Not too much savings but trivial. - LP



diff -u -p -r LYNX2-8-.590/src/gridtext.h LYNX2-8-/src/gridtext.h
--- LYNX2-8-.590/src/gridtext.h Sun Oct  6 17:43:28 2002
+++ LYNX2-8-/src/gridtext.h     Sat Oct 12 04:47:24 2002
@@ -64,7 +64,8 @@ extern HTParentAnchor * HTMainAnchor; /*
 #if defined(VMS) && defined(VAXC) && !defined(__DECC)
 extern int HTVirtualMemorySize;
 #endif /* VMS && VAXC && !__DECC */
-extern HTChildAnchor * HText_childNumber PARAMS((int n));
+
+extern HTChildAnchor * HText_childNextNumber PARAMS((int n, void** prev));
 extern void HText_FormDescNumber PARAMS((int n, char **desc));

 /*     Is there any file left?
diff -u -p -r LYNX2-8-.590/src/lylist.c LYNX2-8-/src/lylist.c
--- LYNX2-8-.590/src/lylist.c   Sun Oct  6 17:43:28 2002
+++ LYNX2-8-/src/lylist.c       Sat Oct 12 04:47:00 2002
@@ -48,6 +48,7 @@ PUBLIC int showlist ARGS2(
     char *LinkTitle = NULL;  /* Rel stored as property of link, not of dest */
     BOOLEAN intern_w_post = FALSE;
     char *desc = "unknown field or link";
+    void* helper;

     refs = HText_sourceAnchors(HTMainText);
     hidden_links = HText_HiddenLinkCount(HTMainText);
@@ -102,8 +103,9 @@ PUBLIC int showlist ARGS2(
        if (LYHiddenLinks == HIDDENLINKS_IGNORE)
            hidden_links = 0;
     }
+    helper = NULL; /* init */
     for (cnt = 1; cnt <= refs; cnt++) {
-       HTChildAnchor *child = HText_childNumber(cnt);
+       HTChildAnchor *child = HText_childNextNumber(cnt, &helper);
        HTAnchor *dest_intl = NULL;
        HTAnchor *dest;
        HTParentAnchor *parent;
@@ -256,6 +258,7 @@ PUBLIC void printlist ARGS2(
     int refs, hidden_links;
     char *address = NULL;
     char *desc = gettext("unknown field or link");
+    void* helper;

     refs = HText_sourceAnchors(HTMainText);
     if (refs <= 0 && LYHiddenLinks != HIDDENLINKS_SEPARATE)
@@ -270,8 +273,9 @@ PUBLIC void printlist ARGS2(
            if (LYHiddenLinks == HIDDENLINKS_IGNORE)
                hidden_links = 0;
        }
+       helper = NULL; /* init */
        for (cnt = 1; cnt <= refs; cnt++) {
-           HTChildAnchor *child = HText_childNumber(cnt);
+           HTChildAnchor *child = HText_childNextNumber(cnt, &helper);
            HTAnchor *dest;
            HTParentAnchor *parent;
            CONST char *title;
diff -u -p -r LYNX2-8-.590/src/gridtext.c LYNX2-8-/src/gridtext.c
--- LYNX2-8-.590/src/gridtext.c Sun Oct  6 17:43:28 2002
+++ LYNX2-8-/src/gridtext.c     Sat Oct 12 20:16:48 2002
@@ -343,7 +349,7 @@ struct _HText {
 #endif
        HTLine *                last_line;
        int                     Lines;          /* Number of them */
-       TextAnchor *            first_anchor;   /* Singly linked list */
+       TextAnchor *            first_anchor;   /* double-linked list */
        TextAnchor *            last_anchor;
        TextAnchor *            last_anchor_before_stbl;
        HTList *                forms;          /* also linked internally */
@@ -5817,23 +5823,33 @@ PUBLIC HTParentAnchor * HText_nodeAnchor
 /*                             GridText specials
 **                             =================
 */
+
 /*
- *  HTChildAnchor() returns the anchor with index N.
- *  The index corresponds to the [number] we print for the anchor.
+ *  HText_childNextNumber() returns the anchor with index [number],
+ *  using a pointer from the previous number (=optimization) or NULL.
  */
-PUBLIC HTChildAnchor * HText_childNumber ARGS1(
-       int,            number)
+PUBLIC HTChildAnchor * HText_childNextNumber ARGS2(
+       int,            number,
+       void**,         prev)
 {
-    TextAnchor * a;
+    /* Sorry, TextAnchor is not declared outside this file, use a cast. */
+    TextAnchor * a = *prev;

-    if (!(HTMainText && HTMainText->first_anchor) || number <= 0)
+    if (!HTMainText || number <= 0)
        return (HTChildAnchor *)0;      /* Fail */
+    if (number == 1 || !a)
+       a = HTMainText->first_anchor;

-    for (a = HTMainText->first_anchor; a; a = a->next) {
-       if (a->number == number)
-           return(a->anchor);
-    }
-    return (HTChildAnchor *)0; /* Fail */
+    /* a strange thing:  positive a->number's are sorted,
+     * and between them several a->number's may be 0 -- skip them
+     */
+    for( ; a && a->number != number; a = a->next)
+       ;
+
+    if (!a)
+       return (HTChildAnchor *)0;      /* Fail */
+    *prev = (void*)a;
+    return a->anchor;
 }

 /*
@@ -10773,7 +10789,7 @@ PUBLIC int HText_SubmitForm ARGS4(
     }
     FREE(previous_blanks);

-    CTRACE((tfp, "QUERY (%d) >> \n%s\n", strlen(query), query));
+    CTRACE((tfp, "QUERY (%ld) >> \n%s\n", strlen(query), query));

     if (submit_item->submit_method == URL_MAIL_METHOD) {
        HTUserMsg2(gettext("Submitting %s"), submit_item->submit_action);



; To UNSUBSCRIBE: Send "unsubscribe lynx-dev" to address@hidden