← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/corelib/tools/qbytearraymatcher.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-08-24 04:09:09 UTC
  • Revision ID: james.westby@ubuntu.com-20050824040909-xmxe9jfr4a0w5671
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/corelib/tools/qbytearraymatcher.cpp
 
1
/****************************************************************************
 
2
**
 
3
** Copyright (C) 1992-2005 Trolltech AS. All rights reserved.
 
4
**
 
5
** This file is part of the core module of the Qt Toolkit.
 
6
**
 
7
** This file may be distributed under the terms of the Q Public License
 
8
** as defined by Trolltech AS of Norway and appearing in the file
 
9
** LICENSE.QPL included in the packaging of this file.
 
10
**
 
11
** This file may be distributed and/or modified under the terms of the
 
12
** GNU General Public License version 2 as published by the Free Software
 
13
** Foundation and appearing in the file LICENSE.GPL included in the
 
14
** packaging of this file.
 
15
**
 
16
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
 
17
**   information about Qt Commercial License Agreements.
 
18
** See http://www.trolltech.com/qpl/ for QPL licensing information.
 
19
** See http://www.trolltech.com/gpl/ for GPL licensing information.
 
20
**
 
21
** Contact info@trolltech.com if any conditions of this licensing are
 
22
** not clear to you.
 
23
**
 
24
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 
25
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 
26
**
 
27
****************************************************************************/
 
28
 
 
29
#include "qbytearraymatcher.h"
 
30
 
 
31
static inline void bm_init_skiptable(const uchar *cc, int l, uint *skiptable)
 
32
{
 
33
    int i = 0;
 
34
    register uint *st = skiptable;
 
35
    while (i++ < 256 / 8) {
 
36
        *st++ = l; *st++ = l; *st++ = l; *st++ = l;
 
37
        *st++ = l; *st++ = l; *st++ = l; *st++ = l;
 
38
    }
 
39
    while (l--)
 
40
        skiptable[*cc++] = l;
 
41
}
 
42
 
 
43
static inline int bm_find(const uchar *cc, int l, int index, const uchar *puc, uint pl,
 
44
                          const uint *skiptable)
 
45
{
 
46
    if (pl == 0)
 
47
        return index > l ? -1 : index;
 
48
    const uint pl_minus_one = pl - 1;
 
49
 
 
50
    register const uchar *current = cc + index + pl_minus_one;
 
51
    const uchar *end = cc + l;
 
52
    while (current < end) {
 
53
        uint skip = skiptable[*current];
 
54
        if (!skip) {
 
55
            // possible match
 
56
            while (skip < pl) {
 
57
                if (*(current - skip) != puc[pl_minus_one - skip])
 
58
                    break;
 
59
                skip++;
 
60
            }
 
61
            if (skip > pl_minus_one) // we have a match
 
62
                return (current - cc) - skip + 1;
 
63
 
 
64
            // in case we don't have a match we are a bit inefficient as we only skip by one
 
65
            // when we have the non matching char in the string.
 
66
            if (skiptable[*(current - skip)] == pl)
 
67
                skip = pl - skip;
 
68
            else
 
69
                skip = 1;
 
70
        }
 
71
        if (current > end - skip)
 
72
            break;
 
73
        current += skip;
 
74
    }
 
75
    return -1; // not found
 
76
}
 
77
 
 
78
/*! \class QByteArrayMatcher
 
79
    \brief The QByteArrayMatcher class holds a sequence of bytes that
 
80
    can be quickly matched in a byte array.
 
81
 
 
82
    \ingroup tools
 
83
    \ingroup text
 
84
 
 
85
    This class is useful when you have a sequence of bytes that you
 
86
    want to repeatedly match against some byte arrays (perhaps in a
 
87
    loop), or when you want to search for the same sequence of bytes
 
88
    multiple times in the same byte array. Using a matcher object and
 
89
    indexIn() is faster than matching a plain QByteArray with
 
90
    QByteArray::indexOf() if repeated matching takes place. This
 
91
    class offers no benefit if you are doing one-off byte array
 
92
    matches.
 
93
 
 
94
    Create the QByteArrayMatcher with the QByteArray you want to
 
95
    search for. Then call indexIn() on the QByteArray that you want to
 
96
    search.
 
97
 
 
98
    \sa QByteArray, QStringMatcher
 
99
*/
 
100
 
 
101
/*!
 
102
    Constructs an empty byte array matcher that won't match anything.
 
103
    Call setPattern() to give it a pattern to match.
 
104
*/
 
105
QByteArrayMatcher::QByteArrayMatcher()
 
106
    : d(0)
 
107
{
 
108
    qMemSet(q_skiptable, 0, sizeof(q_skiptable));
 
109
}
 
110
 
 
111
/*!
 
112
    Constructs a byte array matcher that will search for \a pattern.
 
113
    Call indexIn() to perform a search.
 
114
*/
 
115
QByteArrayMatcher::QByteArrayMatcher(const QByteArray &pattern)
 
116
    : d(0)
 
117
{
 
118
    setPattern(pattern);
 
119
}
 
120
 
 
121
/*!
 
122
    Copies the \a other byte array matcher to this byte array matcher.
 
123
*/
 
124
QByteArrayMatcher::QByteArrayMatcher(const QByteArrayMatcher &other)
 
125
    : d(0)
 
126
{
 
127
    operator=(other);
 
128
}
 
129
 
 
130
/*!
 
131
    Destroys the byte array matcher.
 
132
*/
 
133
QByteArrayMatcher::~QByteArrayMatcher()
 
134
{
 
135
}
 
136
 
 
137
/*!
 
138
    Assigns the \a other byte array matcher to this byte array matcher.
 
139
*/
 
140
QByteArrayMatcher &QByteArrayMatcher::operator=(const QByteArrayMatcher &other)
 
141
{
 
142
    q_pattern = other.q_pattern;
 
143
    qMemCopy(q_skiptable, other.q_skiptable, sizeof(q_skiptable));
 
144
    return *this;
 
145
}
 
146
 
 
147
/*!
 
148
    Sets the byte array that this byte array matcher will search for
 
149
    to \a pattern.
 
150
 
 
151
    \sa pattern(), indexIn()
 
152
*/
 
153
void QByteArrayMatcher::setPattern(const QByteArray &pattern)
 
154
{
 
155
    bm_init_skiptable(reinterpret_cast<const uchar *>(pattern.constData()), pattern.size(),
 
156
                      q_skiptable);
 
157
    q_pattern = pattern;
 
158
}
 
159
 
 
160
/*!
 
161
    Searches the byte array \a ba, from byte position \a from (default
 
162
    0, i.e. from the first byte), for the byte array pattern() that
 
163
    was set in the constructor or in the most recent call to
 
164
    setPattern(). Returns the position where the pattern() matched in
 
165
    \a ba, or -1 if no match was found.
 
166
*/
 
167
int QByteArrayMatcher::indexIn(const QByteArray &ba, int from) const
 
168
{
 
169
    if (from < 0)
 
170
        from = 0;
 
171
    return bm_find(reinterpret_cast<const uchar *>(ba.constData()), ba.size(), from,
 
172
                   reinterpret_cast<const uchar *>(q_pattern.constData()), q_pattern.size(),
 
173
                   q_skiptable);
 
174
}
 
175
 
 
176
/*!
 
177
    \fn QByteArray QByteArrayMatcher::pattern() const
 
178
 
 
179
    Returns the byte array pattern that this byte array matcher will
 
180
    search for.
 
181
 
 
182
    \sa setPattern()
 
183
*/