1// Copyright 2014 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#include "src/compiler/node-cache.h"
6
7namespace v8 {
8namespace internal {
9namespace compiler {
10
11#define INITIAL_SIZE 16
12#define LINEAR_PROBE 5
13
14template <typename Key>
15int32_t NodeCacheHash(Key key) {
16  UNIMPLEMENTED();
17  return 0;
18}
19
20template <>
21inline int32_t NodeCacheHash(int32_t key) {
22  return ComputeIntegerHash(key, 0);
23}
24
25
26template <>
27inline int32_t NodeCacheHash(int64_t key) {
28  return ComputeLongHash(key);
29}
30
31
32template <>
33inline int32_t NodeCacheHash(double key) {
34  return ComputeLongHash(bit_cast<int64_t>(key));
35}
36
37
38template <>
39inline int32_t NodeCacheHash(void* key) {
40  return ComputePointerHash(key);
41}
42
43
44template <typename Key>
45bool NodeCache<Key>::Resize(Zone* zone) {
46  if (size_ >= max_) return false;  // Don't grow past the maximum size.
47
48  // Allocate a new block of entries 4x the size.
49  Entry* old_entries = entries_;
50  int old_size = size_ + LINEAR_PROBE;
51  size_ = size_ * 4;
52  int num_entries = size_ + LINEAR_PROBE;
53  entries_ = zone->NewArray<Entry>(num_entries);
54  memset(entries_, 0, sizeof(Entry) * num_entries);
55
56  // Insert the old entries into the new block.
57  for (int i = 0; i < old_size; i++) {
58    Entry* old = &old_entries[i];
59    if (old->value_ != NULL) {
60      int hash = NodeCacheHash(old->key_);
61      int start = hash & (size_ - 1);
62      int end = start + LINEAR_PROBE;
63      for (int j = start; j < end; j++) {
64        Entry* entry = &entries_[j];
65        if (entry->value_ == NULL) {
66          entry->key_ = old->key_;
67          entry->value_ = old->value_;
68          break;
69        }
70      }
71    }
72  }
73  return true;
74}
75
76
77template <typename Key>
78Node** NodeCache<Key>::Find(Zone* zone, Key key) {
79  int32_t hash = NodeCacheHash(key);
80  if (entries_ == NULL) {
81    // Allocate the initial entries and insert the first entry.
82    int num_entries = INITIAL_SIZE + LINEAR_PROBE;
83    entries_ = zone->NewArray<Entry>(num_entries);
84    size_ = INITIAL_SIZE;
85    memset(entries_, 0, sizeof(Entry) * num_entries);
86    Entry* entry = &entries_[hash & (INITIAL_SIZE - 1)];
87    entry->key_ = key;
88    return &entry->value_;
89  }
90
91  while (true) {
92    // Search up to N entries after (linear probing).
93    int start = hash & (size_ - 1);
94    int end = start + LINEAR_PROBE;
95    for (int i = start; i < end; i++) {
96      Entry* entry = &entries_[i];
97      if (entry->key_ == key) return &entry->value_;
98      if (entry->value_ == NULL) {
99        entry->key_ = key;
100        return &entry->value_;
101      }
102    }
103
104    if (!Resize(zone)) break;  // Don't grow past the maximum size.
105  }
106
107  // If resized to maximum and still didn't find space, overwrite an entry.
108  Entry* entry = &entries_[hash & (size_ - 1)];
109  entry->key_ = key;
110  entry->value_ = NULL;
111  return &entry->value_;
112}
113
114
115template class NodeCache<int64_t>;
116template class NodeCache<int32_t>;
117template class NodeCache<void*>;
118}
119}
120}  // namespace v8::internal::compiler
121