キーワード検索

中国語キーワード検索(敏感語フィルタ)
背景
最近では、ある文字にキーワード(敏感字)が現れるかどうかを調べるのに極めて短い時間が必要になります.ネット上でいくつかの資料を探して、javaが書いた2つの配列のAC木を使って、毎秒27 Mbの速度に達します.cで書かれたacツリーも毎秒30 Mしかありません.
パフォーマンス
マルチフォークc言語で書かれた、マシン:Intel(R)Xeon(R)CPU E 5-2680 v [email protected] GHz検索レート約:111000(bytes/ms)
インプリメンテーション原理
1.マルチマッチングアルゴリズムの検索については、主列について遡及比較を必要としないため、acアルゴリズムに類似した考えが好ましいと考えられる.辞書のようなキーワードが多い場合(abc,abcdef,abcdffのように接頭辞が同じように多い場合)の効率が著しく向上することを前提としている.
しかし、中国語の敏感語では、接頭辞の繰り返し率が低すぎて、ACオートマチックを使うと、ほとんどの場合、根本的なジャンプは遡及アルゴリズムと変わらず、かえって比較が増加し(実際のプログラムの比較は主に異なるメモリへのアクセスであり、数回のmiss cacheが最も消費される)、性能はかえって低下した.
2.ここで採用する方法は、マルチフォークツリーを直接使用し、1段目は24ビット(すなわち、2^24個のポインタ空間=2^27=128 Mのメモリを割り当てる)、2段目は8ビット、3段目は前の2段を除いた残りのバイトを直接保存する.
注意:ここではbitmapアルゴリズムを採用しています.主にメモリスペースを節約するためです.例えば、キーワード「私たちの」、「私」を追加した場合、「私」は3バイトしか占めていません(つまり、第1レベルのインデックスで十分です).bitmapに参加する目的の1つは、検索時にここまで一致していれば(つまり、主列に「私」が現れた)、2つは削除時、その後ユーザーが突然キーワード「私」を削除しようとしたことを示し、bitmapというタグビットを削除するだけで、「私たちの」というキーワードの検索に影響しません.
不足

ここではメモリプールの方法を採用していますが、速度も10%程度しか上げられません.メモリプールのメソッドはざらざらしていますが、ここではデモのみを行います.メモリプールを書き換えるか使いたくない場合は、FindKeyword.cファイルのmpool_をalloc関数はmallocで置き換えればいいです.

ソースコード
直接実行して効果を見たい場合は、リソースgit cloneをダウンロードできます.https://gitee.com/ben_wsx/FindKeyword.git . (http://download.csdn.net/download/w_sx12553/10135616 ここの資源は古くて、気持ち悪いCSDNは削除することができません)あるいは下のファイルを複製します
主なコードは次のとおりです.
FindKeyword.c

//
//   ：           ，2^24       ,       
//
//
//                                          ben
//                                          2017.11.23
//
//

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include   
#include   
#include   
#include  

#include "getTime.h"
#include "mpool.h"


#define _TEST_  //      

#ifdef _TEST_
char* g_findKeyword = NULL; //       
int   g_findKeyword_Len = 0;
#endif


#define GetFirstIndex(i) (((i)>>8) &(0xffffff))
#define GetSecondIndex(i) ((i)&0xff)

mpool* g_mp = NULL;

#define _256_BRANCH 256
#define BigBranchCnts (1<<24)

#define _FOUND_TAG_     (1)     //        

#define  FIRST_LEFTBYTESSET_CNTS    (16 - 1)        //         


#define KEYWORD_MAX_LEN 64
//      (              )     
struct LeftBytesSet {
    uint32_t Cnts;      //        
    uint32_t totalCnts;
    char keySet[1][KEYWORD_MAX_LEN];                //   :       ，             
};


