bmsearch.c

字符串搜索

/******************************************************************************
*
* Revision History:
*   Date            Author          Modification
* ---------------------------------------------------------------------
*
*   采用boyer-moore算法最简单的描述实现，没有添加预处理和改进算法,若是英文搜索，区分大小写
*****************************************************************************/
#include "..\..\include\owner\bmsearch.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static D_U8* n_CheckContentInKW(D_U32 lastkeybyteindex,D_U32 cdataend, D_U8* kdata, D_U8* cdata)
{
    D_U32 kindex;
    D_BOOL have = D_FALSE;
    
    for(kindex=0; kindex<lastkeybyteindex; kindex++)
    {
        if(cdata[lastkeybyteindex] != kdata[kindex]) 
            continue;
        else {
            have = D_TRUE;
            break;
        }
    }
    if(((D_U32)(cdata+lastkeybyteindex-kindex) < cdataend)&&have)
        cdata = (cdata+lastkeybyteindex-kindex);
    else if(((D_U32)(cdata+lastkeybyteindex-kindex) < cdataend)&&(!have))
        cdata +=lastkeybyteindex+1;
    else
        cdata = (D_U8*)cdataend;
    return cdata;
}

static D_BOOL n_KWIdentical(D_U32 lastkeybyteindex, D_U8* kdata, D_U8** pcdata)
{
    D_U32 kindex;
    
    for(kindex=0; kindex<lastkeybyteindex; kindex++)
    {
        if((*pcdata)[kindex] != kdata[kindex])
            return D_FALSE;	
    }
    *pcdata = *pcdata+lastkeybyteindex+1;
    return D_TRUE;
}

D_U32 D_BMSearch(const D_BM_KeyWord *pKeyData, const D_BM_ContentData *pContentData, D_U32* numbers, D_U32 index, D_U32* offset)
{
    D_U8* kdata = pKeyData->data;
    D_U32 csize = pContentData->size;
    D_U8* cdata = pContentData->data;
    D_U32 lastkeybyteindex = pKeyData->size-1; /* keyword最后一位的index；*/
    D_U32 lastkeybyteval = kdata[lastkeybyteindex]; /* keyword最后一位的值；*/
    D_U32 cdataend = (D_U32)(cdata + csize);
    
    if(kdata == NULL)              
        return KEYWORD_DATA_IS_NULL;
    if(cdata == NULL)
        return CONTENT_DATA_IS_NULL;
    if(csize == 0)
        return CONTENT_DATA_SIZE_INVALID;
    
    *numbers = 0;
	*offset  = 0;
    while((D_U32)cdata < cdataend)
    {
        if(lastkeybyteval != cdata[lastkeybyteindex])  
            cdata = n_CheckContentInKW(lastkeybyteindex, cdataend, kdata, cdata);
        else
        {
            if(n_KWIdentical(lastkeybyteindex, kdata, &cdata)) 
			{
                (*numbers)++;
				if(*numbers == index)
				{
					*offset = (D_U32)((D_U32)cdata - (D_U32)(pContentData->data) - pKeyData->size);
				}
			}
            else 
                cdata = n_CheckContentInKW(lastkeybyteindex, cdataend, kdata, cdata);
        }
    }
    return D_OK;
}