Fix bug in GListTruncate, extends templates tests
[tedtools.git] / sfxstr.h
1 /*
2  * Copyright (c) 2004 Teodor Sigaev <teodor@sigaev.ru>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
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.
16  *
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.
28  */
29
30 #ifndef __SFXSTR_H__
31 #define __SFXSTR_H__
32
33 #include <sys/types.h>
34
35 /* 
36  * ëÁÖÄÙÊ ÕÚÅÌ ÄÅÒÅ×Á ÍÏÖÅÔ ÂÙÔÔØ ÏÂÎÉÍ ÉÚ Ä×ÕÈ ÔÉÐÏ×:
37  * SFSNode->isskip = 1  - ÕÚÅÌ "ÐÕÔÅ×ÏÊ ËÏÍÐÒÅÓÉÉ". 
38  *    ôÁËÏÊ ÕÚÅÌ ÍÏÖÅÔ ÉÍÅÔØ ÏÄÎÏÇÏ ÒÅÂÅÎËÁ É/ÉÌÉ
39  *    ÏÄÎÏ ÓÌÏ×Ï.
40  * SFSNode->isskip = 0  - "×ÅÔ×ÑÝÉÊÓÑ ÕÚÅÌ"
41  *
42  * "×ÅÔ×ÑÝÉÊÓÑ" ÕÚÅÌ ÄÅÒÅ×Á ÈÒÁÎÉÔØÓÑ × ÐÁÍÑÔÉ ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏÍ:
43  *  ( SFSNHRDSZ ÂÁÊÔÁ ) SFSNode - ÚÁÇÏÌÏ×ÏË ÕÚÌÁ
44  *  ( sizeof(SFSNodeData)*SFSNode->nchar ÂÁÊÔÁ) SFSNodeData[] - ÍÁÓÓÉ× "ÓÉÍ×ÏÌÏ×"
45  *  ( sizeof(SFSNode*)*SFSNode->nchild ÂÁÊÔÁ ) *SFSNode[] - ÍÁÓÓÉ× ÓÓÙÌÏË ÎÁ ÄÏÞÅÒÎÉÅ ÕÚÌÙ
46  *  ( SFSTree->datasize * (ËÏÌÉÞÅÓÔ×Ï ÓÌÏ×, ÚÁËÁÎÞÉ×ÁÀÝÉÈÓÑ × ÜÔÏÍ ÕÚÌÅ) ) - 
47  *         ÍÁÓÓÉ× ÚÎÁÞÅÎÉÊ
48  *
49  *  ÍÁÓÓÉ× "ÓÉÍ×ÏÌÏ×" - ÕÐÏÒÑÄÏÞÅΠÐÏ ÓÉÍ×ÏÌÁÍ (SFSNodeData->val),
50  *  ÐÏÒÑÄÏË ÏÓÔÁÌØÎÙÈ ÍÁÓÓÉ×Ï× ÚÁÄÁÅÔÓÑ ÍÁÓÓÉ×ÏÍ "ÓÉÍ×ÏÌÏ×"
51  *  ÕÚÅÌ "ÐÕÔÅ×ÏÊ ËÏÍÐÒÅÓÉÉ" ÈÒÁÎÉÔØÓÑ × ÐÁÍÑÔÉ ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏÍ:
52  *  ( SFSNHRDSZ ÂÁÊÔÁ ) SFSNode - ÚÁÇÏÌÏ×ÏË ÕÚÌÁ
53  *  sizeof(SFSNode*) ÂÁÊÔ - ÓÓÙÌËÁ ÎÁ ÒÅÂÅÎËÁ (ÎÅÏÂÑÚÁÔÅÌØÎÏÅ ÐÏÌÅ)
54  *  SFSTree->datasize ÂÁÊÔ - ÚÎÁÞÅÎÉÅ, ÅÓÌÉ ÚÄÅÓØ ÚÁËÁÎÞÉ×ÁÅÔÓÑ ËÌÀÞ 
55  *                        (ÎÅÏÂÑÚÁÔÅÌØÎÏÅ ÐÏÌÅ)
56  *  SFSTree->nchar ÂÁÊÔ - "ÓËÏÍÐÒÅÓÓÉÒÏ×ÁÎÎÁÑ" ÞÁÓÔØ ÐÕÔÉ. 
57  */ 
58
59 /* ÓÔÒÕËÔÕÒÁ, ÏÐÉÓÙ×ÁÀÝÁÑ "ÓÉÍ×ÏÌ" */
60 typedef struct {
61         u_int32_t
62                 /* ÓÍÅÝÅÎÉÅ ÏÔ ÔÅËÕÝÅÇÏ "ÓÉÍ×ÏÌÁ" ÄÏ ÓÓÙÌËÉ ÎÁ ÄÏÞÅÒÎÉÊ ÕÚÅÌ  × ÂÁÊÔÁÈ */
63                 child:10,  
64                 unused:4,
65
66                 /* × ÌÀÂÏÍ "ÓÉÍ×ÏÌÏ×" isword + haschild > 0 */
67                 /* ÚÁËÁÎÞÉ×ÁÅÔÓÑ ÌÉ ÚÄÅÓØ ÓÌÏ×Ï */ 
68                 isword:1,  
69                 /* ÅÓÔØ ÌÉ ÄÏÞÅÒÎÉÊ ÕÚÅÌ */
70                 haschild:1,
71
72                 /* ÓÍÅÝÅÎÉÅ ÏÔ SFSNode->dataptr ÄÏ ÚÎÁÞÅÎÉÑ × ÅÄÉÎÉÃÁÈ SFSTree->datasize */ 
73                 data:8, 
74                 /* óÏÂÓÔ×ÅÎÎÏ ÓÉÍ×ÏÌ */
75                 val:8; 
76 } SFSNodeData;
77
78 /* úÁÇÏÌÏ×ÏË ÕÚÌÁ ÄÅÒÅ×Á */
79 typedef struct SFSNode {
80         u_int32_t
81                 /* ÔÉРÕÚÌÁ */ 
82                 isskip:1,
83                 /* ÚÁËÁÎÞÉ×ÁÅÔÓÑ ÌÉ ËÌÀÞ × ÜÔÏÍ ÕÚÌÅ (ÔÏÌØËÏ ÄÌÑ ÕÚÌÁ "ÐÕÔÅ×ÏÊ ËÏÍÐÒÅÓÉÉ,
84                    ÄÌÑ "×ÅÔ×ÑÝÅÇÏÓÑ" - ÎÅÉÓÐÏÌØÚÕÅÔÓÑ) */
85                 isword:1,
86
87                 /* ÅÓÔØ ÌÉ ÒÅÂÅÎÏË ÜÔÏÇÏ ÕÚÌÁ (ÔÏÌØËÏ ÄÌÑ ÕÚÌÁ "ÐÕÔÅ×ÏÊ ËÏÍÐÒÅÓÉÉ,
88                    ÄÌÑ "×ÅÔ×ÑÝÅÇÏÓÑ" - ÎÅÉÓÐÏÌØÚÕÅÔÓÑ) */
89                 haschild:1, 
90                 unused:1,
91  
92                 /* "ÐÕÔÅ×ÏÊ": ÓÍÅÝÅÎÉÅ × ÂÁÊÔÁÈ ÏÔ ÎÁÞÁÌÁ ÕÚÌÁ ÄÏ ÎÁÞÁÌÁ "ÓËÏÍÐÒÅÓÓÉÒÏ×ÁÎÎÏÊ" ÞÁÓÔÉ ÐÕÔÉ */ 
93                 /* "×ÅÔ×ÑÝÉÊÓÑ": ÓÍÅÝÅÎÉÅ × ÂÁÊÔÁÈ ÏÔ ÎÁÞÁÌÁ ÕÚÌÁ ÄÏ ÎÁÞÁÌÁ ÍÁÓÓÉ×Á ÚÎÁÞÅÎÉÊ */ 
94                 dataptr:12,
95
96                 /* "ÐÕÔÅ×ÏÊ": ÎÅÉÓÐÏÌØÚÕÅÔÓÑ */ 
97                 /* "×ÅÔ×ÑÝÉÊÓÑ": ËÏÌ-×Ï ÄÏÞÅÒÎÉÈ ÕÚÌÏ× */ 
98                 nchild:8,
99
100                 /* "ÐÕÔÅ×ÏÊ": ËÏÌ-×Ï "ÓËÏÍÐÒÅÓÓÏ×ÁÎÎÙÈ" ÕÚÌÏ× */
101                 /* "×ÅÔ×ÑÝÉÊÓÑ": ËÏÌ-×Ï "ÓÉÍ×ÏÌÏ×" */
102                 nchar:8;
103         SFSNodeData      data[1];
104 } SFSNode;
105
106 #define SFSNHRDSZ        (sizeof(u_int32_t))
107
108
109 /* ÓÔÒÕËÔÕÒÁ ÄÌÑ ÏÂÈÏÄÁ ÄÅÒÅ×Á ÉÔÅÒÁÔÏÒÏÍ */
110 typedef struct SFSNodeStack {
111         /* ÕËÁÚÁÔÅÌØ ÎÁ ÕÚÅÌ */
112         SFSNode *node;  
113         /* ÕËÁÚÁÔÅÌØ ÎÁ "ÓÉÍ×ÏÌ" ÕÚÌÁ */ 
114         SFSNodeData *data;
115         u_int32_t 
116                 /* ÆÌÁÇ ÐÒÏ×ÅÒËÉ ËÌÀÞÁ */ 
117                 checkedval:1,
118                 /* ÆÌÁÇ ÐÒÏ×ÅÒËÉ  ÄÏÞÅÒÎÅÇÏ ÕÚÌÁ */ 
119                 checkedchild:1,
120                 /* "ÇÌÕÂÉÎÁ" ÕÚÌÁ */
121                 level:30;
122         struct SFSNodeStack *next;
123 } SFSNodeStack;
124
125 typedef struct {
126         /* óÔÁÔÉÓÔÉÞÅÓËÉÅ ÄÁÎÎÙÅ */
127         u_int64_t       totalen; /* ÏÂÝÅÅ ËÏÌ-×Ï ÍÁÌÌÏÃÉÒÏ×ÁÎÎÏÊ ÐÁÍÑÔÉ */
128         u_int64_t       nnodes;  /* ÏÂÝÅÅ ËÏÌ-×Ï ÕÚÌÏ× ÄÅÒÅ×Á */
129         char            plainmemory;  /* true ÅÓÌÉ ÄÅÒÅ×Ï × ÐÌÏÓËÏÊ ÐÁÍÑÔÉ */ 
130
131         u_int32_t       datasize; /* ÒÁÚÍÅÒ ÚÎÁÞÅÎÉÑ (ËÒÁÔÅΠsizeof(u_int32_t))*/
132         SFSNode         *node;    /* ËÏÒÎÅ×ÏÊ ÕÚÅÌ ÄÅÒÅ×Á */
133
134         /* iterator */
135         SFSNodeStack    *stack;  /* ÓÔÅË ÏÂÈÏÄÁ ÄÅÒÅ×Á */ 
136         char            *buf;    /* ÂÕÆÅÒ ËÌÀÞÁ */
137         int             tlen;    /* ÅÇÏ ÄÌÉÎÁ */
138
139         /* addon for prefix iterator */
140         int             hasword; /* ÅÓÔØ ÌÉ ËÌÀÞ, ÒÁ×ÎÏÅ ÐÒÅÆÉËÓÕ (ÓÌÕÖÅÂÎÏÅ ÐÏÌÅ) */
141         void            *wdata;  /* ÕËÁÚÁÔÅÌØ ÎÁ ÚÎÁÞÅÎÉÅ ËÌÀÞÁ, ÒÁ×ÎÏÇÏ ÐÒÅÆÉËÓÕ (ÓÌÕÖÅÂÎÏÅ ÐÏÌÅ) */ 
142 }       SFSTree;
143
144 /* ÓÔÒÕËÔÕÒÁ ××ÏÄÁ - ×Ù×ÏÄÁ ÚÁÐÉÓÅÊ */
145 typedef struct {
146         /* ËÌÀÞ, ÄÏÌÖÅΠÚÁËÁÎÞÔÉ×ÁÔØÓÑ ÓÉÍ×ÏÌÏÍ '\0' */ 
147         char    *key;
148         /* ÄÌÉÎÁ ËÌÀÞÁ.  ðÒÉ ××ÏÄÅ ÄÏÌÖÎÏ ÓÏÄÅÒÖÁÔØ ÄÌÉÎÕ ËÌÀÞÁ ÉÌÉ 0. 
149            ðÒÉ ×Ù×ÏÄÅ ×ÓÅÇÄÁ ÓÏÄÅÒÖÉÔ ÄÌÉÎÕ ËÌÀÞÁ */ 
150         int     keylen;
151         /* ÕËÁÚÁÔÅÌØ ÎÁ ÚÎÁÞÅÎÉÅ */
152         void    *data;
153 } SFSDataIO;
154
155 /*
156  *  ëÏÒÒÅËÔÎÏÓÔØ ÆÕÎËÃÉÏÎÉÒÏ×ÁÎÉÑ ËÏÎÔÒÏÌÉÒÕÅÔÓÑ assert'ÏÍ,
157  *  × ÔÏÍ ÞÉÓÌÅ É ËÏÎÔÒÏÌØ ÚÁ malloc/realloc
158  *  ÷ÓÅ Æ-ÃÉÉ ÒÁÓÓÞÉÔÁÎÙ ÎÁ ËÌÀÞÉ, ÚÁËÁÎÞÉ×ÁÀÝÉÍÉÓÑ ÓÉÍ×ÏÌÏÍ '\0'
159  */
160
161 /* 
162  * Æ-ÃÉÉ ÉÎÉÃÉÁÌÉÚÁÃÉÉ, datasize - ÒÁÚÍÅÒ × ÂÁÊÔÁÈ
163  * ÚÎÁÞÅÎÉÑ, ÐÒÉ×ÑÚÁÎÎÏÊ Ë ËÌÀÞÁÍ.
164  * SFSInit_c ÐÒÅÄÐÏÌÁÇÁÅÔ, ÞÔÏ ÚÎÁÞÅÎÉÑ ÏÔÓÕÔÓÔ×ÕÀÔ.
165  * òÁÚÍÅÒ ÓÔÒÕËÔÕÒÙ ÄÏÌÖÅΠÂÙÔØ ÒÁ×ÅΠËÒÁÔÅΠsizeof(u_int32_t)
166  */
167 SFSTree* SFSInit_dp(SFSTree *info, u_int32_t datasize, SFSDataIO *in);
168 SFSTree* SFSInit_c(SFSTree *info, char **in);
169
170 /*
171  * ïÓ×ÏÂÏÖÄÅÎÉÅ ÐÁÍÑÔÉ, ÚÁÎÑÔÏÊ ÄÅÒÅ×ÏÍ.
172  * åÓÌÉ ÕËÁÚÁÎÁ freefunc, ÔÏ ÏÎÁ ×ÙÚÙ×ÁÅÔÓÑ ÄÌÑ
173  * ËÁÖÄÏÇÏ ÚÎÁÞÅÎÉÑ , ÐÒÉ×ÑÚÁÎÎÏÇÏ Ë ËÌÀÞÁÍ
174  */ 
175 void SFSFree(SFSTree *info, void (*freefunc)(void*));
176
177 /* 
178  * äÏÂÁ×ÌÅÎÉÅ ÐÁÒÙ ËÌÀÞ-ÚÎÁÞÅÎÉÅ 
179  */
180 void SFSAdd(SFSTree *info, SFSDataIO *in);
181
182 /*
183  * ðÏÉÓË ÚÎÁÞÅÎÉÑ ÐÏ ËÌÀÞÕ, × ÓÌÕÞÁÅ ÕÓÐÅÈÁ ×ÏÚ×ÒÁÝÁÅÔ 
184  * ÕËÁÚÁÔÅÌØ ÎÁ ÚÎÁÞÅÎÉÅ, ÉÎÁÞÅ - NULL
185  */
186 void* SFSFindData(SFSTree *info, char *word, int len /* optional */ );
187
188 typedef struct SFSTreePosition {
189         SFSNode         **nodeptr;
190         SFSNode          *node;
191         int                       level;
192 } SFSTreePosition;
193
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);
197
198 /*
199  * éÎÉÃÉÁÌÉÚÁÃÉÑ ÉÔÅÒÁÔÏÒÁ × ÎÁÞÁÌÏ ÄÅÒÅ×Á 
200  */
201 void SFSIteratorStart(SFSTree *info);
202
203 /*
204  * éÎÉÃÉÁÌÉÚÁÃÉÑ ÉÔÅÒÁÔÏÒÁ Ë ËÌÀÞÕ, ÂÏÌØÛÅ ÉÌÉ ÒÁ×ÎÏÍÕ
205  * word 
206  */
207 void SFSPrefixIteratorStart(SFSTree *info, char *word);
208
209 /* 
210  * ïÂÈÏÄ ÉÔÅÒÁÔÏÒÁ, × ÓÌÕÞÁÅ ÕÓÐÅÈÁ ×ÏÚ×ÒÁÝÁÅÔ 1 É ÚÁÐÏÌÎÅÎÎÕÀ
211  * ÓÔÒÕËÔÕÒÕ SFSDataIO *out, ÉÎÁÞÅ 0 É ÎÅÐÒÅÄÓËÁÚÕÅÍÏ ÚÁÐÏÌÎÅÎÎÕÀ
212  * ÓÔÒÕËÔÕÒÕ SFSDataIO *out. ÷ ÓÔÒÕËÔÕÒÅ out ÐÏÌÑ key É data
213  * îå ÄÏÌÖÎÙ ÉÚÍÅÎÑÔØÓÑ ÉÌÉ ÏÓ×ÏÂÏÖÄÁÔØÓÑ ÐÁÍÑÔØ.
214  * æ-ÃÉÑ ÐÒÅËÒÁÝÁÅÔ ÏÂÈÏÄ:
215  *  1) ÉÎÉÃÉÁÌÉÚÁÃÉÑ SFSIteratorStart: ×ÙÂÒÁÎÙ ×ÓÅ ËÌÀÞÉ
216  *  2) -/- SFSPrefixIteratorStart: ×ÙÂÒÁÎÙ ×ÓÅ ËÌÀÞÉ Ó ÚÁÄÁÎÎÙÍ ÐÒÅÆÉËÓÏÍ.
217  * ëÌÀÞÉ ×ÙÄÁÀÔÓÑ × ÌÅËÓÉËÏÇÒÁÆÉÞÅÓËÏÍ ÐÏÒÑÄËÅ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÍ
218  * ASCI ËÏÄÉÒÏ×ËÅ. 
219  */ 
220 int SFSIterate(SFSTree *info, SFSDataIO *out);
221
222 /* 
223  * ðÏÉÓË ÍÉÎÉÍÁÌØÎÏÇÏ É ÍÁËÓÉÍÁÌØÎÏÇÏ ËÌÀÞÅÊ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ
224  * ÐÒÅÆÉËÓÕ word. ÷ ÓÌÕÞÁÅ ÕÓÐÅÈÁ ×ÏÚ×ÒÁÝÁÅÔ 1 É ÚÁÐÏÌÎÅÎÎÙÅ ÓÔÒÕËÔÕÒÙ f É l,
225  * byfxt - 0 É "ÍÕÓÏÒ" × f É l. ÷ ÓÔÒÕËÔÕÒÁÈ f É l ÐÏÌÑ key É data
226  * îå ÄÏÌÖÎÙ ÉÚÍÅÎÑÔØÓÑ ÉÌÉ ÏÓ×ÏÂÏÖÄÁÔØÓÑ ÐÁÍÑÔØ.
227  */
228 int SFSRange(SFSTree *info, char *word, SFSDataIO *f, SFSDataIO *l); 
229
230 /*
231  * ëÏÐÉÒÕÅÔ ÄÅÒÅ×Ï × "ÐÌÏÓËÕÀ" ÐÁÍÑÔØ. "ðÌÏÓËÏÅ" ÄÅÒÅ×Ï Read Only.
232  */
233 void SFSMakePlain(SFSTree *info, void *pointer);
234
235 /*
236  * ëÏÎ×ÅÒÔÉÒÕÅÔ "ÐÌÏÓËÏÅ" ÄÅÒÅ×Ï × ÏÂÙÞÎÏÅ. 
237  */
238 void * SFSRevertPlain(SFSTree *info);
239
240 typedef struct SFSTreeDumpHeader {
241         u_int32_t               version;
242         u_int16_t               opaquesize;
243         u_int16_t               headersize;
244         u_int32_t               datasize;
245         u_int32_t               extrasize;
246         u_int64_t               totalen;
247         u_int64_t               nnodes;
248 } SFSTreeDumpHeader;
249
250 #define  SFSTDHSZ       MAXALIGN( sizeof(SFSTreeDumpHeader) )
251
252 /*
253  * óÏÚÄÁÅÔ dump ÄÅÒÅ×Á, ÎÅ ÔÒÅÂÕÅÔ ÂÏÌØÛÏÇÏ ÒÁÓÈÏÄÁ ÐÁÍÑÔÉ
254  */
255 void SFSWriteDump(SFSTree *info, char *filename, void *extradata, u_int32_t extrasize);
256
257 /*
258  * óÏÚÄÁÅÔ "ÏÂÙÞÎÏÅ" (ÎÅ ÐÌÏÓËÏÅ) ÄÅÒÅ×Ï ÉÚ ÄÁÍÐÁ, 
259  * ÎÅ ÔÒÅÂÕÅÔ ÂÏÌØÛÏÇÏ ÒÁÓÈÏÄÁ ÐÁÍÑÔÉ
260  * ïÂÎÕÌÑÅÔ info!
261  */
262 void SFSReadDump(SFSTree *info, char *filename, void **extradata, u_int32_t *extrasize);
263
264 /*
265  * éÎÉÃÉÁÌÉÚÉÒÕÅÔ "ÐÌÏÓËÏÅ" ÄÅÒÅ×Ï ÉÚ ÏÂÒÁÚÁ ÄÁÍÐÁ
266  * ïÂÎÕÌÑÅÔ info!
267  */
268 void SFSInitFromDump(SFSTree *info, void *pointer, u_int64_t size, void **extradata, u_int32_t *extrasize);
269
270
271 #endif
272