Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(30)

Side by Side Diff: third_party/WebKit/Source/platform/text/SuffixTree.h

Issue 1521923002: Make platform/text to use USING_FAST_MALLOC. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Created 4 years, 12 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
1 /* 1 /*
2 * Copyright (C) 2010 Adam Barth. All rights reserved. 2 * Copyright (C) 2010 Adam Barth. All rights reserved.
3 * 3 *
4 * Redistribution and use in source and binary forms, with or without 4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions 5 * modification, are permitted provided that the following conditions
6 * are met: 6 * are met:
7 * 1. Redistributions of source code must retain the above copyright 7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer. 8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright 9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the 10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution. 11 * documentation and/or other materials provided with the distribution.
12 * 12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */ 24 */
25 25
26 #ifndef SuffixTree_h 26 #ifndef SuffixTree_h
27 #define SuffixTree_h 27 #define SuffixTree_h
28 28
29 #include "wtf/Allocator.h"
30 #include "wtf/Noncopyable.h"
29 #include "wtf/Vector.h" 31 #include "wtf/Vector.h"
30 #include "wtf/text/WTFString.h" 32 #include "wtf/text/WTFString.h"
31 33
32 namespace blink { 34 namespace blink {
33 35
34 class UnicodeCodebook { 36 class UnicodeCodebook {
37 STATIC_ONLY(UnicodeCodebook);
35 public: 38 public:
36 static int codeWord(UChar c) { return c; } 39 static int codeWord(UChar c) { return c; }
37 enum { codeSize = 1 << 8 * sizeof(UChar) }; 40 enum { codeSize = 1 << 8 * sizeof(UChar) };
38 }; 41 };
39 42
40 class ASCIICodebook { 43 class ASCIICodebook {
44 STATIC_ONLY(ASCIICodebook);
41 public: 45 public:
42 static int codeWord(UChar c) { return c & (codeSize - 1); } 46 static int codeWord(UChar c) { return c & (codeSize - 1); }
43 enum { codeSize = 1 << (8 * sizeof(char) - 1) }; 47 enum { codeSize = 1 << (8 * sizeof(char) - 1) };
44 }; 48 };
45 49
46 template<typename Codebook> 50 template<typename Codebook>
47 class SuffixTree { 51 class SuffixTree {
52 USING_FAST_MALLOC(SuffixTree);
53 WTF_MAKE_NONCOPYABLE(SuffixTree);
48 public: 54 public:
49 SuffixTree(const String& text, unsigned depth) 55 SuffixTree(const String& text, unsigned depth)
50 : m_depth(depth) 56 : m_depth(depth)
51 , m_leaf(true) 57 , m_leaf(true)
52 { 58 {
53 build(text); 59 build(text);
54 } 60 }
55 61
56 bool mightContain(const String& query) 62 bool mightContain(const String& query)
57 { 63 {
58 Node* current = &m_root; 64 Node* current = &m_root;
59 int limit = std::min(m_depth, query.length()); 65 int limit = std::min(m_depth, query.length());
60 for (int i = 0; i < limit; ++i) { 66 for (int i = 0; i < limit; ++i) {
61 current = current->at(Codebook::codeWord(query[i])); 67 current = current->at(Codebook::codeWord(query[i]));
62 if (!current) 68 if (!current)
63 return false; 69 return false;
64 } 70 }
65 return true; 71 return true;
66 } 72 }
67 73
68 private: 74 private:
69 class Node { 75 class Node {
76 USING_FAST_MALLOC(Node);
77 WTF_MAKE_NONCOPYABLE(Node);
70 public: 78 public:
71 Node(bool isLeaf = false) 79 Node(bool isLeaf = false)
72 { 80 {
73 m_children.resize(Codebook::codeSize); 81 m_children.resize(Codebook::codeSize);
74 m_children.fill(0); 82 m_children.fill(0);
75 m_isLeaf = isLeaf; 83 m_isLeaf = isLeaf;
76 } 84 }
77 85
78 ~Node() 86 ~Node()
79 { 87 {
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after
113 121
114 // Instead of allocating a fresh empty leaf node for ever leaf in the tree 122 // Instead of allocating a fresh empty leaf node for ever leaf in the tree
115 // (there can be a lot of these), we alias all the leaves to this "static" 123 // (there can be a lot of these), we alias all the leaves to this "static"
116 // leaf node. 124 // leaf node.
117 Node m_leaf; 125 Node m_leaf;
118 }; 126 };
119 127
120 } // namespace blink 128 } // namespace blink
121 129
122 #endif // SuffixTree_h 130 #endif // SuffixTree_h
OLDNEW
« no previous file with comments | « third_party/WebKit/Source/platform/text/StringTruncator.h ('k') | third_party/WebKit/Source/platform/text/TabSize.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698