struct LeftBytesSet*
getLeftBytesSet(mpool* mp, int size)
{
    struct LeftBytesSet* pLeftBytesSet =
        (struct LeftBytesSet*)mpool_alloc(mp, sizeof(struct LeftBytesSet) + (KEYWORD_MAX_LEN * (size-1)));

    pLeftBytesSet->totalCnts = size;
    pLeftBytesSet->Cnts = 0;

    return pLeftBytesSet;
}


//     Node
struct _2_Node {
    struct LeftBytesSet* child[_256_BRANCH];
    int findTag[_256_BRANCH];
};


//     Node
struct _1_Node {
    struct _2_Node* child[BigBranchCnts];
};


//        
struct TreeInfo {
    mpool* mPool;
    struct _1_Node* root;   //      
    char bitmapMemBlock[2*1024*1024];
};


//
//   ：            （   c++   strcpy_s   ）
//
void myStrcpy_s(char* dst, char* src, int len)
{
    int i;
    for (i = 0; i < len; ++i) {
        dst[i] = src[i];
        }

    dst[len] = '\0';
}

//   ：       
int myStrlen(char* str)
{
    int len = 0;
    while (*str) {
        if ('\r' == *str || '
' == *str)
            break;

        len++;
        str++;
        }

    return len;
}


//
//   :          
//
//    :     0:   ，1:    , -1:   。
//
int isFileOrDir(char* path)     
{
    if (0 == access(path, 0))     
    {
        struct stat *buf;

        buf = (struct stat *) malloc(sizeof(struct stat));     
        memset(buf, 0, sizeof(struct stat));

        stat(path, buf);

        if (S_ISDIR(buf->st_mode))
        {
            free(buf);
            buf = NULL;
            return 1;     
        }     
        else         
        {     
            free(buf);
            buf = NULL;     
            return -1;
        }     
    }
    else    
    {     
        return 0;
    }
}


//
//   :        (      s1   ，  :        strcmp )
//
inline int __attribute__((always_inline))
myStrcmp(char* s1, char* s2)
{
    while (*s1) {
        if (*s1 > *s2)
            return 1;

        if (*s1 < *s2)
            return -1;

        ++s1,++s2;      
        }

    return 0;
}


//
//   :    utf-8     ，   UTF-8     (   )     
//
//   : UTF-8       
// http://note.youdao.com/noteshare?id=85958bf43d761398962af780b12392d6&sub=F79830034DF14F138B69146D19EB315B
// 
inline int32_t __attribute__((always_inline))
get_utf_8_word_length(char tmp)
{
    int len;

    //          tmp           1110****   ，
    //               3。
    //       ，         3   。
    if (!( (tmp & 0xf0) ^ 0xe0))
        return 3;


    if (tmp > 0)    //             0，     ASCII
        return 1;


    len = 0;
    do {
        tmp <<= 1;
        len++;
    } while (tmp < 0);

    return len;
}


//  ---------------------------------
//  BITAMP 

inline void __attribute__((always_inline))
bitmap_set(char* bitmapMemBlock, int pos)
{
    bitmapMemBlock[pos>>3] |= (1 << (pos&7));
}

inline void __attribute__((always_inline))
bitmap_unset(char* bitmapMemBlock, int pos)
{
    bitmapMemBlock[pos>>3] &= ~(1 << (pos&7));
}


inline bool __attribute__((always_inline))
bitmap_get(char* bitmapMemBlock, int pos)
{
    return bitmapMemBlock[pos>>3] & (1 << (pos&7));
}
// -------------------------------------------


//
//   ：     
//
inline void __attribute__((always_inline))
insertKeyword(struct TreeInfo* pTreeInfo, char* keyword, int keywordLen)
{
    const int leftLen = 4;                  //                    

    mpool* mp;
    struct _1_Node* root;
    struct _2_Node* p_2Node;
    struct LeftBytesSet* pLeftbytesSet, *pLeftbytesSet_2;

    uint32_t index;
    int Cnts;
    int i, j;

    root = pTreeInfo->root;
    mp = pTreeInfo->mPool;

    //         (   3  ，  3  )          
    if (keywordLen >= 3) {
        index = (*((uint32_t *)keyword)) & 0xffffff;
        }
    else if (2 == keywordLen) {
        //index = keyword[0] | (keyword[1]<<8);
        index = (*((uint32_t *)keyword)) & 0xffff;
        }
    else if (1 == keywordLen) {
        index = keyword[0]&0xff;
        }
    else
        return;

    if ((keywordLen - 3) <= 0) {
        bitmap_set(pTreeInfo->bitmapMemBlock, index);
        return;
        }

    p_2Node = root->child[index];
    if (NULL == p_2Node) {
        p_2Node =  root->child[index] = (struct _2_Node*)mpool_alloc(mp, sizeof(struct _2_Node));
        }

    //         
    index = keyword[3]&0xff;
    pLeftbytesSet = p_2Node->child[index];


    if ((keywordLen - 4) <= 0) {
        p_2Node->findTag[index] = _FOUND_TAG_;
        return;     
        }

    if (NULL == pLeftbytesSet) {
        pLeftbytesSet =  p_2Node->child[index] = 
            getLeftBytesSet(mp, FIRST_LEFTBYTESSET_CNTS);       
        }
    else if(0 == pLeftbytesSet->totalCnts - pLeftbytesSet->Cnts) {
        //          ，     (    c++ Vector      )
        pLeftbytesSet_2 = 
            getLeftBytesSet(mp, pLeftbytesSet->totalCnts*2+1);

        //                 
        for (i = 0; i < pLeftbytesSet->totalCnts; ++i) {
            strcpy(pLeftbytesSet_2->keySet[i], pLeftbytesSet->keySet[i]);
            pLeftbytesSet_2->Cnts ++;   
            }

        pLeftbytesSet = p_2Node->child[index] = pLeftbytesSet_2;
        //printf("    ： %d 
", pLeftbytesSet->totalCnts);      
        }


    //                  ,           (         )
    //
    int beyondResult;   //          
    Cnts = pLeftbytesSet->Cnts;
    for (i = 0; i < Cnts; ++i) {
        beyondResult = myStrcmp(keyword+leftLen, pLeftbytesSet->keySet[i]);

        if (0 > beyondResult) {
            break;
            }
        }

    for (j = Cnts; j > i; j--) {
        strcpy( pLeftbytesSet->keySet[j],  pLeftbytesSet->keySet[j-1]);
        }
    myStrcpy_s(pLeftbytesSet->keySet[i], keyword+leftLen, keywordLen-leftLen);

    pLeftbytesSet->Cnts++;
//  printf("cpystr= %s,    pLeftbytesSet->Cnts = %d
 ", keyword+leftLen, pLeftbytesSet->Cnts);
}


//
//   ：     
// 
//   :             "   " " "     ，        " "        。
//
//
void deleteKeyword(struct TreeInfo* pTreeInfo, char* keyword, int keywordLen)
{
    int cnts;
    int high, low, midle;           //      
    struct _2_Node* p_2Node;
    struct LeftBytesSet* pLeftbytesSet;
    uint32_t index;

    if (keywordLen >= 3) {
        index =  (*((uint32_t *)keyword)) & 0xffffff;
        }
    else if (2 == keywordLen) {
        index =  (*((uint32_t *)keyword)) & 0xffff;
        }
    else if (1 == keywordLen) {
        index = keyword[0]&0xff;
        }
    else
        return;


    if ((keywordLen - 3) <= 0) {
        bitmap_unset(pTreeInfo->bitmapMemBlock, index);
        return;
        }

    p_2Node = pTreeInfo->root->child[index];
    if (NULL == p_2Node) 
        return;


    //           
    index = keyword[3] & 0xff;
    if ((keywordLen - 4) <= 0) {
        p_2Node->findTag[index] = 0;
        return;
        }

    pLeftbytesSet = p_2Node->child[index];
    if (NULL == pLeftbytesSet)
        return;


    //     3 
    cnts = pLeftbytesSet->Cnts;
    high = cnts - 1;//            
    low = 0;
    midle = cnts/2; 

    int beyondResult;
    while(high >= low) {
            midle = (high + low)/2;

            beyondResult = myStrcmp(pLeftbytesSet->keySet[midle], keyword+4);

            if(beyondResult > 0)
               high = midle - 1;
            else if(beyondResult < 0)
               low = midle + 1;
            else if(0 == beyondResult) { //    。。。
                strcpy(pLeftbytesSet->keySet[midle], pLeftbytesSet->keySet[cnts-1]);
                pLeftbytesSet->Cnts--;
                return;
                }
        }
}


//
//   ：      
//
inline bool __attribute__((always_inline))
findKeyword(struct TreeInfo* pTreeInfo, char* str)
{
    int cnts, high, low, midle; //      
    int i;

    struct _1_Node* root;
    struct _2_Node* p_2Node;
    struct LeftBytesSet* pLeftbytesSet;
    uint32_t index;

    char tempCh;

    int beyondResult;   //     

    int first_utf_8_word_len;   //      ，       (      )

    root = pTreeInfo->root;

    while (*str) {

#if 0   //
        //                      
        first_utf_8_word_len = get_utf_8_word_length(*str);

#else   //           get_utf_8_word_length()   ，              
        //
        //
        //                      
        do {
                //                        1110****   ，
                //                  3。
                //       ?
                //         3   ，         do-while(0)  ，        。
                if (!((*str & 0xf0) ^ 0xe0)) {
                    first_utf_8_word_len = 3;
                    break;
                    }               

                if (*str > 0) { //             0，     ASCII
                    first_utf_8_word_len = 1;
                    break;
                    }

                first_utf_8_word_len = 0;
                tempCh = *str;
                do {
                    tempCh <<= 1;
                    first_utf_8_word_len++;
                } while (tempCh < 0);               
            } while(0);
#endif

        //         ?  
        //    str[1]=='\0'            。    str[2]    0,   3            。
        if (str[1])
            index =  (*((uint32_t *)str)) & 0xffffff;
        else 
            index =  (*((uint32_t *)str)) & 0xff;

        p_2Node = root->child[index];

        if ((pTreeInfo->bitmapMemBlock[index>>3] & (1 << (index&7)))) {
#ifdef _TEST_
            g_findKeyword = str;
            g_findKeyword_Len = (str[1]) ? 3 :2;
#endif
            return true;
            }

        if (NULL == p_2Node)
            goto mytag;


        //           
        index = str[3] & 0xff;  
        if (_FOUND_TAG_ == p_2Node->findTag[index]) {
#ifdef _TEST_
            g_findKeyword = str;
            g_findKeyword_Len = 4;
#endif      
            return true;
            }

        pLeftbytesSet = p_2Node->child[index];
        if (NULL == pLeftbytesSet)
            goto mytag;

        //     3 
        cnts = pLeftbytesSet->Cnts;

    //        ，     (      )
    if (cnts <= 7) {
        for (i = 0; i < cnts; ++i) {
            if(0 ==myStrcmp(pLeftbytesSet->keySet[i],  str+4)) { //    。。。
#ifdef _TEST_
                    g_findKeyword = str;
                    g_findKeyword_Len = 4 + strlen(pLeftbytesSet->keySet[i]);
#endif
                    return true;
                }
            }
        }
    else { //           
        high = cnts - 1;//            
        low = 0;
        midle = cnts/2;
        while(high >= low) {
                midle = (high + low)/2;

                beyondResult = myStrcmp(pLeftbytesSet->keySet[midle],  str+4);

                if(beyondResult > 0)
                   high = midle - 1;
                else if(beyondResult < 0)
                   low = midle + 1;
                else if(0 == beyondResult) { //    。。。
#ifdef _TEST_
                    g_findKeyword = str;
                    g_findKeyword_Len = 4 + strlen(pLeftbytesSet->keySet[midle]);
#endif
                    return true;
                    }
            } 
        }


mytag:
        str += first_utf_8_word_len;    //        ，       (   )   
        }

    return false;
}


struct TreeInfo* InitTreeInfo()
{   
    struct TreeInfo* pTreeInfo = (struct TreeInfo*)malloc(sizeof(struct TreeInfo));

    pTreeInfo->mPool = mpool_init(1024*1024*128, 8);            //       
    pTreeInfo->root =  mpool_alloc(pTreeInfo->mPool, sizeof(struct _1_Node));
    memset(pTreeInfo->root, 0, sizeof(struct _1_Node));

    memset(pTreeInfo->bitmapMemBlock, 0, 2*1024*1024);

    return pTreeInfo;   
}


void deinitTreeInfo(struct TreeInfo* pTreeInfo)
{
    mpool_destroy(pTreeInfo->mPool);
}


//
//   :     
//
int testPerformance(int argc, char* argv[])
{
#define MAX_KEY_CNTS    256*1024                //         
#define MAX_KEY_LEN     64                      //         

    long long begTime, endTime, totalTime;
    struct ACAutoMation *mation;
    char (*StrLine)[MAX_KEY_LEN];           //          
    int key_cnts    = 0;                    //                          
    int lSize;                              //       
    char *text;                             //       
    int len;
    FILE *fTxt; 
    FILE *fDic;
    char ch;  
    int32_t findResult = 0;
    int i;

    char tmpFindKeyword[64] = {0};

    struct TreeInfo *pTreeInfo = InitTreeInfo();

    StrLine = (char(*)[MAX_KEY_LEN])malloc(MAX_KEY_LEN * MAX_KEY_CNTS);
    if (NULL == StrLine) {
        printf("      。。。 
");
        exit(1);
        }

    if(argc < 3) {
        printf("     :      ：  ./test text.txt dictionary.txt
");
        exit(1);
        }

    if ((-1 != isFileOrDir(argv[1])) || (-1 != isFileOrDir(argv[2]))) {
        printf("          ，       :        ：  ./test dictionary.txt  text.txt
");
        exit(1);
        }

    if((fTxt=fopen(argv[1], "r")) == NULL) {  
        printf("file cannot be opened
");   
        exit(1);
    }

    if((fDic=fopen(argv[2], "r")) == NULL) {  
        printf("file cannot be opened
");   
        exit(1);
    }

    fseek(fTxt, 3, SEEK_SET); //             BOM  
    fseek(fDic, 3, SEEK_SET); //             BOM  


    //    Key     
    while (!feof(fDic) && (key_cnts < MAX_KEY_CNTS)) { 
      fgets(StrLine[key_cnts], MAX_KEY_LEN, fDic);  //    

     // trim(StrLine[key_cnts]);            //       
      len = myStrlen(StrLine[key_cnts]);    

      //printf("len = %d
", len);

      if (0 != len) {
        ++key_cnts;  
        }
    } 
    fclose(fDic);


    printf("         ... 
");
    begTime = getSystemTime();
    for (i = 0; i < key_cnts; ++i) {
        len = myStrlen(StrLine[i]);
        insertKeyword(pTreeInfo, StrLine[i], len);  
        }
    endTime = getSystemTime();  
    printf("       ...     %lld (ms)
",  (endTime - begTime > 0) ? (endTime - begTime) : 1);


    // ----------------------------------------------------------------------
    begTime = getSystemTime();  
    //           
    fseek(fTxt, 0, SEEK_END);
    lSize = ftell(fTxt);
    text = (char*)malloc(lSize+1);
    fseek(fTxt, 0, SEEK_SET);   // rewind
    fread(text, sizeof(char), lSize, fTxt);
    text[lSize] = '\0';
    fclose(fTxt);

    findResult = findKeyword(pTreeInfo, text);
    endTime = getSystemTime();


    printf("------------------------

");

    if (findResult > 0) {
        myStrcpy_s(tmpFindKeyword, g_findKeyword, g_findKeyword_Len);

        printf("      =   (%s) 
", tmpFindKeyword);
        } 
    else {
        printf("      ！
");
    }

    totalTime = (endTime - begTime > 0) ? (endTime - begTime) : 1;
    printf("      : %d,        : %d ,     : %lld ms,     : %lld (bytes/ms) 
", 
                key_cnts, lSize, totalTime, (lSize)/(int)(totalTime));

    deinitTreeInfo(pTreeInfo);
    return 0;
}


//
//   :          
//
void test()
{
    struct TreeInfo *pTreeInfo = InitTreeInfo();
    char tmpFindKeyword[64] = {0};
    char* text = "kfk     fkfabca32bxa";

    //insertKeyword(pTreeInfo, "a", strlen("a"));
    insertKeyword(pTreeInfo, "ab", strlen("ab"));
    insertKeyword(pTreeInfo, "abx", strlen("abx"));
    insertKeyword(pTreeInfo, "     ", strlen("     "));


    if ( findKeyword(pTreeInfo, text) > 0){
        myStrcpy_s(tmpFindKeyword, g_findKeyword, g_findKeyword_Len);

        printf("      =   (%s) 
", tmpFindKeyword);
        } 
    else {
        printf("      ！
");
    }

    printf("
---->            ----- 

");
    char* delKeyword =  "     ";
    deleteKeyword(pTreeInfo, delKeyword, strlen(delKeyword));

    printf("     ：( %s)
     ...
 
", delKeyword);

    if ( findKeyword(pTreeInfo, text) > 0){
        myStrcpy_s(tmpFindKeyword, g_findKeyword, g_findKeyword_Len);

        printf("      =   (%s) 
", tmpFindKeyword);
        } 
    else {
        printf("      ！
");
    }

    deinitTreeInfo(pTreeInfo);
}


int main(int argc, char* argv[])
{
    //     
    testPerformance(argc, argv);

    //test();

    return 0;
}

mpool.h

/*******************************************************
     ：
      ：                     ，   Cache miss。
                                    2017.04.08
*******************************************************/
#ifndef MPOOL_H
#define MPOOL_H

#include 
//#include 

#ifdef _MSC_VER // windows     
#define INLINE(RETURN_TYPE) RETURN_TYPE 
#else
#define INLINE(RETURN_TYPE) \
    static inline RETURN_TYPE __attribute__((always_inline))
#endif

#define M_ALIGNMENT     8       //         
#pragma pack(8)

#ifndef MPOOL_MALLOC
#define MPOOL_MALLOC(sz) malloc(sz)
#define MPOOL_REALLOC(p, sz) realloc(p, sz)
#define MPOOL_FREE(p, sz) free(p)
#endif

//      
typedef struct {
    void* pBlock;           //        
    void* pCur;             //                   
    int remainderSize;      //                
} mBlockInfo;

//      
typedef struct {
    unsigned int defaultBlockSize;          //             （  ），               ，                  。
                                            //               ，         ;       ，      ！
    unsigned int nAllocBytes;               //          
    unsigned int blockCnts;                 //         

    mBlockInfo mBlockInfoArray[1];          //      ，               
    //   ：               
} mpool;

//   ：       ，        
//   ： nBlockSize -           
//       maxBlockCnts -           （  ：         ，              ）
mpool *mpool_init(unsigned int nBlockSize, unsigned int maxBlockCnts);

void* mpool_alloc(mpool* mp, int nBytes);
void mpool_destroy(mpool* mp);
#endif

mpool.c

#include 
#include 
#include 
#include "mpool.h"


//      ，    4096.
long getPageSize()
{
    return 4096;
//#ifdef _MSC_VER   // windows     
//  return 4096;
//#else         // Linux     
//#include 
//long pgsz = sysconf(_SC_PAGESIZE);
//return pasz;
//#endif
}

//   ：       ，        
//   ： nBlockSize -           
//       maxBlockCnts -           （  ：         ，              ）

mpool *
mpool_init(unsigned int nBlockSize, unsigned int maxBlockCnts /* = 100*/)
{
    printf("test
");

    mpool * pMpool = (mpool*)malloc(sizeof(mpool) + (maxBlockCnts - 1) * sizeof(mBlockInfo));

    long pgsz = getPageSize();  //          
    pMpool->defaultBlockSize = pgsz * ((nBlockSize + pgsz - 1) / pgsz); //         ，             
    pMpool->blockCnts = 0;
    pMpool->nAllocBytes = 0;

    return pMpool;
}


void*
 mpool_alloc(mpool* mp, int nBytes)
{
    assert(mp);
    void* retVal = NULL;    //    
    void* pAlloc = NULL;
    int i, tmp;
    unsigned int blockCnts = mp->blockCnts;
    unsigned int allocBlockSize = mp->defaultBlockSize;
    unsigned int ActualBytes = M_ALIGNMENT * ((nBytes + M_ALIGNMENT - 1) / M_ALIGNMENT);    //           （  ，          ，      nBytes）
    mBlockInfo* pBlockInfo = NULL;

    if (mp->defaultBlockSize < nBytes)
    {
        printf("          >         
");
        return NULL;
    }

    //            ，            
    for (i = 0; i < blockCnts; ++i)
    {
        if (mp->mBlockInfoArray[i].remainderSize >= ActualBytes)
        {
        //  printf("         。。。。
");

            pBlockInfo = &(mp->mBlockInfoArray[i]);
            retVal = pBlockInfo->pCur;

             pBlockInfo->remainderSize -= ActualBytes;

            pBlockInfo->pCur = (void*)((char*)pBlockInfo->pCur + ActualBytes);


            break;
        }
    }

    //             ，         。
    if (NULL == retVal)
    {
        //printf("     
");

        do 
        {
            retVal = malloc(allocBlockSize);
            if (NULL != retVal)
            {
                mp->nAllocBytes += allocBlockSize;

                break;
            }

            //printf("    ，    %d,    %d
", allocBlockSize, allocBlockSize / 2);

            allocBlockSize /= 2;

            if (0 == allocBlockSize)
            {
                break;
            }

        } while (1);

        if (NULL != retVal)
        {
            pBlockInfo = &(mp->mBlockInfoArray[mp->blockCnts]);

            pBlockInfo->pBlock = retVal;

            pBlockInfo->remainderSize = allocBlockSize;
            pBlockInfo->pCur = retVal;

            if (allocBlockSize >= ActualBytes)
            {
                pBlockInfo->remainderSize -= ActualBytes;

                pBlockInfo->pCur = (void*)((char*)pBlockInfo->pCur + ActualBytes);
            }
            else
            {
                //printf("mpool_init: allocBlockSize = %d , ActualBytes = %d... 9
", allocBlockSize, ActualBytes);
                retVal = NULL;
            }

            mp->blockCnts++;
        }
    }

    if (NULL == retVal)
    {
        printf("ffk
");
    }

    return retVal;
}


void
mpool_destroy(mpool* mp)
{
    int i;
    unsigned int blockCnts = mp->blockCnts;
    for (i = 0; i < blockCnts; ++i)
    {
        free(mp->mBlockInfoArray[i].pBlock);
    }

    free(mp);

    mp = NULL;
}

getTime.h

#ifndef GETTIME_H
#define GETTIME_H

#ifdef _MSC_VER // windows     

#include 
#include 
#include 

//       
long long getSystemTime()
{
    return GetTickCount();
}

#else           // Linux     

#include 
#include // sleep(3);
#include //timeb

//       
 long long getSystemTime() 
{ 
    struct timeb t;
    ftime(&t);
    return 1000 * t.time + t.millitm;
}
#endif

#endif

Makefile

main:
        gcc mpool.c getTime.h FindKeyword.c -o findKeyword -O3
clean: 
        rm -f findKeyword

1.マルチモードマッチング2.一般的なアルゴリズム