Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/util/doxygen/src/searchindex.cpp

Source at commit 1322 created 9 years 5 months ago.
By meklort, Add doxygen to utils folder
1/******************************************************************************
2 *
3 * $Id: searchindex.cpp,v 1.7 2001/03/19 19:27:41 root Exp $
4 *
5 * Copyright (C) 1997-2011 by Dimitri van Heesch.
6 *
7 * Permission to use, copy, modify, and distribute this software and its
8 * documentation under the terms of the GNU General Public License is hereby
9 * granted. No representations are made about the suitability of this software
10 * for any purpose. It is provided "as is" without express or implied warranty.
11 * See the GNU General Public License for more details.
12 *
13 * Documents produced by Doxygen are derivative works derived from the
14 * input used in their production; they are not affected by this license.
15 *
16 */
17
18#include "qtbc.h"
19#include "searchindex.h"
20#include "config.h"
21#include "util.h"
22#include <qfile.h>
23#include <ctype.h>
24#include <qregexp.h>
25
26
27// file format: (all multi-byte values are stored in big endian format)
28// 4 byte header
29// 256*256*4 byte index (4 bytes)
30// for each index entry: a zero terminated list of words
31// for each word: a \0 terminated string + 4 byte offset to the stats info
32// padding bytes to align at 4 byte boundary
33// for each word: the number of urls (4 bytes)
34// + for each url containing the word 8 bytes statistics
35// (4 bytes index to url string + 4 bytes frequency counter)
36// for each url: a \0 terminated string
37
38const int numIndexEntries = 256*256;
39
40//--------------------------------------------------------------------
41
42IndexWord::IndexWord(const char *word) : m_word(word), m_urls(17)
43{
44 m_urls.setAutoDelete(TRUE);
45 //printf("IndexWord::IndexWord(%s)\n",word);
46}
47
48void IndexWord::addUrlIndex(int idx,bool hiPriority)
49{
50 //printf("IndexWord::addUrlIndex(%d,%d)\n",idx,hiPriority);
51 URLInfo *ui = m_urls.find(idx);
52 if (ui==0)
53 {
54 //printf("URLInfo::URLInfo(%d)\n",idx);
55 ui=new URLInfo(idx,0);
56 m_urls.insert(idx,ui);
57 }
58 ui->freq+=2;
59 if (hiPriority) ui->freq|=1; // mark as high priority document
60}
61
62//--------------------------------------------------------------------
63
64SearchIndex::SearchIndex() : m_words(328829), m_index(numIndexEntries), m_urlIndex(-1)
65{
66 int i;
67 m_words.setAutoDelete(TRUE);
68 m_urls.setAutoDelete(TRUE);
69 m_index.setAutoDelete(TRUE);
70 for (i=0;i<numIndexEntries;i++) m_index.insert(i,new QList<IndexWord>);
71}
72
73void SearchIndex::setCurrentDoc(const char *name,const char *baseName,const char *anchor)
74{
75 if (name==0 || baseName==0) return;
76 //printf("SearchIndex::setCurrentDoc(%s,%s,%s)\n",name,baseName,anchor);
77 QCString url=baseName+Config_getString("HTML_FILE_EXTENSION");
78 if (anchor) url+=(QCString)"#"+anchor;
79 m_urlIndex++;
80 m_urls.insert(m_urlIndex,new URL(name,url));
81}
82
83static int charsToIndex(const char *word)
84{
85 if (word==0) return -1;
86
87 // Fast string hashing algorithm
88 //register ushort h=0;
89 //const char *k = word;
90 //ushort mask=0xfc00;
91 //while ( *k )
92 //{
93 // h = (h&mask)^(h<<6)^(*k++);
94 //}
95 //return h;
96
97 // Simple hashing that allows for substring searching
98 uint c1=word[0];
99 if (c1==0) return -1;
100 uint c2=word[1];
101 if (c2==0) return -1;
102 return c1*256+c2;
103}
104
105void SearchIndex::addWord(const char *word,bool hiPriority,bool recurse)
106{
107 static QRegExp nextPart("[_a-z:][A-Z]");
108 //printf("SearchIndex::addWord(%s,%d)\n",word,hiPriority);
109 QString wStr(word);
110 if (wStr.isEmpty()) return;
111 wStr=wStr.lower();
112 IndexWord *w = m_words[wStr];
113 if (w==0)
114 {
115 int idx=charsToIndex(wStr);
116 if (idx<0) return;
117 w = new IndexWord(wStr);
118 //fprintf(stderr,"addWord(%s) at index %d\n",word,idx);
119 m_index[idx]->append(w);
120 m_words.insert(wStr,w);
121 }
122 w->addUrlIndex(m_urlIndex,hiPriority);
123 int i;
124 bool found=FALSE;
125 if (!recurse) // the first time we check if we can strip the prefix
126 {
127 i=getPrefixIndex(word);
128 if (i>0)
129 {
130 addWord(word+i,hiPriority,TRUE);
131 found=TRUE;
132 }
133 }
134 if (!found) // no prefix stripped
135 {
136 if ((i=nextPart.match(word))>=1)
137 {
138 addWord(word+i+1,hiPriority,TRUE);
139 }
140 }
141}
142
143
144static void writeInt(QFile &f,int index)
145{
146 f.putch(((uint)index)>>24);
147 f.putch((((uint)index)>>16)&0xff);
148 f.putch((((uint)index)>>8)&0xff);
149 f.putch(((uint)index)&0xff);
150}
151
152static void writeString(QFile &f,const char *s)
153{
154 const char *p = s;
155 while (*p) f.putch(*p++);
156 f.putch(0);
157}
158
159void SearchIndex::write(const char *fileName)
160{
161 int i;
162 int size=4; // for the header
163 size+=4*numIndexEntries; // for the index
164 int wordsOffset = size;
165 // first pass: compute the size of the wordlist
166 for (i=0;i<numIndexEntries;i++)
167 {
168 QList<IndexWord> *wlist = m_index[i];
169 if (!wlist->isEmpty())
170 {
171 QListIterator<IndexWord> iwi(*wlist);
172 IndexWord *iw;
173 for (iwi.toFirst();(iw=iwi.current());++iwi)
174 {
175 int ws = iw->word().length()+1;
176 size+=ws+4; // word + url info list offset
177 }
178 size+=1; // zero list terminator
179 }
180 }
181
182 // second pass: compute the offsets in the index
183 int indexOffsets[numIndexEntries];
184 int offset=wordsOffset;
185 for (i=0;i<numIndexEntries;i++)
186 {
187 QList<IndexWord> *wlist = m_index[i];
188 if (!wlist->isEmpty())
189 {
190 indexOffsets[i]=offset;
191 QListIterator<IndexWord> iwi(*wlist);
192 IndexWord *iw;
193 for (iwi.toFirst();(iw=iwi.current());++iwi)
194 {
195 offset+= iw->word().length()+1;
196 offset+=4; // word + offset to url info array
197 }
198 offset+=1; // zero list terminator
199 }
200 else
201 {
202 indexOffsets[i]=0;
203 }
204 }
205 int padding = size;
206 size = (size+3)&~3; // round up to 4 byte boundary
207 padding = size - padding;
208
209 //int statsOffset = size;
210 QDictIterator<IndexWord> wdi(m_words);
211 //IndexWord *iw;
212 int *wordStatOffsets = new int[m_words.count()];
213
214 int count=0;
215
216 // third pass: compute offset to stats info for each word
217 for (i=0;i<numIndexEntries;i++)
218 {
219 QList<IndexWord> *wlist = m_index[i];
220 if (!wlist->isEmpty())
221 {
222 QListIterator<IndexWord> iwi(*wlist);
223 IndexWord *iw;
224 for (iwi.toFirst();(iw=iwi.current());++iwi)
225 {
226 //printf("wordStatOffsets[%d]=%d\n",count,size);
227 wordStatOffsets[count++] = size;
228 size+=4+iw->urls().count()*8; // count + (url_index,freq) per url
229 }
230 }
231 }
232 int *urlOffsets = new int[m_urls.count()];
233 //int urlsOffset = size;
234 QIntDictIterator<URL> udi(m_urls);
235 URL *url;
236 for (udi.toFirst();(url=udi.current());++udi)
237 {
238 urlOffsets[udi.currentKey()]=size;
239 size+=url->name.length()+1+
240 url->url.length()+1;
241 }
242 //printf("Total size %x bytes (word=%x stats=%x urls=%x)\n",size,wordsOffset,statsOffset,urlsOffset);
243 QFile f(fileName);
244 if (f.open(IO_WriteOnly))
245 {
246 // write header
247 f.putch('D'); f.putch('O'); f.putch('X'); f.putch('S');
248 // write index
249 for (i=0;i<numIndexEntries;i++)
250 {
251 writeInt(f,indexOffsets[i]);
252 }
253 // write word lists
254 count=0;
255 for (i=0;i<numIndexEntries;i++)
256 {
257 QList<IndexWord> *wlist = m_index[i];
258 if (!wlist->isEmpty())
259 {
260 QListIterator<IndexWord> iwi(*wlist);
261 IndexWord *iw;
262 for (iwi.toFirst();(iw=iwi.current());++iwi)
263 {
264 writeString(f,iw->word());
265 writeInt(f,wordStatOffsets[count++]);
266 }
267 f.putch(0);
268 }
269 }
270 // write extra padding bytes
271 for (i=0;i<padding;i++) f.putch(0);
272 // write word statistics
273 for (i=0;i<numIndexEntries;i++)
274 {
275 QList<IndexWord> *wlist = m_index[i];
276 if (!wlist->isEmpty())
277 {
278 QListIterator<IndexWord> iwi(*wlist);
279 IndexWord *iw;
280 for (iwi.toFirst();(iw=iwi.current());++iwi)
281 {
282 int numUrls = iw->urls().count();
283 writeInt(f,numUrls);
284 QIntDictIterator<URLInfo> uli(iw->urls());
285 URLInfo *ui;
286 for (uli.toFirst();(ui=uli.current());++uli)
287 {
288 writeInt(f,urlOffsets[ui->urlIdx]);
289 writeInt(f,ui->freq);
290 }
291 }
292 }
293 }
294 // write urls
295 QIntDictIterator<URL> udi(m_urls);
296 URL *url;
297 for (udi.toFirst();(url=udi.current());++udi)
298 {
299 writeString(f,url->name);
300 writeString(f,url->url);
301 }
302 }
303
304 delete[] urlOffsets;
305 delete[] wordStatOffsets;
306}
307
308

Archive Download this file

Revision: 1322