2 * Copyright (c) 2004 Teodor Sigaev <teodor@sigaev.ru>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the author nor the names of any co-contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS
18 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY
21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
23 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
25 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
26 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
27 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 #include <sys/types.h>
36 * ëÁÖÄÙÊ ÕÚÅÌ ÄÅÒÅ×Á ÍÏÖÅÔ ÂÙÔÔØ ÏÂÎÉÍ ÉÚ Ä×ÕÈ ÔÉÐÏ×:
37 * SFSNode->isskip = 1 - ÕÚÅÌ "ÐÕÔÅ×ÏÊ ËÏÍÐÒÅÓÉÉ".
38 * ôÁËÏÊ ÕÚÅÌ ÍÏÖÅÔ ÉÍÅÔØ ÏÄÎÏÇÏ ÒÅÂÅÎËÁ É/ÉÌÉ
40 * SFSNode->isskip = 0 - "×ÅÔ×ÑÝÉÊÓÑ ÕÚÅÌ"
42 * "×ÅÔ×ÑÝÉÊÓÑ" ÕÚÅÌ ÄÅÒÅ×Á ÈÒÁÎÉÔØÓÑ × ÐÁÍÑÔÉ ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏÍ:
43 * ( SFSNHRDSZ ÂÁÊÔÁ ) SFSNode - ÚÁÇÏÌÏ×ÏË ÕÚÌÁ
44 * ( sizeof(SFSNodeData)*SFSNode->nchar ÂÁÊÔÁ) SFSNodeData[] - ÍÁÓÓÉ× "ÓÉÍ×ÏÌÏ×"
45 * ( sizeof(SFSNode*)*SFSNode->nchild ÂÁÊÔÁ ) *SFSNode[] - ÍÁÓÓÉ× ÓÓÙÌÏË ÎÁ ÄÏÞÅÒÎÉÅ ÕÚÌÙ
46 * ( SFSTree->datasize * (ËÏÌÉÞÅÓÔ×Ï ÓÌÏ×, ÚÁËÁÎÞÉ×ÁÀÝÉÈÓÑ × ÜÔÏÍ ÕÚÌÅ) ) -
49 * ÍÁÓÓÉ× "ÓÉÍ×ÏÌÏ×" - ÕÐÏÒÑÄÏÞÅÎ ÐÏ ÓÉÍ×ÏÌÁÍ (SFSNodeData->val),
50 * ÐÏÒÑÄÏË ÏÓÔÁÌØÎÙÈ ÍÁÓÓÉ×Ï× ÚÁÄÁÅÔÓÑ ÍÁÓÓÉ×ÏÍ "ÓÉÍ×ÏÌÏ×"
51 * ÕÚÅÌ "ÐÕÔÅ×ÏÊ ËÏÍÐÒÅÓÉÉ" ÈÒÁÎÉÔØÓÑ × ÐÁÍÑÔÉ ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏÍ:
52 * ( SFSNHRDSZ ÂÁÊÔÁ ) SFSNode - ÚÁÇÏÌÏ×ÏË ÕÚÌÁ
53 * sizeof(SFSNode*) ÂÁÊÔ - ÓÓÙÌËÁ ÎÁ ÒÅÂÅÎËÁ (ÎÅÏÂÑÚÁÔÅÌØÎÏÅ ÐÏÌÅ)
54 * SFSTree->datasize ÂÁÊÔ - ÚÎÁÞÅÎÉÅ, ÅÓÌÉ ÚÄÅÓØ ÚÁËÁÎÞÉ×ÁÅÔÓÑ ËÌÀÞ
55 * (ÎÅÏÂÑÚÁÔÅÌØÎÏÅ ÐÏÌÅ)
56 * SFSTree->nchar ÂÁÊÔ - "ÓËÏÍÐÒÅÓÓÉÒÏ×ÁÎÎÁÑ" ÞÁÓÔØ ÐÕÔÉ.
59 /* ÓÔÒÕËÔÕÒÁ, ÏÐÉÓÙ×ÁÀÝÁÑ "ÓÉÍ×ÏÌ" */
62 /* ÓÍÅÝÅÎÉÅ ÏÔ ÔÅËÕÝÅÇÏ "ÓÉÍ×ÏÌÁ" ÄÏ ÓÓÙÌËÉ ÎÁ ÄÏÞÅÒÎÉÊ ÕÚÅÌ × ÂÁÊÔÁÈ */
66 /* × ÌÀÂÏÍ "ÓÉÍ×ÏÌÏ×" isword + haschild > 0 */
67 /* ÚÁËÁÎÞÉ×ÁÅÔÓÑ ÌÉ ÚÄÅÓØ ÓÌÏ×Ï */
69 /* ÅÓÔØ ÌÉ ÄÏÞÅÒÎÉÊ ÕÚÅÌ */
72 /* ÓÍÅÝÅÎÉÅ ÏÔ SFSNode->dataptr ÄÏ ÚÎÁÞÅÎÉÑ × ÅÄÉÎÉÃÁÈ SFSTree->datasize */
74 /* óÏÂÓÔ×ÅÎÎÏ ÓÉÍ×ÏÌ */
78 /* úÁÇÏÌÏ×ÏË ÕÚÌÁ ÄÅÒÅ×Á */
79 typedef struct SFSNode {
83 /* ÚÁËÁÎÞÉ×ÁÅÔÓÑ ÌÉ ËÌÀÞ × ÜÔÏÍ ÕÚÌÅ (ÔÏÌØËÏ ÄÌÑ ÕÚÌÁ "ÐÕÔÅ×ÏÊ ËÏÍÐÒÅÓÉÉ,
84 ÄÌÑ "×ÅÔ×ÑÝÅÇÏÓÑ" - ÎÅÉÓÐÏÌØÚÕÅÔÓÑ) */
87 /* ÅÓÔØ ÌÉ ÒÅÂÅÎÏË ÜÔÏÇÏ ÕÚÌÁ (ÔÏÌØËÏ ÄÌÑ ÕÚÌÁ "ÐÕÔÅ×ÏÊ ËÏÍÐÒÅÓÉÉ,
88 ÄÌÑ "×ÅÔ×ÑÝÅÇÏÓÑ" - ÎÅÉÓÐÏÌØÚÕÅÔÓÑ) */
92 /* "ÐÕÔÅ×ÏÊ": ÓÍÅÝÅÎÉÅ × ÂÁÊÔÁÈ ÏÔ ÎÁÞÁÌÁ ÕÚÌÁ ÄÏ ÎÁÞÁÌÁ "ÓËÏÍÐÒÅÓÓÉÒÏ×ÁÎÎÏÊ" ÞÁÓÔÉ ÐÕÔÉ */
93 /* "×ÅÔ×ÑÝÉÊÓÑ": ÓÍÅÝÅÎÉÅ × ÂÁÊÔÁÈ ÏÔ ÎÁÞÁÌÁ ÕÚÌÁ ÄÏ ÎÁÞÁÌÁ ÍÁÓÓÉ×Á ÚÎÁÞÅÎÉÊ */
96 /* "ÐÕÔÅ×ÏÊ": ÎÅÉÓÐÏÌØÚÕÅÔÓÑ */
97 /* "×ÅÔ×ÑÝÉÊÓÑ": ËÏÌ-×Ï ÄÏÞÅÒÎÉÈ ÕÚÌÏ× */
100 /* "ÐÕÔÅ×ÏÊ": ËÏÌ-×Ï "ÓËÏÍÐÒÅÓÓÏ×ÁÎÎÙÈ" ÕÚÌÏ× */
101 /* "×ÅÔ×ÑÝÉÊÓÑ": ËÏÌ-×Ï "ÓÉÍ×ÏÌÏ×" */
106 #define SFSNHRDSZ (sizeof(u_int32_t))
109 /* ÓÔÒÕËÔÕÒÁ ÄÌÑ ÏÂÈÏÄÁ ÄÅÒÅ×Á ÉÔÅÒÁÔÏÒÏÍ */
110 typedef struct SFSNodeStack {
111 /* ÕËÁÚÁÔÅÌØ ÎÁ ÕÚÅÌ */
113 /* ÕËÁÚÁÔÅÌØ ÎÁ "ÓÉÍ×ÏÌ" ÕÚÌÁ */
116 /* ÆÌÁÇ ÐÒÏ×ÅÒËÉ ËÌÀÞÁ */
118 /* ÆÌÁÇ ÐÒÏ×ÅÒËÉ ÄÏÞÅÒÎÅÇÏ ÕÚÌÁ */
122 struct SFSNodeStack *next;
126 /* óÔÁÔÉÓÔÉÞÅÓËÉÅ ÄÁÎÎÙÅ */
127 u_int64_t totalen; /* ÏÂÝÅÅ ËÏÌ-×Ï ÍÁÌÌÏÃÉÒÏ×ÁÎÎÏÊ ÐÁÍÑÔÉ */
128 u_int64_t nnodes; /* ÏÂÝÅÅ ËÏÌ-×Ï ÕÚÌÏ× ÄÅÒÅ×Á */
129 char plainmemory; /* true ÅÓÌÉ ÄÅÒÅ×Ï × ÐÌÏÓËÏÊ ÐÁÍÑÔÉ */
131 u_int32_t datasize; /* ÒÁÚÍÅÒ ÚÎÁÞÅÎÉÑ (ËÒÁÔÅÎ sizeof(u_int32_t))*/
132 SFSNode *node; /* ËÏÒÎÅ×ÏÊ ÕÚÅÌ ÄÅÒÅ×Á */
135 SFSNodeStack *stack; /* ÓÔÅË ÏÂÈÏÄÁ ÄÅÒÅ×Á */
136 char *buf; /* ÂÕÆÅÒ ËÌÀÞÁ */
137 int tlen; /* ÅÇÏ ÄÌÉÎÁ */
139 /* addon for prefix iterator */
140 int hasword; /* ÅÓÔØ ÌÉ ËÌÀÞ, ÒÁ×ÎÏÅ ÐÒÅÆÉËÓÕ (ÓÌÕÖÅÂÎÏÅ ÐÏÌÅ) */
141 void *wdata; /* ÕËÁÚÁÔÅÌØ ÎÁ ÚÎÁÞÅÎÉÅ ËÌÀÞÁ, ÒÁ×ÎÏÇÏ ÐÒÅÆÉËÓÕ (ÓÌÕÖÅÂÎÏÅ ÐÏÌÅ) */
144 /* ÓÔÒÕËÔÕÒÁ ××ÏÄÁ - ×Ù×ÏÄÁ ÚÁÐÉÓÅÊ */
146 /* ËÌÀÞ, ÄÏÌÖÅÎ ÚÁËÁÎÞÔÉ×ÁÔØÓÑ ÓÉÍ×ÏÌÏÍ '\0' */
148 /* ÄÌÉÎÁ ËÌÀÞÁ. ðÒÉ ××ÏÄÅ ÄÏÌÖÎÏ ÓÏÄÅÒÖÁÔØ ÄÌÉÎÕ ËÌÀÞÁ ÉÌÉ 0.
149 ðÒÉ ×Ù×ÏÄÅ ×ÓÅÇÄÁ ÓÏÄÅÒÖÉÔ ÄÌÉÎÕ ËÌÀÞÁ */
151 /* ÕËÁÚÁÔÅÌØ ÎÁ ÚÎÁÞÅÎÉÅ */
156 * ëÏÒÒÅËÔÎÏÓÔØ ÆÕÎËÃÉÏÎÉÒÏ×ÁÎÉÑ ËÏÎÔÒÏÌÉÒÕÅÔÓÑ assert'ÏÍ,
157 * × ÔÏÍ ÞÉÓÌÅ É ËÏÎÔÒÏÌØ ÚÁ malloc/realloc
158 * ÷ÓÅ Æ-ÃÉÉ ÒÁÓÓÞÉÔÁÎÙ ÎÁ ËÌÀÞÉ, ÚÁËÁÎÞÉ×ÁÀÝÉÍÉÓÑ ÓÉÍ×ÏÌÏÍ '\0'
162 * Æ-ÃÉÉ ÉÎÉÃÉÁÌÉÚÁÃÉÉ, datasize - ÒÁÚÍÅÒ × ÂÁÊÔÁÈ
163 * ÚÎÁÞÅÎÉÑ, ÐÒÉ×ÑÚÁÎÎÏÊ Ë ËÌÀÞÁÍ.
164 * SFSInit_c ÐÒÅÄÐÏÌÁÇÁÅÔ, ÞÔÏ ÚÎÁÞÅÎÉÑ ÏÔÓÕÔÓÔ×ÕÀÔ.
165 * òÁÚÍÅÒ ÓÔÒÕËÔÕÒÙ ÄÏÌÖÅÎ ÂÙÔØ ÒÁ×ÅÎ ËÒÁÔÅÎ sizeof(u_int32_t)
167 SFSTree* SFSInit_dp(SFSTree *info, u_int32_t datasize, SFSDataIO *in);
168 SFSTree* SFSInit_c(SFSTree *info, char **in);
171 * ïÓ×ÏÂÏÖÄÅÎÉÅ ÐÁÍÑÔÉ, ÚÁÎÑÔÏÊ ÄÅÒÅ×ÏÍ.
172 * åÓÌÉ ÕËÁÚÁÎÁ freefunc, ÔÏ ÏÎÁ ×ÙÚÙ×ÁÅÔÓÑ ÄÌÑ
173 * ËÁÖÄÏÇÏ ÚÎÁÞÅÎÉÑ , ÐÒÉ×ÑÚÁÎÎÏÇÏ Ë ËÌÀÞÁÍ
175 void SFSFree(SFSTree *info, void (*freefunc)(void*));
178 * äÏÂÁ×ÌÅÎÉÅ ÐÁÒÙ ËÌÀÞ-ÚÎÁÞÅÎÉÅ
180 void SFSAdd(SFSTree *info, SFSDataIO *in);
183 * ðÏÉÓË ÚÎÁÞÅÎÉÑ ÐÏ ËÌÀÞÕ, × ÓÌÕÞÁÅ ÕÓÐÅÈÁ ×ÏÚ×ÒÁÝÁÅÔ
184 * ÕËÁÚÁÔÅÌØ ÎÁ ÚÎÁÞÅÎÉÅ, ÉÎÁÞÅ - NULL
186 void* SFSFindData(SFSTree *info, char *word, int len /* optional */ );
188 typedef struct SFSTreePosition {
194 void* SFSFindDataOrSave(SFSTree *info, SFSDataIO *in, SFSTreePosition *position);
195 void* SFSFindDataFromSavedOrSave(SFSTree *info, SFSDataIO *in, SFSTreePosition *position);
196 void SFSAddSaved(SFSTree *info, SFSDataIO *in, SFSTreePosition *position);
199 * éÎÉÃÉÁÌÉÚÁÃÉÑ ÉÔÅÒÁÔÏÒÁ × ÎÁÞÁÌÏ ÄÅÒÅ×Á
201 void SFSIteratorStart(SFSTree *info);
204 * éÎÉÃÉÁÌÉÚÁÃÉÑ ÉÔÅÒÁÔÏÒÁ Ë ËÌÀÞÕ, ÂÏÌØÛÅ ÉÌÉ ÒÁ×ÎÏÍÕ
207 void SFSPrefixIteratorStart(SFSTree *info, char *word);
210 * ïÂÈÏÄ ÉÔÅÒÁÔÏÒÁ, × ÓÌÕÞÁÅ ÕÓÐÅÈÁ ×ÏÚ×ÒÁÝÁÅÔ 1 É ÚÁÐÏÌÎÅÎÎÕÀ
211 * ÓÔÒÕËÔÕÒÕ SFSDataIO *out, ÉÎÁÞÅ 0 É ÎÅÐÒÅÄÓËÁÚÕÅÍÏ ÚÁÐÏÌÎÅÎÎÕÀ
212 * ÓÔÒÕËÔÕÒÕ SFSDataIO *out. ÷ ÓÔÒÕËÔÕÒÅ out ÐÏÌÑ key É data
213 * îå ÄÏÌÖÎÙ ÉÚÍÅÎÑÔØÓÑ ÉÌÉ ÏÓ×ÏÂÏÖÄÁÔØÓÑ ÐÁÍÑÔØ.
214 * æ-ÃÉÑ ÐÒÅËÒÁÝÁÅÔ ÏÂÈÏÄ:
215 * 1) ÉÎÉÃÉÁÌÉÚÁÃÉÑ SFSIteratorStart: ×ÙÂÒÁÎÙ ×ÓÅ ËÌÀÞÉ
216 * 2) -/- SFSPrefixIteratorStart: ×ÙÂÒÁÎÙ ×ÓÅ ËÌÀÞÉ Ó ÚÁÄÁÎÎÙÍ ÐÒÅÆÉËÓÏÍ.
217 * ëÌÀÞÉ ×ÙÄÁÀÔÓÑ × ÌÅËÓÉËÏÇÒÁÆÉÞÅÓËÏÍ ÐÏÒÑÄËÅ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÍ
220 int SFSIterate(SFSTree *info, SFSDataIO *out);
223 * ðÏÉÓË ÍÉÎÉÍÁÌØÎÏÇÏ É ÍÁËÓÉÍÁÌØÎÏÇÏ ËÌÀÞÅÊ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ
224 * ÐÒÅÆÉËÓÕ word. ÷ ÓÌÕÞÁÅ ÕÓÐÅÈÁ ×ÏÚ×ÒÁÝÁÅÔ 1 É ÚÁÐÏÌÎÅÎÎÙÅ ÓÔÒÕËÔÕÒÙ f É l,
225 * byfxt - 0 É "ÍÕÓÏÒ" × f É l. ÷ ÓÔÒÕËÔÕÒÁÈ f É l ÐÏÌÑ key É data
226 * îå ÄÏÌÖÎÙ ÉÚÍÅÎÑÔØÓÑ ÉÌÉ ÏÓ×ÏÂÏÖÄÁÔØÓÑ ÐÁÍÑÔØ.
228 int SFSRange(SFSTree *info, char *word, SFSDataIO *f, SFSDataIO *l);
231 * ëÏÐÉÒÕÅÔ ÄÅÒÅ×Ï × "ÐÌÏÓËÕÀ" ÐÁÍÑÔØ. "ðÌÏÓËÏÅ" ÄÅÒÅ×Ï Read Only.
233 void SFSMakePlain(SFSTree *info, void *pointer);
236 * ëÏÎ×ÅÒÔÉÒÕÅÔ "ÐÌÏÓËÏÅ" ÄÅÒÅ×Ï × ÏÂÙÞÎÏÅ.
238 void * SFSRevertPlain(SFSTree *info);
240 typedef struct SFSTreeDumpHeader {
242 u_int16_t opaquesize;
243 u_int16_t headersize;
250 #define SFSTDHSZ MAXALIGN( sizeof(SFSTreeDumpHeader) )
253 * óÏÚÄÁÅÔ dump ÄÅÒÅ×Á, ÎÅ ÔÒÅÂÕÅÔ ÂÏÌØÛÏÇÏ ÒÁÓÈÏÄÁ ÐÁÍÑÔÉ
255 void SFSWriteDump(SFSTree *info, char *filename, void *extradata, u_int32_t extrasize);
258 * óÏÚÄÁÅÔ "ÏÂÙÞÎÏÅ" (ÎÅ ÐÌÏÓËÏÅ) ÄÅÒÅ×Ï ÉÚ ÄÁÍÐÁ,
259 * ÎÅ ÔÒÅÂÕÅÔ ÂÏÌØÛÏÇÏ ÒÁÓÈÏÄÁ ÐÁÍÑÔÉ
262 void SFSReadDump(SFSTree *info, char *filename, void **extradata, u_int32_t *extrasize);
265 * éÎÉÃÉÁÌÉÚÉÒÕÅÔ "ÐÌÏÓËÏÅ" ÄÅÒÅ×Ï ÉÚ ÏÂÒÁÚÁ ÄÁÍÐÁ
268 void SFSInitFromDump(SFSTree *info, void *pointer, u_int64_t size, void **extradata, u_int32_t *extrasize);