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);
189 * éÎÉÃÉÁÌÉÚÁÃÉÑ ÉÔÅÒÁÔÏÒÁ × ÎÁÞÁÌÏ ÄÅÒÅ×Á
191 void SFSIteratorStart(SFSTree *info);
194 * éÎÉÃÉÁÌÉÚÁÃÉÑ ÉÔÅÒÁÔÏÒÁ Ë ËÌÀÞÕ, ÂÏÌØÛÅ ÉÌÉ ÒÁ×ÎÏÍÕ
197 void SFSPrefixIteratorStart(SFSTree *info, char *word);
200 * ïÂÈÏÄ ÉÔÅÒÁÔÏÒÁ, × ÓÌÕÞÁÅ ÕÓÐÅÈÁ ×ÏÚ×ÒÁÝÁÅÔ 1 É ÚÁÐÏÌÎÅÎÎÕÀ
201 * ÓÔÒÕËÔÕÒÕ SFSDataIO *out, ÉÎÁÞÅ 0 É ÎÅÐÒÅÄÓËÁÚÕÅÍÏ ÚÁÐÏÌÎÅÎÎÕÀ
202 * ÓÔÒÕËÔÕÒÕ SFSDataIO *out. ÷ ÓÔÒÕËÔÕÒÅ out ÐÏÌÑ key É data
203 * îå ÄÏÌÖÎÙ ÉÚÍÅÎÑÔØÓÑ ÉÌÉ ÏÓ×ÏÂÏÖÄÁÔØÓÑ ÐÁÍÑÔØ.
204 * æ-ÃÉÑ ÐÒÅËÒÁÝÁÅÔ ÏÂÈÏÄ:
205 * 1) ÉÎÉÃÉÁÌÉÚÁÃÉÑ SFSIteratorStart: ×ÙÂÒÁÎÙ ×ÓÅ ËÌÀÞÉ
206 * 2) -/- SFSPrefixIteratorStart: ×ÙÂÒÁÎÙ ×ÓÅ ËÌÀÞÉ Ó ÚÁÄÁÎÎÙÍ ÐÒÅÆÉËÓÏÍ.
207 * ëÌÀÞÉ ×ÙÄÁÀÔÓÑ × ÌÅËÓÉËÏÇÒÁÆÉÞÅÓËÏÍ ÐÏÒÑÄËÅ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÍ
210 int SFSIterate(SFSTree *info, SFSDataIO *out);
213 * ðÏÉÓË ÍÉÎÉÍÁÌØÎÏÇÏ É ÍÁËÓÉÍÁÌØÎÏÇÏ ËÌÀÞÅÊ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ
214 * ÐÒÅÆÉËÓÕ word. ÷ ÓÌÕÞÁÅ ÕÓÐÅÈÁ ×ÏÚ×ÒÁÝÁÅÔ 1 É ÚÁÐÏÌÎÅÎÎÙÅ ÓÔÒÕËÔÕÒÙ f É l,
215 * byfxt - 0 É "ÍÕÓÏÒ" × f É l. ÷ ÓÔÒÕËÔÕÒÁÈ f É l ÐÏÌÑ key É data
216 * îå ÄÏÌÖÎÙ ÉÚÍÅÎÑÔØÓÑ ÉÌÉ ÏÓ×ÏÂÏÖÄÁÔØÓÑ ÐÁÍÑÔØ.
218 int SFSRange(SFSTree *info, char *word, SFSDataIO *f, SFSDataIO *l);
221 * ëÏÐÉÒÕÅÔ ÄÅÒÅ×Ï × "ÐÌÏÓËÕÀ" ÐÁÍÑÔØ. "ðÌÏÓËÏÅ" ÄÅÒÅ×Ï Read Only.
223 void SFSMakePlain(SFSTree *info, void *pointer);
226 * ëÏÎ×ÅÒÔÉÒÕÅÔ "ÐÌÏÓËÏÅ" ÄÅÒÅ×Ï × ÏÂÙÞÎÏÅ.
228 void * SFSRevertPlain(SFSTree *info);
230 typedef struct SFSTreeDumpHeader {
232 u_int32_t opaquesize;
233 u_int32_t headersize;
239 #define SFSTDHSZ ( MAXALIGN(sizeof(SFSTreeDumpHeader)) )
242 * óÏÚÄÁÅÔ dump ÄÅÒÅ×Á, ÎÅ ÔÒÅÂÕÅÔ ÂÏÌØÛÏÇÏ ÒÁÓÈÏÄÁ ÐÁÍÑÔÉ
244 void SFSWriteDump(SFSTree *info, char *filename);
247 * óÏÚÄÁÅÔ "ÏÂÙÞÎÏÅ" (ÎÅ ÐÌÏÓËÏÅ) ÄÅÒÅ×Ï ÉÚ ÄÁÍÐÁ,
248 * ÎÅ ÔÒÅÂÕÅÔ ÂÏÌØÛÏÇÏ ÒÁÓÈÏÄÁ ÐÁÍÑÔÉ
251 void SFSReadDump(SFSTree *info, char *filename);
254 * éÎÉÃÉÁÌÉÚÉÒÕÅÔ "ÐÌÏÓËÏÅ" ÄÅÒÅ×Ï ÉÚ ÏÂÒÁÚÁ ÄÁÍÐÁ
257 void SFSInitFromDump(SFSTree *info, void *pointer, u_int64_t size);