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_int32_t       totalen; /* ÏÂÝÅÅ ËÏÌ-×Ï ÍÁÌÌÏÃÉÒÏ×ÁÎÎÏÊ ÐÁÍÑÔÉ */
 128         u_int32_t       nnodes;  /* ÏÂÝÅÅ ËÏÌ-×Ï ÕÚÌÏ× ÄÅÒÅ×Á */
 129
 130         u_int32_t       datasize; /* ÒÁÚÍÅÒ ÚÎÁÞÅÎÉÑ (ËÒÁÔÅÎ sizeof(u_int32_t))*/
 131         SFSNode         *node;    /* ËÏÒÎÅ×ÏÊ ÕÚÅÌ ÄÅÒÅ×Á */
 132
 133         /* iterator */
 134         SFSNodeStack    *stack;  /* ÓÔÅË ÏÂÈÏÄÁ ÄÅÒÅ×Á */
 135         char            *buf;    /* ÂÕÆÅÒ ËÌÀÞÁ */
 136         int             tlen;    /* ÅÇÏ ÄÌÉÎÁ */
 137
 138         /* addon for prefix iterator */
 139         int             hasword; /* ÅÓÔØ ÌÉ ËÌÀÞ, ÒÁ×ÎÏÅ ÐÒÅÆÉËÓÕ (ÓÌÕÖÅÂÎÏÅ ÐÏÌÅ) */
 140         void            *wdata;  /* ÕËÁÚÁÔÅÌØ ÎÁ ÚÎÁÞÅÎÉÅ ËÌÀÞÁ, ÒÁ×ÎÏÇÏ ÐÒÅÆÉËÓÕ (ÓÌÕÖÅÂÎÏÅ ÐÏÌÅ) */
 141 }       SFSTree;
 142
 143 /* ÓÔÒÕËÔÕÒÁ ××ÏÄÁ - ×Ù×ÏÄÁ ÚÁÐÉÓÅÊ */
 144 typedef struct {
 145         /* ËÌÀÞ, ÄÏÌÖÅÎ ÚÁËÁÎÞÔÉ×ÁÔØÓÑ ÓÉÍ×ÏÌÏÍ '\0' */
 146         char    *key;
 147         /* ÄÌÉÎÁ ËÌÀÞÁ.  ðÒÉ ××ÏÄÅ ÄÏÌÖÎÏ ÓÏÄÅÒÖÁÔØ ÄÌÉÎÕ ËÌÀÞÁ ÉÌÉ 0.
 148            ðÒÉ ×Ù×ÏÄÅ ×ÓÅÇÄÁ ÓÏÄÅÒÖÉÔ ÄÌÉÎÕ ËÌÀÞÁ */
 149         int     keylen;
 150         /* ÕËÁÚÁÔÅÌØ ÎÁ ÚÎÁÞÅÎÉÅ */
 151         void    *data;
 152 } SFSDataIO;
 153
 154 /*
 155  *  ëÏÒÒÅËÔÎÏÓÔØ ÆÕÎËÃÉÏÎÉÒÏ×ÁÎÉÑ ËÏÎÔÒÏÌÉÒÕÅÔÓÑ assert'ÏÍ,
 156  *  × ÔÏÍ ÞÉÓÌÅ É ËÏÎÔÒÏÌØ ÚÁ malloc/realloc
 157  *  ÷ÓÅ Æ-ÃÉÉ ÒÁÓÓÞÉÔÁÎÙ ÎÁ ËÌÀÞÉ, ÚÁËÁÎÞÉ×ÁÀÝÉÍÉÓÑ ÓÉÍ×ÏÌÏÍ '\0'
 158  */
 159
 160 /*
 161  * Æ-ÃÉÉ ÉÎÉÃÉÁÌÉÚÁÃÉÉ, datasize - ÒÁÚÍÅÒ × ÂÁÊÔÁÈ
 162  * ÚÎÁÞÅÎÉÑ, ÐÒÉ×ÑÚÁÎÎÏÊ Ë ËÌÀÞÁÍ.
 163  * SFSInit_c ÐÒÅÄÐÏÌÁÇÁÅÔ, ÞÔÏ ÚÎÁÞÅÎÉÑ ÏÔÓÕÔÓÔ×ÕÀÔ.
 164  * òÁÚÍÅÒ ÓÔÒÕËÔÕÒÙ ÄÏÌÖÅÎ ÂÙÔØ ÒÁ×ÅÎ ËÒÁÔÅÎ sizeof(u_int32_t)
 165  */
 166 SFSTree* SFSInit_dp(SFSTree *info, u_int32_t datasize, SFSDataIO *in);
 167 SFSTree* SFSInit_c(SFSTree *info, char **in);
 168
 169 /*
 170  * ïÓ×ÏÂÏÖÄÅÎÉÅ ÐÁÍÑÔÉ, ÚÁÎÑÔÏÊ ÄÅÒÅ×ÏÍ.
 171  * åÓÌÉ ÕËÁÚÁÎÁ freefunc, ÔÏ ÏÎÁ ×ÙÚÙ×ÁÅÔÓÑ ÄÌÑ
 172  * ËÁÖÄÏÇÏ ÚÎÁÞÅÎÉÑ , ÐÒÉ×ÑÚÁÎÎÏÇÏ Ë ËÌÀÞÁÍ
 173  */
 174 void SFSFree(SFSTree *info, void (*freefunc)(void*));
 175
 176 /*
 177  * äÏÂÁ×ÌÅÎÉÅ ÐÁÒÙ ËÌÀÞ-ÚÎÁÞÅÎÉÅ
 178  */
 179 void SFSAdd(SFSTree *info, SFSDataIO *in);
 180
 181 /*
 182  * ðÏÉÓË ÚÎÁÞÅÎÉÑ ÐÏ ËÌÀÞÕ, × ÓÌÕÞÁÅ ÕÓÐÅÈÁ ×ÏÚ×ÒÁÝÁÅÔ
 183  * ÕËÁÚÁÔÅÌØ ÎÁ ÚÎÁÞÅÎÉÅ, ÉÎÁÞÅ - NULL
 184  */
 185 void* SFSFindData(SFSTree *info, char *word);
 186
 187 /*
 188  * éÎÉÃÉÁÌÉÚÁÃÉÑ ÉÔÅÒÁÔÏÒÁ × ÎÁÞÁÌÏ ÄÅÒÅ×Á
 189  */
 190 void SFSIteratorStart(SFSTree *info);
 191
 192 /*
 193  * éÎÉÃÉÁÌÉÚÁÃÉÑ ÉÔÅÒÁÔÏÒÁ Ë ËÌÀÞÕ, ÂÏÌØÛÅ ÉÌÉ ÒÁ×ÎÏÍÕ
 194  * word
 195  */
 196 void SFSPrefixIteratorStart(SFSTree *info, char *word);
 197
 198 /*
 199  * ïÂÈÏÄ ÉÔÅÒÁÔÏÒÁ, × ÓÌÕÞÁÅ ÕÓÐÅÈÁ ×ÏÚ×ÒÁÝÁÅÔ 1 É ÚÁÐÏÌÎÅÎÎÕÀ
 200  * ÓÔÒÕËÔÕÒÕ SFSDataIO *out, ÉÎÁÞÅ 0 É ÎÅÐÒÅÄÓËÁÚÕÅÍÏ ÚÁÐÏÌÎÅÎÎÕÀ
 201  * ÓÔÒÕËÔÕÒÕ SFSDataIO *out. ÷ ÓÔÒÕËÔÕÒÅ out ÐÏÌÑ key É data
 202  * îå ÄÏÌÖÎÙ ÉÚÍÅÎÑÔØÓÑ ÉÌÉ ÏÓ×ÏÂÏÖÄÁÔØÓÑ ÐÁÍÑÔØ.
 203  * æ-ÃÉÑ ÐÒÅËÒÁÝÁÅÔ ÏÂÈÏÄ:
 204  *  1) ÉÎÉÃÉÁÌÉÚÁÃÉÑ SFSIteratorStart: ×ÙÂÒÁÎÙ ×ÓÅ ËÌÀÞÉ
 205  *  2) -/- SFSPrefixIteratorStart: ×ÙÂÒÁÎÙ ×ÓÅ ËÌÀÞÉ Ó ÚÁÄÁÎÎÙÍ ÐÒÅÆÉËÓÏÍ.
 206  * ëÌÀÞÉ ×ÙÄÁÀÔÓÑ × ÌÅËÓÉËÏÇÒÁÆÉÞÅÓËÏÍ ÐÏÒÑÄËÅ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÍ
 207  * ASCI ËÏÄÉÒÏ×ËÅ.
 208  */
 209 int SFSIterate(SFSTree *info, SFSDataIO *out);
 210
 211 /*
 212  * ðÏÉÓË ÍÉÎÉÍÁÌØÎÏÇÏ É ÍÁËÓÉÍÁÌØÎÏÇÏ ËÌÀÞÅÊ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ
 213  * ÐÒÅÆÉËÓÕ word. ÷ ÓÌÕÞÁÅ ÕÓÐÅÈÁ ×ÏÚ×ÒÁÝÁÅÔ 1 É ÚÁÐÏÌÎÅÎÎÙÅ ÓÔÒÕËÔÕÒÙ f É l,
 214  * byfxt - 0 É "ÍÕÓÏÒ" × f É l. ÷ ÓÔÒÕËÔÕÒÁÈ f É l ÐÏÌÑ key É data
 215  * îå ÄÏÌÖÎÙ ÉÚÍÅÎÑÔØÓÑ ÉÌÉ ÏÓ×ÏÂÏÖÄÁÔØÓÑ ÐÁÍÑÔØ.
 216  */
 217 int SFSRange(SFSTree *info, char *word, SFSDataIO *f, SFSDataIO *l);
 218
 219 #endif
 220