Doxygen Performance Issues and Solutions

Index: src/util.cpp
===================================================================
--- src/util.cpp	(revision 803)
+++ src/util.cpp	(working copy)
@@ -20,6 +20,10 @@
 #include <errno.h>
 #include <math.h>
 
+#include <map>
+#include <vector>
+#include <algorithm>
+
 #include "md5.h"
 
 #include "qtbc.h"
@@ -849,6 +853,56 @@
 }
 
 
+struct isAccessibleFrom_visitedKey
+{
+  isAccessibleFrom_visitedKey(Definition *scope,FileDef *fileScope,Definition *item)
+  : _scope(scope), _fileScope(fileScope), _item(item)
+  {}
+
+  bool operator <(const struct isAccessibleFrom_visitedKey &other) const
+  {
+    if (_scope             < other._scope            )  return true;
+    if (_scope             > other._scope            )  return false;
+    if (_fileScope         < other._fileScope        )  return true;
+    if (_fileScope         > other._fileScope        )  return false;
+    if (_item              < other._item             )  return true;
+    if (_item              > other._item             )  return false;
+
+    return false;
+  }
+
+  bool operator ==(const struct isAccessibleFrom_visitedKey &other) const
+  {
+    if (_scope     == other._scope     &&
+        _fileScope == other._fileScope &&
+        _item      == other._item      )  
+      return true;
+
+    return false;
+  }
+
+  const Definition *_scope;
+  const FileDef *_fileScope;
+  const Definition *_item;
+};
+
+#define USE_ISACCESSIBLEFROM_CACHE
+
+#ifdef USE_ISACCESSIBLEFROM_CACHE
+static std::map<isAccessibleFrom_visitedKey, int> isAccessibleFromCache;
+
+/* Clear the isAccessibleFromCache. Claled between phases to avoid false matches */
+void clearIsAccessibleFromCache(void)
+{
+  isAccessibleFromCache.clear();
+}
+#else
+void clearIsAccessibleFromCache(void)
+{
+}
+#endif
+
+
 /* Returns the "distance" (=number of levels up) from item to scope, or -1
  * if item in not inside scope. 
  */
@@ -856,17 +910,32 @@
 {
   //printf("<isAccesibleFrom(scope=%s,item=%s itemScope=%s)\n",
   //    scope->name().data(),item->name().data(),item->getOuterScope()->name().data());
-
-  QCString key(40);
-  key.sprintf("%p:%p:%p",scope,fileScope,item);
-  static QDict<void> visitedDict;
-  if (visitedDict.find(key)) 
+  
+  isAccessibleFrom_visitedKey key(scope, fileScope, item);
+  
+#ifdef USE_ISACCESSIBLEFROM_CACHE
+  std::map<isAccessibleFrom_visitedKey, int>::iterator cit;
+  
+  cit = isAccessibleFromCache.find(key);
+  if (cit != isAccessibleFromCache.end())
   {
-    //printf("> already found\n");
+    return cit->second;
+  } 
+#endif
+  
+  static std::vector<isAccessibleFrom_visitedKey> visitedDict;
+  std::vector<isAccessibleFrom_visitedKey>::iterator it;
+  
+  it = std::find(visitedDict.begin(), visitedDict.end(), key);
+  
+  if (it != visitedDict.end()) 
+  {
+    //printf("Already visited!\n");
     return -1; // already looked at this
   }
-  visitedDict.insert(key,(void *)0x8);
 
+  visitedDict.push_back(key);
+
   int result=0; // assume we found it
   int i;
 
@@ -934,12 +1003,55 @@
     result= (i==-1) ? -1 : i+2;
   }
 done:
-  visitedDict.remove(key);
+//printf("isAccessibleFrom: leave %p %p %p dictsize %ld return %d\n", scope,fileScope,item,visitedDict.size(), result);
+  visitedDict.pop_back();
+  
+#ifdef USE_ISACCESSIBLEFROM_CACHE
+  isAccessibleFromCache[key] = result;
+#endif
+  
   //Doxygen::lookupCache.insert(key,new int(result));
   return result;
 }
 
