Use flock call instead of open's flags O_EXLOCK/O_SHLOCK
[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);
187
188 /*
189  * éÎÉÃÉÁÌÉÚÁÃÉÑ ÉÔÅÒÁÔÏÒÁ × ÎÁÞÁÌÏ ÄÅÒÅ×Á 
190  */
191 void SFSIteratorStart(SFSTree *info);
192
193 /*
194  * éÎÉÃÉÁÌÉÚÁÃÉÑ ÉÔÅÒÁÔÏÒÁ Ë ËÌÀÞÕ, ÂÏÌØÛÅ ÉÌÉ ÒÁ×ÎÏÍÕ
195  * word 
196  */
197 void SFSPrefixIteratorStart(SFSTree *info, char *word);
198
199 /* 
200  * ïÂÈÏÄ ÉÔÅÒÁÔÏÒÁ, × ÓÌÕÞÁÅ ÕÓÐÅÈÁ ×ÏÚ×ÒÁÝÁÅÔ 1 É ÚÁÐÏÌÎÅÎÎÕÀ
201  * ÓÔÒÕËÔÕÒÕ SFSDataIO *out, ÉÎÁÞÅ 0 É ÎÅÐÒÅÄÓËÁÚÕÅÍÏ ÚÁÐÏÌÎÅÎÎÕÀ
202  * ÓÔÒÕËÔÕÒÕ SFSDataIO *out. ÷ ÓÔÒÕËÔÕÒÅ out ÐÏÌÑ key É data
203  * îå ÄÏÌÖÎÙ ÉÚÍÅÎÑÔØÓÑ ÉÌÉ ÏÓ×ÏÂÏÖÄÁÔØÓÑ ÐÁÍÑÔØ.
204  * æ-ÃÉÑ ÐÒÅËÒÁÝÁÅÔ ÏÂÈÏÄ:
205  *  1) ÉÎÉÃÉÁÌÉÚÁÃÉÑ SFSIteratorStart: ×ÙÂÒÁÎÙ ×ÓÅ ËÌÀÞÉ
206  *  2) -/- SFSPrefixIteratorStart: ×ÙÂÒÁÎÙ ×ÓÅ ËÌÀÞÉ Ó ÚÁÄÁÎÎÙÍ ÐÒÅÆÉËÓÏÍ.
207  * ëÌÀÞÉ ×ÙÄÁÀÔÓÑ × ÌÅËÓÉËÏÇÒÁÆÉÞÅÓËÏÍ ÐÏÒÑÄËÅ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÍ
208  * ASCI ËÏÄÉÒÏ×ËÅ. 
209  */ 
210 int SFSIterate(SFSTree *info, SFSDataIO *out);
211
212 /* 
213  * ðÏÉÓË ÍÉÎÉÍÁÌØÎÏÇÏ É ÍÁËÓÉÍÁÌØÎÏÇÏ ËÌÀÞÅÊ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ
214  * ÐÒÅÆÉËÓÕ word. ÷ ÓÌÕÞÁÅ ÕÓÐÅÈÁ ×ÏÚ×ÒÁÝÁÅÔ 1 É ÚÁÐÏÌÎÅÎÎÙÅ ÓÔÒÕËÔÕÒÙ f É l,
215  * byfxt - 0 É "ÍÕÓÏÒ" × f É l. ÷ ÓÔÒÕËÔÕÒÁÈ f É l ÐÏÌÑ key É data
216  * îå ÄÏÌÖÎÙ ÉÚÍÅÎÑÔØÓÑ ÉÌÉ ÏÓ×ÏÂÏÖÄÁÔØÓÑ ÐÁÍÑÔØ.
217  */
218 int SFSRange(SFSTree *info, char *word, SFSDataIO *f, SFSDataIO *l); 
219
220 /*
221  * ëÏÐÉÒÕÅÔ ÄÅÒÅ×Ï × "ÐÌÏÓËÕÀ" ÐÁÍÑÔØ. "ðÌÏÓËÏÅ" ÄÅÒÅ×Ï Read Only.
222  */
223 void SFSMakePlain(SFSTree *info, void *pointer);
224
225 /*
226  * ëÏÎ×ÅÒÔÉÒÕÅÔ "ÐÌÏÓËÏÅ" ÄÅÒÅ×Ï × ÏÂÙÞÎÏÅ. 
227  */
228 void * SFSRevertPlain(SFSTree *info);
229
230 typedef struct SFSTreeDumpHeader {
231         u_int32_t               version;
232         u_int32_t               opaquesize;
233         u_int32_t               headersize;
234         u_int32_t               datasize;
235         u_int64_t               totalen;
236         u_int64_t               nnodes;
237 } SFSTreeDumpHeader;
238
239 #define  SFSTDHSZ       ( MAXALIGN(sizeof(SFSTreeDumpHeader))  )
240
241 /*
242  * óÏÚÄÁÅÔ dump ÄÅÒÅ×Á, ÎÅ ÔÒÅÂÕÅÔ ÂÏÌØÛÏÇÏ ÒÁÓÈÏÄÁ ÐÁÍÑÔÉ
243  */
244 void SFSWriteDump(SFSTree *info, char *filename);
245
246 /*
247  * óÏÚÄÁÅÔ "ÏÂÙÞÎÏÅ" (ÎÅ ÐÌÏÓËÏÅ) ÄÅÒÅ×Ï ÉÚ ÄÁÍÐÁ, 
248  * ÎÅ ÔÒÅÂÕÅÔ ÂÏÌØÛÏÇÏ ÒÁÓÈÏÄÁ ÐÁÍÑÔÉ
249  * ïÂÎÕÌÑÅÔ info!
250  */
251 void SFSReadDump(SFSTree *info, char *filename);
252
253 /*
254  * éÎÉÃÉÁÌÉÚÉÒÕÅÔ "ÐÌÏÓËÏÅ" ÄÅÒÅ×Ï ÉÚ ÏÂÒÁÚÁ ÄÁÍÐÁ
255  * ïÂÎÕÌÑÅÔ info!
256  */
257 void SFSInitFromDump(SFSTree *info, void *pointer, u_int64_t size);
258
259
260 #endif
261