From 56f8c6a1acd043d06f836296b5d90f4516ad3ffd Mon Sep 17 00:00:00 2001 From: =?utf8?q?Vladim=C3=ADr=20Vondru=C5=A1?= Date: Sat, 3 Feb 2018 18:45:08 +0100 Subject: [PATCH] doxygen: gathering search results breadth-first. Instead of depth-first. So the shortest results are first. --- doxygen/search.js | 113 ++++++++++++++++++------------------ doxygen/test/test-search.js | 10 ++-- 2 files changed, 62 insertions(+), 61 deletions(-) diff --git a/doxygen/search.js b/doxygen/search.js index 06062610..d21e6d8d 100644 --- a/doxygen/search.js +++ b/doxygen/search.js @@ -222,77 +222,78 @@ var Search = { return []; } - /* Otherwise recursively gather the results */ + /* Otherwise gather the results */ let results = []; - this.gatherResults(this.searchStack[this.searchStack.length - 1], 0, results); - return results; - }, - - gatherResults: function(offset, suffixLength, results) { - let resultCount = this.trie.getUint8(offset); + let leaves = [[this.searchStack[this.searchStack.length - 1], 0]]; + while(leaves.length) { + /* Pop offset from the queue */ + let current = leaves.shift(); + let offset = current[0]; + let suffixLength = current[1]; + + /* Populate the results with all values associated with this node */ + let resultCount = this.trie.getUint8(offset); + for(let i = 0; i != resultCount; ++i) { + let index = this.trie.getUint16(offset + (i + 1)*2, true); + let flags = this.map.getUint8(index*4 + 3); + let resultOffset = this.map.getUint32(index*4, true) & 0x00ffffff; + + /* The result has a suffix, extract its length */ + let resultSuffixLength = 0; + if(flags & 0x01) { + resultSuffixLength = this.map.getUint8(resultOffset); + ++resultOffset; + } - /* Populate the results with all values associated with this node */ - for(let i = 0; i != resultCount; ++i) { - let index = this.trie.getUint16(offset + (i + 1)*2, true); - let flags = this.map.getUint8(index*4 + 3); - let resultOffset = this.map.getUint32(index*4, true) & 0x00ffffff; + let nextResultOffset = this.map.getUint32((index + 1)*4, true) & 0x00ffffff; - /* The result has a suffix, extract its length */ - let resultSuffixLength = 0; - if(flags & 0x01) { - resultSuffixLength = this.map.getUint8(resultOffset); - ++resultOffset; - } + let name = ''; + let j = resultOffset; + for(; j != nextResultOffset; ++j) { + let c = this.map.getUint8(j); - let nextResultOffset = this.map.getUint32((index + 1)*4, true) & 0x00ffffff; + /* End of null-delimited name */ + if(!c) { + ++j; + break; /* null-delimited */ + } - let name = ''; - let j = resultOffset; - for(; j != nextResultOffset; ++j) { - let c = this.map.getUint8(j); + name += String.fromCharCode(c); /* eheh. IS THIS FAST?! */ + } - /* End of null-delimited name */ - if(!c) { - ++j; - break; /* null-delimited */ + let url = ''; + for(; j != nextResultOffset; ++j) { + url += String.fromCharCode(this.map.getUint8(j)); } - name += String.fromCharCode(c); /* eheh. IS THIS FAST?! */ - } + /* Keeping in UTF-8, as we need that for proper slicing */ + results.push({name: name, + url: url, + flags: flags, + suffixLength: suffixLength + resultSuffixLength}); - let url = ''; - for(; j != nextResultOffset; ++j) { - url += String.fromCharCode(this.map.getUint8(j)); + /* 'nuff said. */ + /* TODO: remove once proper barriers are in */ + if(results.length >= this.maxResults) return results; } - /* Keeping in UTF-8, as we need that for proper slicing */ - results.push({name: name, - url: url, - flags: flags, - suffixLength: suffixLength + resultSuffixLength}); - - /* 'nuff said. */ - /* TODO: remove once proper barriers are in */ - if(results.length >= this.maxResults) return true; - } - - /* Dig deeper. If the child already has enough, return. */ - /* TODO: hmmm. this is helluvalot duplicated code. hmm. */ - let relChildOffset = 2 + this.trie.getUint8(offset)*2; - let childCount = this.trie.getUint8(offset + 1); - let childOffset = offset + relChildOffset; - for(let j = 0; j != childCount; ++j) { - let offsetBarrier = this.trie.getUint32(childOffset + j*4, true); + /* Dig deeper */ + /* TODO: hmmm. this is helluvalot duplicated code. hmm. */ + let relChildOffset = 2 + this.trie.getUint8(offset)*2; + let childCount = this.trie.getUint8(offset + 1); + let childOffset = offset + relChildOffset; + for(let j = 0; j != childCount; ++j) { + let offsetBarrier = this.trie.getUint32(childOffset + j*4, true); - /* Lookahead barrier, don't dig deeper */ - if(offsetBarrier & 0x00800000) continue; + /* Lookahead barrier, don't dig deeper */ + if(offsetBarrier & 0x00800000) continue; - if(this.gatherResults(offsetBarrier & 0x007fffff, suffixLength + 1, results)) - return true; + /* Append to the queue */ + leaves.push([offsetBarrier & 0x007fffff, suffixLength + 1]); + } } - /* Still hungry. */ - return false; + return results; }, escapeForRtl: function(name) { diff --git a/doxygen/test/test-search.js b/doxygen/test/test-search.js index 7c94f2df..129093aa 100644 --- a/doxygen/test/test-search.js +++ b/doxygen/test/test-search.js @@ -220,14 +220,14 @@ const { StringDecoder } = require('string_decoder'); assert.equal(Search.dataSize, 0.1); assert.equal(Search.symbolCount, 2); assert.deepEqual(Search.search('h'), [ - { name: Search.toUtf8('Hýždě'), - url: '#a', - flags: 0, - suffixLength: 7 }, { name: Search.toUtf8('Hárá'), url: '#b', flags: 0, - suffixLength: 5 }]); + suffixLength: 5 }, + { name: Search.toUtf8('Hýždě'), + url: '#a', + flags: 0, + suffixLength: 7 }]); assert.deepEqual(Search.search('hý'), [ { name: Search.toUtf8('Hýždě'), url: '#a', -- 2.30.2