+struct isAccessibleFromWithExpScope_visitedKey
+{
+  isAccessibleFromWithExpScope_visitedKey(Definition *scope,FileDef *fileScope,Definition *item, 
+          char *explicitScopePart)
+  : _scope(scope), _fileScope(fileScope), _item(item), 
+  _explicitScopePart(explicitScopePart)
+  {}
 
+  bool operator <(const struct isAccessibleFromWithExpScope_visitedKey &other) const
+  {
+    if (_scope             < other._scope            )  return true;
+    if (_scope             > other._scope            )  return false;
+    if (_item              < other._item             )  return true;
+    if (_item              > other._item             )  return false;
+    if (_fileScope         < other._fileScope        )  return true;
+    if (_fileScope         > other._fileScope        )  return false;
+    if (_explicitScopePart < other._explicitScopePart)  return true;
+    if (_explicitScopePart > other._explicitScopePart)  return false;
+
+    return false;
+  }
+
+  bool operator ==(const struct isAccessibleFromWithExpScope_visitedKey &other) const
+  {
+    if (_scope             == other._scope             &&
+        _fileScope         == other._fileScope         &&
+        _item              == other._item              &&  
+        _explicitScopePart == other._explicitScopePart      )  
+      return true;
+
+    return false;
+  }
+  const Definition *_scope;
+  const FileDef *_fileScope;
+  const Definition *_item;
+  const char *_explicitScopePart;
+};
+
 /* Returns the "distance" (=number of levels up) from item to scope, or -1
  * if item in not in this scope. The explicitScopePart limits the search
  * to scopes that match \a scope (or its parent scope(s)) plus the explicit part.
@@ -963,16 +1075,20 @@
     // handle degenerate case where there is no explicit scope.
     return isAccessibleFrom(scope,fileScope,item);
   }
-
-  QCString key(40+explicitScopePart.length());
-  key.sprintf("%p:%p:%p:%s",scope,fileScope,item,explicitScopePart.data());
-  static QDict<void> visitedDict;
-  if (visitedDict.find(key)) 
+  
+  static std::vector<isAccessibleFromWithExpScope_visitedKey> visitedDict;
+  std::vector<isAccessibleFromWithExpScope_visitedKey>::iterator it;
+  
+  isAccessibleFromWithExpScope_visitedKey key(scope,fileScope,item,explicitScopePart.data());
+  
+  it = std::find(visitedDict.begin(), visitedDict.end(), key);
+  
+  if (it != visitedDict.end()) 
   {
     //printf("Already visited!\n");
     return -1; // already looked at this
   }
-  visitedDict.insert(key,(void *)0x8);
+  visitedDict.push_back(key);
 
   //printf("  <isAccessibleFromWithExpScope(%s,%s,%s)\n",scope?scope->name().data():"<global>",
   //                                      item?item->name().data():"<none>",
@@ -1103,7 +1219,7 @@
   }
 done:
   //printf("  > result=%d\n",result);
-  visitedDict.remove(key);
+  visitedDict.pop_back();
   //Doxygen::lookupCache.insert(key,new int(result));
   return result;
 }
@@ -1766,7 +1882,7 @@
     { 
       if (txtStr.at(i)=='"') insideString=!insideString; 
     }
-
+///!!! why?    autoBreak = false;
     //printf("floatingIndex=%d strlen=%d autoBreak=%d\n",floatingIndex,strLen,autoBreak);
     if (strLen>35 && floatingIndex>30 && autoBreak) // try to insert a split point
     {
@@ -3231,7 +3347,7 @@
     //printf("word=%s typeString=%s\n",word.data(),mType->typeString());
     if (word!=mType->typeString())
     {
-      result = getCanonicalTypeForIdentifier(d,fs,mType->typeString(),tSpec,count+1);
+      result = getCanonicalTypeForIdentifier(d,fs,mType->typeString(),tSpec,++count);
     }
     else
     {
Index: src/lodepng.cpp
===================================================================
--- src/lodepng.cpp	(revision 803)
+++ src/lodepng.cpp	(working copy)
@@ -165,6 +165,16 @@
   p->size = p->allocsize = 0;
 }
 
+static void uivector_clear(uivector* p)
+{
+  memset(p->data, 0, p->size * sizeof(unsigned));
+}
+
+static void uivector_reset(uivector* p)
+{
+  p->size = 0;
+}
+
 #ifdef LODEPNG_COMPILE_ENCODER
 static unsigned uivector_push_back(uivector* p, unsigned c) /*returns 1 if success, 0 if failure ==> nothing done*/
 {
@@ -1033,15 +1043,74 @@
   uivector_push_back(values, extra_distance);
 }
 
