qstringmatcher.cpp File Reference

#include "qstringmatcher.h"

Go to the source code of this file.

Functions
static int	bm_find (const ushort *uc, uint l, int index, const ushort *puc, uint pl, const uchar *skiptable, Qt::CaseSensitivity cs)
static void	bm_init_skiptable (const ushort *uc, int len, uchar *skiptable, Qt::CaseSensitivity cs)
int	qFindStringBoyerMoore (const QChar *haystack, int haystackLen, int haystackOffset, const QChar *needle, int needleLen, Qt::CaseSensitivity cs)

Function Documentation

bm_find()

static int bm_find ( const ushort *  uc, uint  l, int  index, const ushort *  puc, uint  pl, const uchar *  skiptable, Qt::CaseSensitivity  cs  )

inlinestatic

Definition at line 65 of file qstringmatcher.cpp.

Referenced by QStringMatcher::indexIn(), and qFindStringBoyerMoore().

{
    if (pl == 0)
        return index > (int)l ? -1 : index;
    const uint pl_minus_one = pl - 1;

    register const ushort *current = uc + index + pl_minus_one;
    const ushort *end = uc + l;
    if (cs == Qt::CaseSensitive) {
        while (current < end) {
            uint skip = skiptable[*current & 0xff];
            if (!skip) {
                // possible match
                while (skip < pl) {
                    if (*(current - skip) != puc[pl_minus_one-skip])
                        break;
                    skip++;
                }
                if (skip > pl_minus_one) // we have a match
                    return (current - uc) - pl_minus_one;

                // in case we don't have a match we are a bit inefficient as we only skip by one
                // when we have the non matching char in the string.
                if (skiptable[*(current - skip) & 0xff] == pl)
                    skip = pl - skip;
                else
                    skip = 1;
            }
            if (current > end - skip)
                break;
            current += skip;
        }
    } else {
        while (current < end) {
            uint skip = skiptable[foldCase(current, uc) & 0xff];
            if (!skip) {
                // possible match
                while (skip < pl) {
                    if (foldCase(current - skip, uc) != foldCase(puc + pl_minus_one - skip, puc))
                        break;
                    skip++;
                }
                if (skip > pl_minus_one) // we have a match
                    return (current - uc) - pl_minus_one;
                // in case we don't have a match we are a bit inefficient as we only skip by one
                // when we have the non matching char in the string.
                if (skiptable[foldCase(current - skip, uc) & 0xff] == pl)
                    skip = pl - skip;
                else
                    skip = 1;
            }
            if (current > end - skip)
                break;
            current += skip;
        }
    }
    return -1; // not found
}

bm_init_skiptable()

static void bm_init_skiptable ( const ushort *  uc, int  len, uchar *  skiptable, Qt::CaseSensitivity  cs  )

static

Definition at line 46 of file qstringmatcher.cpp.

Referenced by qFindStringBoyerMoore(), QStringMatcher::QStringMatcher(), QStringMatcher::setCaseSensitivity(), and QStringMatcher::setPattern().

{
    int l = qMin(len, 255);
    memset(skiptable, l, 256*sizeof(uchar));
    uc += len - l;
    if (cs == Qt::CaseSensitive) {
        while (l--) {
            skiptable[*uc & 0xff] = l;
            uc++;
        }
    } else {
        const ushort *start = uc;
        while (l--) {
            skiptable[foldCase(uc, start) & 0xff] = l;
            uc++;
        }
    }
}

qFindStringBoyerMoore()

int qFindStringBoyerMoore	(	const QChar *	haystack,
		int	haystackLen,
		int	haystackOffset,
		const QChar *	needle,
		int	needleLen,
		Qt::CaseSensitivity	cs
	)

Warning

This function is not part of the public interface.

Definition at line 322 of file qstringmatcher.cpp.

Referenced by qFindString().

{
    uchar skiptable[256];
    bm_init_skiptable((const ushort *)needle, needleLen, skiptable, cs);
    if (haystackOffset < 0)
        haystackOffset = 0;
    return bm_find((const ushort *)haystack, haystackLen, haystackOffset,
                   (const ushort *)needle, needleLen, skiptable, cs);
}