refactoring: modernize search index

Also QVector has been removed from qtools as it was no longer used.

2 files changed, 116 insertions, 157 deletions

diff --git a/src/searchindex.cpp b/src/searchindex.cpp
index d9e5c99..067370b 100644
--- a/src/searchindex.cpp
+++ b/src/searchindex.cpp
@@ -37,6 +37,8 @@
 #include "filename.h"
 #include "membername.h"
 #include "resourcemgr.h"
+#include "namespacedef.h"
+#include "classdef.h"
 
 // file format: (all multi-byte values are stored in big endian format)
 //   4 byte header
@@ -49,41 +51,33 @@
 //                 (4 bytes index to url string + 4 bytes frequency counter)
 //   for each url: a \0 terminated string
 
-const int numIndexEntries = 256*256;
+const size_t numIndexEntries = 256*256;
 
 //--------------------------------------------------------------------
 
-IndexWord::IndexWord(const char *word) : m_word(word), m_urls(17)
+IndexWord::IndexWord(QCString word) : m_word(word)
 {
-  m_urls.setAutoDelete(TRUE);
   //printf("IndexWord::IndexWord(%s)\n",word);
 }
 
 void IndexWord::addUrlIndex(int idx,bool hiPriority)
 {
   //printf("IndexWord::addUrlIndex(%d,%d)\n",idx,hiPriority);
-  URLInfo *ui = m_urls.find(idx);
-  if (ui==0)
+  auto it = m_urls.find(idx);
+  if (it==m_urls.end())
   {
     //printf("URLInfo::URLInfo(%d)\n",idx);
-    ui=new URLInfo(idx,0);
-    m_urls.insert(idx,ui);
+    it = m_urls.insert(std::make_pair(idx,URLInfo(idx,0))).first;
   }
-  ui->freq+=2;
-  if (hiPriority) ui->freq|=1; // mark as high priority document
+  it->second.freq+=2;
+  if (hiPriority) it->second.freq|=1; // mark as high priority document
 }
 
 //--------------------------------------------------------------------
 
-SearchIndex::SearchIndex() : SearchIndexIntf(Internal),
-      m_words(328829), m_index(numIndexEntries), m_url2IdMap(10007), m_urls(10007), m_urlIndex(-1)
+SearchIndex::SearchIndex() : SearchIndexIntf(Internal)
 {
-  int i;
-  m_words.setAutoDelete(TRUE);
-  m_url2IdMap.setAutoDelete(TRUE);
-  m_urls.setAutoDelete(TRUE);
-  m_index.setAutoDelete(TRUE);
-  for (i=0;i<numIndexEntries;i++) m_index.insert(i,new QList<IndexWord>);
+  m_index.resize(numIndexEntries);
 }
 
 void SearchIndex::setCurrentDoc(const Definition *ctx,const char *anchor,bool isSourceFile)
@@ -167,16 +161,16 @@ void SearchIndex::setCurrentDoc(const Definition *ctx,const char *anchor,bool is
     }
   }
 
-  int *pIndex = m_url2IdMap.find(baseUrl);
-  if (pIndex==0)
+  auto it = m_url2IdMap.find(baseUrl.str());
+  if (it == m_url2IdMap.end())
   {
     ++m_urlIndex;
-    m_url2IdMap.insert(baseUrl,new int(m_urlIndex));
-    m_urls.insert(m_urlIndex,new URL(name,url));
+    m_url2IdMap.insert(std::make_pair(baseUrl.str(),m_urlIndex));
+    m_urls.insert(std::make_pair(m_urlIndex,URL(name,url)));
   }
   else
   {
-    m_urls.insert(*pIndex,new URL(name,url));
+    m_urls.insert(std::make_pair(it->second,URL(name,url)));
   }
 }
 
@@ -208,17 +202,16 @@ void SearchIndex::addWord(const char *word,bool hiPriority,bool recurse)
   if (word==0 || word[0]=='\0') return;
   QCString wStr = QCString(word).lower();
   //printf("SearchIndex::addWord(%s,%d) wStr=%s\n",word,hiPriority,wStr.data());