-#if 0
+#if 1
+
 /*the "brute force" version of the encodeLZ7 algorithm, not used anymore, kept here for reference*/
-static void encodeLZ77_brute(uivector* out, const unsigned char* in, size_t size, unsigned windowSize)
+static unsigned encodeLZ77(uivector* out, const unsigned char* in, size_t size, unsigned windowSize)
 {
   size_t pos;
   /*using pointer instead of vector for input makes it faster when NOT using optimization when compiling; no influence if optimization is used*/
   for(pos = 0; pos < size; pos++)
   {
-    size_t length = 0, offset = 0; /*the length and offset found for the current position*/
+    /*Phase 1: doxygen images often have long runs of the same color, try to find them*/   
+    const int minLength = 4; // Minimum length for a run to make sense
+    
+    if(pos < size - minLength * 4)
+    {
+      size_t p, fp;
+      size_t current_length;
+      
+      /*RGBA pixel run?*/
+      p  = pos;
+      fp = pos + 4;
+      current_length = 0;
+      
+      while(fp < size && in[p] == in[fp] && current_length < MAX_SUPPORTED_DEFLATE_LENGTH)
+      {
+        ++p;
+        ++fp;
+        ++current_length;
+      }
+      
+      if (current_length > (minLength - 1 ) * 4) /*worth using?*/
+      {
+        uivector_push_back(out, in[pos    ]);
+        uivector_push_back(out, in[pos + 1]);
+        uivector_push_back(out, in[pos + 2]);
+        uivector_push_back(out, in[pos + 3]);
+        addLengthDistance(out, current_length, 4);
+        
+        pos += current_length + 4 - 1; /*-1 for loop's pos++*/
+        continue;
+      }
+      
+      /*RGB pixel run?*/
+      p  = pos;
+      fp = pos + 3;
+      current_length = 0;
+      
+      while(fp < size && in[p] == in[fp] && current_length < MAX_SUPPORTED_DEFLATE_LENGTH)
+      {
+        ++p;
+        ++fp;
+        ++current_length;
+      }
+      
+      if (current_length > (minLength - 1 ) * 3) /*worth using?*/
+      {
+        uivector_push_back(out, in[pos    ]);
+        uivector_push_back(out, in[pos + 1]);
+        uivector_push_back(out, in[pos + 2]);
+        addLengthDistance(out, current_length, 3);
+        
+        pos += current_length + 3 - 1; /*-1 for loop's pos++*/
+        continue;
+      }
+    }
+    
+    /*Phase 2: Regular LZ77 encoding*/
+    
+    size_t length = 0, offset = 0; /*the length and offset found for the current position*/   
     size_t max_offset = pos < windowSize ? pos : windowSize; /*how far back to test*/
     size_t current_offset;
   
@@ -1082,9 +1151,12 @@
       pos += (length - 1);
     }
   } /*end of the loop through each character of input*/
+  
+  return 0;
 }
-#endif
 
