/* * Copyright (c) 2004 Teodor Sigaev * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. Neither the name of the author nor the names of any co-contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef __SFXSTR_H__ #define __SFXSTR_H__ #include /* * Каждый узел дерева может бытть обним из двух типов: * SFSNode->isskip = 1 - узел "путевой компресии". * Такой узел может иметь одного ребенка и/или * одно слово. * SFSNode->isskip = 0 - "ветвящийся узел" * * "ветвящийся" узел дерева храниться в памяти следующим образом: * ( SFSNHRDSZ байта ) SFSNode - заголовок узла * ( sizeof(SFSNodeData)*SFSNode->nchar байта) SFSNodeData[] - массив "символов" * ( sizeof(SFSNode*)*SFSNode->nchild байта ) *SFSNode[] - массив ссылок на дочерние узлы * ( SFSTree->datasize * (количество слов, заканчивающихся в этом узле) ) - * массив значений * * массив "символов" - упорядочен по символам (SFSNodeData->val), * порядок остальных массивов задается массивом "символов" * узел "путевой компресии" храниться в памяти следующим образом: * ( SFSNHRDSZ байта ) SFSNode - заголовок узла * sizeof(SFSNode*) байт - ссылка на ребенка (необязательное поле) * SFSTree->datasize байт - значение, если здесь заканчивается ключ * (необязательное поле) * SFSTree->nchar байт - "скомпрессированная" часть пути. */ /* структура, описывающая "символ" */ typedef struct { u_int32_t /* смещение от текущего "символа" до ссылки на дочерний узел в байтах */ child:10, unused:4, /* в любом "символов" isword + haschild > 0 */ /* заканчивается ли здесь слово */ isword:1, /* есть ли дочерний узел */ haschild:1, /* смещение от SFSNode->dataptr до значения в единицах SFSTree->datasize */ data:8, /* Собственно символ */ val:8; } SFSNodeData; /* Заголовок узла дерева */ typedef struct SFSNode { u_int32_t /* тип узла */ isskip:1, /* заканчивается ли ключ в этом узле (только для узла "путевой компресии, для "ветвящегося" - неиспользуется) */ isword:1, /* есть ли ребенок этого узла (только для узла "путевой компресии, для "ветвящегося" - неиспользуется) */ haschild:1, unused:1, /* "путевой": смещение в байтах от начала узла до начала "скомпрессированной" части пути */ /* "ветвящийся": смещение в байтах от начала узла до начала массива значений */ dataptr:12, /* "путевой": неиспользуется */ /* "ветвящийся": кол-во дочерних узлов */ nchild:8, /* "путевой": кол-во "скомпрессованных" узлов */ /* "ветвящийся": кол-во "символов" */ nchar:8; SFSNodeData data[1]; } SFSNode; #define SFSNHRDSZ (sizeof(u_int32_t)) /* структура для обхода дерева итератором */ typedef struct SFSNodeStack { /* указатель на узел */ SFSNode *node; /* указатель на "символ" узла */ SFSNodeData *data; u_int32_t /* флаг проверки ключа */ checkedval:1, /* флаг проверки дочернего узла */ checkedchild:1, /* "глубина" узла */ level:30; struct SFSNodeStack *next; } SFSNodeStack; typedef struct { /* Статистические данные */ u_int64_t totalen; /* общее кол-во маллоцированной памяти */ u_int64_t nnodes; /* общее кол-во узлов дерева */ char plainmemory; /* true если дерево в плоской памяти */ u_int32_t datasize; /* размер значения (кратен sizeof(u_int32_t))*/ SFSNode *node; /* корневой узел дерева */ /* iterator */ SFSNodeStack *stack; /* стек обхода дерева */ char *buf; /* буфер ключа */ int tlen; /* его длина */ /* addon for prefix iterator */ int hasword; /* есть ли ключ, равное префиксу (служебное поле) */ void *wdata; /* указатель на значение ключа, равного префиксу (служебное поле) */ } SFSTree; /* структура ввода - вывода записей */ typedef struct { /* ключ, должен заканчтиваться символом '\0' */ char *key; /* длина ключа. При вводе должно содержать длину ключа или 0. При выводе всегда содержит длину ключа */ int keylen; /* указатель на значение */ void *data; } SFSDataIO; /* * Корректность функционирования контролируется assert'ом, * в том числе и контроль за malloc/realloc * Все ф-ции рассчитаны на ключи, заканчивающимися символом '\0' */ /* * ф-ции инициализации, datasize - размер в байтах * значения, привязанной к ключам. * SFSInit_c предполагает, что значения отсутствуют. * Размер структуры должен быть равен кратен sizeof(u_int32_t) */ SFSTree* SFSInit_dp(SFSTree *info, u_int32_t datasize, SFSDataIO *in); SFSTree* SFSInit_c(SFSTree *info, char **in); /* * Освобождение памяти, занятой деревом. * Если указана freefunc, то она вызывается для * каждого значения , привязанного к ключам */ void SFSFree(SFSTree *info, void (*freefunc)(void*)); /* * Добавление пары ключ-значение */ void SFSAdd(SFSTree *info, SFSDataIO *in); /* * Поиск значения по ключу, в случае успеха возвращает * указатель на значение, иначе - NULL */ void* SFSFindData(SFSTree *info, char *word, int len /* optional */ ); typedef struct SFSTreePosition { SFSNode **nodeptr; SFSNode *node; int level; } SFSTreePosition; void* SFSFindDataOrSave(SFSTree *info, SFSDataIO *in, SFSTreePosition *position); void* SFSFindDataFromSavedOrSave(SFSTree *info, SFSDataIO *in, SFSTreePosition *position); void SFSAddSaved(SFSTree *info, SFSDataIO *in, SFSTreePosition *position); /* * Инициализация итератора в начало дерева */ void SFSIteratorStart(SFSTree *info); /* * Инициализация итератора к ключу, больше или равному * word */ void SFSPrefixIteratorStart(SFSTree *info, char *word); /* * Обход итератора, в случае успеха возвращает 1 и заполненную * структуру SFSDataIO *out, иначе 0 и непредсказуемо заполненную * структуру SFSDataIO *out. В структуре out поля key и data * НЕ должны изменяться или освобождаться память. * Ф-ция прекращает обход: * 1) инициализация SFSIteratorStart: выбраны все ключи * 2) -/- SFSPrefixIteratorStart: выбраны все ключи с заданным префиксом. * Ключи выдаются в лексикографическом порядке, соответствующим * ASCI кодировке. */ int SFSIterate(SFSTree *info, SFSDataIO *out); /* * Поиск минимального и максимального ключей, соответствующих * префиксу word. В случае успеха возвращает 1 и заполненные структуры f и l, * byfxt - 0 и "мусор" в f и l. В структурах f и l поля key и data * НЕ должны изменяться или освобождаться память. */ int SFSRange(SFSTree *info, char *word, SFSDataIO *f, SFSDataIO *l); /* * Копирует дерево в "плоскую" память. "Плоское" дерево Read Only. */ void SFSMakePlain(SFSTree *info, void *pointer); /* * Конвертирует "плоское" дерево в обычное. */ void * SFSRevertPlain(SFSTree *info); typedef struct SFSTreeDumpHeader { u_int32_t version; u_int16_t opaquesize; u_int16_t headersize; u_int32_t datasize; u_int32_t extrasize; u_int64_t totalen; u_int64_t nnodes; } SFSTreeDumpHeader; #define SFSTDHSZ MAXALIGN( sizeof(SFSTreeDumpHeader) ) /* * Создает dump дерева, не требует большого расхода памяти */ void SFSWriteDump(SFSTree *info, char *filename, void *extradata, u_int32_t extrasize); /* * Создает "обычное" (не плоское) дерево из дампа, * не требует большого расхода памяти * Обнуляет info! */ void SFSReadDump(SFSTree *info, char *filename, void **extradata, u_int32_t *extrasize); /* * Инициализирует "плоское" дерево из образа дампа * Обнуляет info! */ void SFSInitFromDump(SFSTree *info, void *pointer, u_int64_t size, void **extradata, u_int32_t *extrasize); #endif