-  IndexWord *w = m_words[wStr];
-  if (w==0)
+  int idx=charsToIndex(wStr);
+  if (idx<0 || idx>=static_cast<int>(m_index.size())) return;
+  auto it = m_words.find(wStr.str());
+  if (it==m_words.end())
   {
-    int idx=charsToIndex(wStr);
     //fprintf(stderr,"addWord(%s) at index %d\n",word,idx);
-    if (idx<0) return;
-    w = new IndexWord(wStr);
-    m_index[idx]->append(w);
-    m_words.insert(wStr,w);
+    m_index[idx].push_back(IndexWord(wStr));
+    it = m_words.insert({ wStr.str(), m_index[idx].size()-1 }).first;
   }
-  w->addUrlIndex(m_urlIndex,hiPriority);
+  m_index[idx][it->second].addUrlIndex(m_urlIndex,hiPriority);
   int i;
   bool found=FALSE;
   if (!recurse) // the first time we check if we can strip the prefix
@@ -244,12 +237,12 @@ void SearchIndex::addWord(const char *word,bool hiPriority)
   addWord(word,hiPriority,FALSE);
 }
 
-static void writeInt(QFile &f,int index)
+static void writeInt(QFile &f,size_t index)
 {
-  f.putch(((uint)index)>>24);
-  f.putch((((uint)index)>>16)&0xff);
-  f.putch((((uint)index)>>8)&0xff);
-  f.putch(((uint)index)&0xff);
+  f.putch(index>>24);
+  f.putch((index>>16)&0xff);
+  f.putch((index>>8)&0xff);
+  f.putch(index&0xff);
 }
 
 static void writeString(QFile &f,const char *s)