+#else
+
 static const unsigned HASH_NUM_VALUES = 65536;
 static const unsigned HASH_NUM_CHARACTERS = 6;
 static const unsigned HASH_SHIFT = 2;
@@ -1196,6 +1268,8 @@
   return error;
 }
 
+#endif
+
 /* /////////////////////////////////////////////////////////////////////////// */
 
 static unsigned deflateNoCompression(ucvector* out, const unsigned char* data, size_t datasize)

Index: src/doxygen.cpp
===================================================================
--- src/doxygen.cpp	(revision 803)
+++ src/doxygen.cpp	(working copy)
@@ -7642,7 +7644,7 @@
       // template instances 
       if ( cd->isLinkableInProject() && cd->templateMaster()==0)
       {
-        msg("Generating docs for compound %s...\n",cd->name().data());
+        msg("Generating docs for compound 1 %s...\n",cd->name().data());
 
         cd->writeDocumentation(*g_outputList);
         cd->writeMemberList(*g_outputList);
@@ -8553,7 +8555,7 @@
            && !cd->isHidden() && !cd->isEmbeddedInOuterScope()
          )
       {
-        msg("Generating docs for compound %s...\n",cd->name().data());
+        msg("Generating docs for compound 2 %s...\n",cd->name().data());
 
         cd->writeDocumentation(*g_outputList);
         cd->writeMemberList(*g_outputList);
@@ -10342,6 +10344,7 @@
 
   msg("Building example list...\n");
   buildExampleList(rootNav);
+  clearIsAccessibleFromCache();
   
   msg("Searching for enumerations...\n");
   findEnums(rootNav);
@@ -10367,18 +10370,24 @@
 
   msg("Building member list...\n"); // using class info only !
   buildFunctionList(rootNav);
-
+  clearIsAccessibleFromCache();
+  
   msg("Searching for friends...\n");
   findFriends();
+  clearIsAccessibleFromCache();
   
   msg("Searching for documented defines...\n");
   findDefineDocumentation(rootNav); 
+  clearIsAccessibleFromCache();
   
   findClassEntries(rootNav);         
   msg("Computing class inheritance relations...\n");
   findInheritedTemplateInstances();       
+  clearIsAccessibleFromCache();
   msg("Computing class usage relations...\n");
   findUsedTemplateInstances();       
+  clearIsAccessibleFromCache();
+
   if (Config_getBool("INLINE_SIMPLE_STRUCTS"))
   {
     msg("Searching for tag less structs...\n");
@@ -10394,7 +10403,10 @@
   msg("Computing class relations...\n");
   computeTemplateClassRelations(); 
   flushUnresolvedRelations();
+  clearIsAccessibleFromCache();
   computeClassRelations();        
+  clearIsAccessibleFromCache();
+
   if (Config_getBool("OPTIMIZE_OUTPUT_VHDL"))
   {
     VhdlDocGen::computeVhdlComponentRelations(); 
@@ -10404,6 +10416,7 @@
   msg("Add enum values to enums...\n");
   addEnumValuesToEnums(rootNav);
   findEnumDocumentation(rootNav);
+  clearIsAccessibleFromCache();
 
   msg("Searching for member function documentation...\n");
   findObjCMethodDefinitions(rootNav);
@@ -10445,6 +10458,7 @@
 
   msg("Computing member relations...\n");
   computeMemberRelations();
+  clearIsAccessibleFromCache();
 
   msg("Building full member lists recursively...\n");
   mergeCategories();
Index: src/util.h
===================================================================
--- src/util.h	(revision 803)
+++ src/util.h	(working copy)
@@ -310,6 +310,8 @@
 
 void replaceNamespaceAliases(QCString &scope,int i);
 
+void clearIsAccessibleFromCache(void);
+
 int isAccessibleFrom(Definition *scope,FileDef *fileScope,Definition *item);
 
 int isAccessibleFromWithExpScope(Definition *scope,FileDef *fileScope,Definition *item,