1// Copyright 2011 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_PARSING_DUPLICATE_FINDER_H_
6#define V8_PARSING_DUPLICATE_FINDER_H_
7
8#include "src/base/hashmap.h"
9#include "src/collector.h"
10
11namespace v8 {
12namespace internal {
13
14// DuplicateFinder discovers duplicate symbols.
15class DuplicateFinder {
16 public:
17  DuplicateFinder() : backing_store_(16), map_(&Match) {}
18
19  bool AddOneByteSymbol(Vector<const uint8_t> key);
20  bool AddTwoByteSymbol(Vector<const uint16_t> key);
21
22 private:
23  bool AddSymbol(Vector<const uint8_t> key, bool is_one_byte);
24  // Backs up the key and its length in the backing store.
25  // The backup is stored with a base 127 encoding of the
26  // length (plus a bit saying whether the string is one byte),
27  // followed by the bytes of the key.
28  uint8_t* BackupKey(Vector<const uint8_t> key, bool is_one_byte);
29
30  // Compare two encoded keys (both pointing into the backing store)
31  // for having the same base-127 encoded lengths and representation.
32  // and then having the same 'length' bytes following.
33  static bool Match(void* first, void* second);
34
35  // Creates a hash from a sequence of bytes.
36  static uint32_t Hash(Vector<const uint8_t> key, bool is_one_byte);
37
38  // Backing store used to store strings used as hashmap keys.
39  SequenceCollector<unsigned char> backing_store_;
40  base::CustomMatcherHashMap map_;
41};
42
43}  // namespace internal
44}  // namespace v8
45
46#endif  // V8_PARSING_DUPLICATE_FINDER_H_
47