@@ -261,21 +254,19 @@ static void writeString(QFile &f,const char *s)
 
 void SearchIndex::write(const char *fileName)
 {
-  int i;
-  int size=4; // for the header
+  size_t i;
+  size_t size=4; // for the header
   size+=4*numIndexEntries; // for the index
-  int wordsOffset = size;
+  size_t wordsOffset = size;
   // first pass: compute the size of the wordlist
   for (i=0;i<numIndexEntries;i++)
   {
-    QList<IndexWord> *wlist = m_index[i];
-    if (!wlist->isEmpty())
+    const auto &wlist = m_index[i];
+    if (!wlist.empty())
     {
-      QListIterator<IndexWord> iwi(*wlist);
-      IndexWord *iw;
-      for (iwi.toFirst();(iw=iwi.current());++iwi)
+      for (const auto &iw : wlist)
       {
-        int ws = iw->word().length()+1;
+        int ws = iw.word().length()+1;
         size+=ws+4; // word + url info list offset
       }
       size+=1; // zero list terminator
@@ -283,19 +274,17 @@ void SearchIndex::write(const char *fileName)
   }
 
   // second pass: compute the offsets in the index
-  int indexOffsets[numIndexEntries];
-  int offset=wordsOffset;
+  size_t indexOffsets[numIndexEntries];
+  size_t offset=wordsOffset;
   for (i=0;i<numIndexEntries;i++)
   {
-    QList<IndexWord> *wlist = m_index[i];
-    if (!wlist->isEmpty())
+    const auto &wlist = m_index[i];
+    if (!wlist.empty())
     {
       indexOffsets[i]=offset;
-      QListIterator<IndexWord> iwi(*wlist);
-      IndexWord *iw;
-      for (iwi.toFirst();(iw=iwi.current());++iwi)
+      for (const auto &iw : wlist)
       {
-        offset+= iw->word().length()+1;
+        offset+= iw.word().length()+1;
         offset+=4; // word + offset to url info array
       }
       offset+=1; // zero list terminator
@@ -305,42 +294,36 @@ void SearchIndex::write(const char *fileName)
       indexOffsets[i]=0;
     }
   }
-  int padding = size;
+  size_t padding = size;
   size = (size+3)&~3; // round up to 4 byte boundary
   padding = size - padding;
 
-  //int statsOffset = size;
-  //IndexWord *iw;
-  int *wordStatOffsets = new int[m_words.count()];
+  std::vector<size_t> wordStatOffsets(m_words.size());
 
   int count=0;
 
   // third pass: compute offset to stats info for each word
   for (i=0;i<numIndexEntries;i++)
   {
-    QList<IndexWord> *wlist = m_index[i];
-    if (!wlist->isEmpty())
+    const auto &wlist = m_index[i];
+    if (!wlist.empty())
     {
-      QListIterator<IndexWord> iwi(*wlist);
-      IndexWord *iw;
-      for (iwi.toFirst();(iw=iwi.current());++iwi)
+      for (const auto &iw : wlist)
       {
         //printf("wordStatOffsets[%d]=%d\n",count,size);
         wordStatOffsets[count++] = size;
-        size+=4+iw->urls().count()*8; // count + (url_index,freq) per url
+        size+=4 + iw.urls().size() * 8; // count + (url_index,freq) per url
       }
     }
   }
-  int *urlOffsets = new int[m_urls.count()];
-  //int urlsOffset = size;
-  QIntDictIterator<URL> udi(m_urls);
-  URL *url;
-  for (udi.toFirst();(url=udi.current());++udi)
+  std::vector<size_t> urlOffsets(m_urls.size());
+  for (const auto &udi : m_urls)
   {
-    urlOffsets[udi.currentKey()]=size;
-    size+=url->name.length()+1+
-          url->url.length()+1;
+    urlOffsets[udi.first]=size;
+    size+=udi.second.name.length()+1+
+          udi.second.url.length()+1;
   }
+
   //printf("Total size %x bytes (word=%x stats=%x urls=%x)\n",size,wordsOffset,statsOffset,urlsOffset);
   QFile f(fileName);
   if (f.open(IO_WriteOnly))
@@ -356,14 +339,12 @@ void SearchIndex::write(const char *fileName)
     count=0;
     for (i=0;i<numIndexEntries;i++)
     {
-      QList<IndexWord> *wlist = m_index[i];
-      if (!wlist->isEmpty())
+      const auto &wlist = m_index[i];
+      if (!wlist.empty())
       {
-        QListIterator<IndexWord> iwi(*wlist);
-        IndexWord *iw;
-        for (iwi.toFirst();(iw=iwi.current());++iwi)
+        for (const auto &iw : wlist)
         {
-          writeString(f,iw->word());
+          writeString(f,iw.word());
           writeInt(f,wordStatOffsets[count++]);
         }
         f.putch(0);
@@ -374,35 +355,29 @@ void SearchIndex::write(const char *fileName)
     // write word statistics
     for (i=0;i<numIndexEntries;i++)
     {
-      QList<IndexWord> *wlist = m_index[i];
-      if (!wlist->isEmpty())
+      const auto &wlist = m_index[i];
+      if (!wlist.empty())
       {
-        QListIterator<IndexWord> iwi(*wlist);
-        IndexWord *iw;
-        for (iwi.toFirst();(iw=iwi.current());++iwi)
+        for (const auto &iw : wlist)
         {
-          int numUrls = iw->urls().count();
+          size_t numUrls = iw.urls().size();
           writeInt(f,numUrls);
-          QIntDictIterator<URLInfo> uli(iw->urls());
-          URLInfo *ui;
-          for (uli.toFirst();(ui=uli.current());++uli)
+          for (const auto &ui : iw.urls())
           {
-            writeInt(f,urlOffsets[ui->urlIdx]);
-            writeInt(f,ui->freq);
+            writeInt(f,urlOffsets[ui.second.urlIdx]);
+            writeInt(f,ui.second.freq);
           }
         }
       }
     }
     // write urls
-    for (udi.toFirst();(url=udi.current());++udi)
+    for (const auto &udi : m_urls)
     {
-      writeString(f,url->name);
-      writeString(f,url->url);
+      writeString(f,udi.second.name);
+      writeString(f,udi.second.url);
     }
   }
 
-  delete[] urlOffsets;
-  delete[] wordStatOffsets;
 }
 
 
@@ -422,22 +397,12 @@ struct SearchDocEntry
 
 struct SearchIndexExternal::Private
 {
-  Private() : docEntries(12251) {}
-  SDict<SearchDocEntry> docEntries;
+  std::map<std::string,SearchDocEntry> docEntries;
   SearchDocEntry *current = 0;
 };
 
-SearchIndexExternal::SearchIndexExternal() : SearchIndexIntf(External)
-{
-  p = new SearchIndexExternal::Private;
-  p->docEntries.setAutoDelete(TRUE);
-  p->current=0;
-}
-
-SearchIndexExternal::~SearchIndexExternal()
+SearchIndexExternal::SearchIndexExternal() : SearchIndexIntf(External), p(std::make_unique<Private>())
 {
-  //printf("p->docEntries.count()=%d\n",p->docEntries.count());
-  delete p;
 }
 
 static QCString definitionToName(const Definition *ctx)
@@ -497,29 +462,28 @@ static QCString definitionToName(const Definition *ctx)
 
 void SearchIndexExternal::setCurrentDoc(const Definition *ctx,const char *anchor,bool isSourceFile)
 {
-  QCString extId = stripPath(Config_getString(EXTERNAL_SEARCH_ID));
+  static QCString extId = stripPath(Config_getString(EXTERNAL_SEARCH_ID));
   QCString baseName = isSourceFile ? (dynamic_cast<const FileDef*>(ctx))->getSourceFileBase() : ctx->getOutputFileBase();
   QCString url = baseName + Doxygen::htmlFileExtension;
   if (anchor) url+=QCString("#")+anchor;
   QCString key = extId+";"+url;
 
-  p->current = p->docEntries.find(key);
-  //printf("setCurrentDoc(url=%s,isSourceFile=%d) current=%p\n",url.data(),isSourceFile,p->current);
-  if (!p->current)
+  auto it = p->docEntries.find(key.str());
+  if (it == p->docEntries.end())
   {
-    SearchDocEntry *e = new SearchDocEntry;
-    e->type = isSourceFile ? QCString("source") : definitionToName(ctx);
-    e->name = ctx->qualifiedName();
+    SearchDocEntry e;
+    e.type = isSourceFile ? QCString("source") : definitionToName(ctx);
+    e.name = ctx->qualifiedName();
     if (ctx->definitionType()==Definition::TypeMember)
     {
-      e->args = (dynamic_cast<const MemberDef*>(ctx))->argsString();
+      e.args = (dynamic_cast<const MemberDef*>(ctx))->argsString();
     }
-    e->extId = extId;
-    e->url  = url;
-    p->current = e;
-    p->docEntries.append(key,e);
+    e.extId = extId;
+    e.url  = url;
+    it = p->docEntries.insert({key.str(),e}).first;
     //printf("searchIndexExt %s : %s\n",e->name.data(),e->url.data());
   }
+  p->current = &it->second;
 }
 
 void SearchIndexExternal::addWord(const char *word,bool hiPriority)
@@ -539,26 +503,25 @@ void SearchIndexExternal::write(const char *fileName)
     FTextStream t(&f);
     t << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>" << endl;
     t << "<add>" << endl;
-    SDict<SearchDocEntry>::Iterator it(p->docEntries);
-    SearchDocEntry *doc;
-    for (it.toFirst();(doc=it.current());++it)
+    for (auto &kv : p->docEntries)
     {
-      doc->normalText.addChar(0);    // make sure buffer ends with a 0 terminator
-      doc->importantText.addChar(0); // make sure buffer ends with a 0 terminator
+      SearchDocEntry &doc = kv.second;
+      doc.normalText.addChar(0);    // make sure buffer ends with a 0 terminator
+      doc.importantText.addChar(0); // make sure buffer ends with a 0 terminator
       t << "  <doc>" << endl;
-      t << "    <field name=\"type\">"     << doc->type << "</field>" << endl;
-      t << "    <field name=\"name\">"     << convertToXML(doc->name) << "</field>" << endl;
-      if (!doc->args.isEmpty())
+      t << "    <field name=\"type\">"     << doc.type << "</field>" << endl;
+      t << "    <field name=\"name\">"     << convertToXML(doc.name) << "</field>" << endl;
+      if (!doc.args.isEmpty())
       {
-        t << "    <field name=\"args\">"     << convertToXML(doc->args) << "</field>" << endl;
+        t << "    <field name=\"args\">"     << convertToXML(doc.args) << "</field>" << endl;
       }
-      if (!doc->extId.isEmpty())
+      if (!doc.extId.isEmpty())
       {
-        t << "    <field name=\"tag\">"      << convertToXML(doc->extId)  << "</field>" << endl;
+        t << "    <field name=\"tag\">"      << convertToXML(doc.extId)  << "</field>" << endl;
       }
-      t << "    <field name=\"url\">"      << convertToXML(doc->url)  << "</field>" << endl;
-      t << "    <field name=\"keywords\">" << convertToXML(doc->importantText.get())  << "</field>" << endl;
-      t << "    <field name=\"text\">"     << convertToXML(doc->normalText.get())     << "</field>" << endl;
+      t << "    <field name=\"url\">"      << convertToXML(doc.url)  << "</field>" << endl;
+      t << "    <field name=\"keywords\">" << convertToXML(doc.importantText.get())  << "</field>" << endl;
+      t << "    <field name=\"text\">"     << convertToXML(doc.normalText.get())     << "</field>" << endl;
       t << "  </doc>" << endl;
     }
     t << "</add>" << endl;
@@ -572,14 +535,6 @@ void SearchIndexExternal::write(const char *fileName)
 //---------------------------------------------------------------------------
 // the following part is for the javascript based search engine
 
-#include "memberdef.h"
-#include "namespacedef.h"
-#include "pagedef.h"
-#include "classdef.h"
-#include "filedef.h"
-#include "language.h"
-#include "doxygen.h"
-#include "message.h"
 
 static SearchIndexInfo g_searchIndexInfo[NUM_SEARCH_INDICES];
 
diff --git a/src/searchindex.h b/src/searchindex.h
index 923973c..71c1ce1 100644
--- a/src/searchindex.h
+++ b/src/searchindex.h
@@ -1,12 +1,12 @@
 /******************************************************************************
  *
- * 
+ *
  *
  * Copyright (C) 1997-2015 by Dimitri van Heesch.
  *
  * Permission to use, copy, modify, and distribute this software and its
- * documentation under the terms of the GNU General Public License is hereby 
- * granted. No representations are made about the suitability of this software 
+ * documentation under the terms of the GNU General Public License is hereby
+ * granted. No representations are made about the suitability of this software
  * for any purpose. It is provided "as is" without express or implied warranty.
  * See the GNU General Public License for more details.
  *
@@ -18,11 +18,15 @@
 #ifndef _SEARCHINDEX_H
 #define _SEARCHINDEX_H
 
+#include <memory>
+#include <vector>
+#include <map>
+#include <unordered_map>
+#include <string>
+
 #include <qintdict.h>
 #include <qlist.h>
-#include <qdict.h>
 #include <qintdict.h>
-#include <qvector.h>
 #include "sortdict.h"
 #include "definition.h"
 #include "util.h"
@@ -40,7 +44,7 @@ void finalizeSearchIndexer();
 
 struct URL
 {
-  URL(const char *n,const char *u) : name(n), url(u) {} 
+  URL(QCString n,QCString u) : name(n), url(u) {}
   QCString name;
   QCString url;
 };
@@ -56,14 +60,15 @@ struct URLInfo
 class IndexWord
 {
   public:
-    IndexWord(const char *word);
+    using URLInfoMap = std::unordered_map<int,URLInfo>;
+    IndexWord(QCString word);
     void addUrlIndex(int,bool);
-    const QIntDict<URLInfo> &urls() const { return m_urls; }
+    URLInfoMap urls() const { return m_urls; }
     QCString word() const { return m_word; }
 
   private:
     QCString    m_word;
-    QIntDict<URLInfo> m_urls;
+    URLInfoMap  m_urls;
 };
 
 class SearchIndexIntf
@@ -84,16 +89,16 @@ class SearchIndex : public SearchIndexIntf
 {
   public:
     SearchIndex();
-    void setCurrentDoc(const Definition *ctx,const char *anchor,bool isSourceFile);
-    void addWord(const char *word,bool hiPriority);
-    void write(const char *file);
+    void setCurrentDoc(const Definition *ctx,const char *anchor,bool isSourceFile) override;
+    void addWord(const char *word,bool hiPriority) override;
+    void write(const char *file) override;
   private:
     void addWord(const char *word,bool hiPrio,bool recurse);
-    QDict<IndexWord> m_words;
-    QVector< QList<IndexWord> > m_index;
-    QDict<int> m_url2IdMap;
-    QIntDict<URL> m_urls;
-    int m_urlIndex;
+    std::unordered_map<std::string,int> m_words;
+    std::vector< std::vector< IndexWord> > m_index;
+    std::unordered_map<std::string,int> m_url2IdMap;
+    std::map<int,URL> m_urls;
+    int m_urlIndex = -1;
 };
 
 
@@ -102,12 +107,11 @@ class SearchIndexExternal : public SearchIndexIntf
     struct Private;
   public:
     SearchIndexExternal();
-   ~SearchIndexExternal();
     void setCurrentDoc(const Definition *ctx,const char *anchor,bool isSourceFile);
     void addWord(const char *word,bool hiPriority);
     void write(const char *file);
   private:
-    Private *p;
+    std::unique_ptr<Private> p;
 };
 
 //------- client side search index ----------------------