1.1 --- a/jitcraft/HashTable.h Sat Jul 07 17:11:31 2012 -0700
1.2 +++ b/jitcraft/HashTable.h Sat Jul 07 20:28:29 2012 -0700
1.3 @@ -1,23 +1,28 @@
1.4 -// vim: set ts=4 sw=4 tw=99 et:
1.5 -//
1.6 -//
1.7 -// (C) Copyright 2010-2011 AlliedModders LLC
1.8 -//
1.9 -// Initial Author: David Anderson
1.10 -// Contributors:
1.11 -//
1.12 -//
1.13 -
1.14 +/*
1.15 + * Copyright (C) 2012 David Anderson
1.16 + *
1.17 + * This file is part of JITCraft.
1.18 + *
1.19 + * JITCraft is free software: you can redistribute it and/or modify it under
1.20 + * the terms of the GNU General Public License as published by the Free
1.21 + * Software Foundation, either version 3 of the License, or (at your option)
1.22 + * any later version.
1.23 + *
1.24 + * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
1.25 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.26 + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
1.27 + *
1.28 + * You should have received a copy of the GNU General Public License along with
1.29 + * JITCraft. If not, see http://www.gnu.org/licenses/.
1.30 + */
1.31 #ifndef _INCLUDE_KEIMA_HASHTABLE_H_
1.32 #define _INCLUDE_KEIMA_HASHTABLE_H_
1.33
1.34 #include <new>
1.35 #include <limits.h>
1.36 -#include "Object.h"
1.37 -#include "vm/Array.h"
1.38 -#include "Environment.h"
1.39 +#include "Utility.h"
1.40
1.41 -namespace ke {
1.42 +namespace jc {
1.43
1.44 template <typename T>
1.45 class HashTableEntry
1.46 @@ -38,9 +43,10 @@
1.47 }
1.48 void setRemoved() {
1.49 hash_ = kRemovedHash;
1.50 - destruct();
1.51 + t_ = T();
1.52 }
1.53 void construct() {
1.54 + hash_ = kFreeHash;
1.55 new (&t_) T();
1.56 }
1.57 void destruct() {
1.58 @@ -66,6 +72,8 @@
1.59 template <typename HashPolicy, typename AllocPolicy>
1.60 class HashTable : public AllocPolicy
1.61 {
1.62 + friend class iterator;
1.63 +
1.64 typedef typename HashPolicy::Payload Payload;
1.65 typedef HashTableEntry<Payload> Entry;
1.66
1.67 @@ -73,6 +81,7 @@
1.68 uint32 nelements_;
1.69 uint32 ndeleted_;
1.70 Entry *table_;
1.71 + uint32 minCapacity_;
1.72
1.73 private:
1.74 static const uint32 kMinCapacity = 16;
1.75 @@ -88,7 +97,7 @@
1.76 }
1.77
1.78 Entry *createTable(uint32 capacity) {
1.79 - KE_ASSERT(capacity <= kMaxCapacity);
1.80 + assert(capacity <= kMaxCapacity);
1.81
1.82 Entry *table = (Entry *)this->malloc(capacity * sizeof(Entry));
1.83 if (!table)
1.84 @@ -154,7 +163,7 @@
1.85 : hash_(hash),
1.86 capacity_(capacity)
1.87 {
1.88 - KE_ASSERT(IsPowerOfTwo(capacity_));
1.89 + assert(IsPowerOfTwo(capacity_));
1.90 }
1.91
1.92 uint32 entry() const {
1.93 @@ -176,11 +185,13 @@
1.94 }
1.95
1.96 bool shrink() {
1.97 + if ((capacity_ >> 1) < minCapacity_)
1.98 + return true;
1.99 return changeCapacity(capacity_ >> 1);
1.100 }
1.101
1.102 bool grow() {
1.103 - KE_ASSERT(IsPowerOfTwo(kMaxCapacity));
1.104 + assert(IsPowerOfTwo(kMaxCapacity));
1.105 if (capacity_ >= kMaxCapacity) {
1.106 this->reportAllocationOverflow();
1.107 return false;
1.108 @@ -188,16 +199,8 @@
1.109 return changeCapacity(capacity_ << 1);
1.110 }
1.111
1.112 - bool checkDensity() {
1.113 - if (underloaded())
1.114 - return shrink();
1.115 - if (overloaded())
1.116 - return grow();
1.117 - return true;
1.118 - }
1.119 -
1.120 bool changeCapacity(uint32 newCapacity) {
1.121 - KE_ASSERT(newCapacity <= kMaxCapacity);
1.122 + assert(newCapacity <= kMaxCapacity);
1.123
1.124 Entry *newTable = createTable(newCapacity);
1.125 if (!newTable)
1.126 @@ -219,7 +222,7 @@
1.127 }
1.128 oldEntry.destruct();
1.129 }
1.130 - this->free(table_);
1.131 + this->free(oldTable);
1.132
1.133 return true;
1.134 }
1.135 @@ -277,7 +280,7 @@
1.136 }
1.137
1.138 bool add(Insert &i) {
1.139 - KE_ASSERT(!i.found());
1.140 + assert(!i.found());
1.141
1.142 // If the entry is deleted, just re-use the slot.
1.143 if (i.entry().removed()) {
1.144 @@ -310,13 +313,21 @@
1.145 return true;
1.146 }
1.147
1.148 + void remove(Entry &e) {
1.149 + assert(!e.isLive());
1.150 + e.setRemoved();
1.151 + ndeleted_++;
1.152 + nelements_--;
1.153 + }
1.154 +
1.155 public:
1.156 HashTable(AllocPolicy ap)
1.157 : AllocPolicy(ap),
1.158 capacity_(0),
1.159 nelements_(0),
1.160 ndeleted_(0),
1.161 - table_(NULL)
1.162 + table_(NULL),
1.163 + minCapacity_(kMinCapacity)
1.164 {
1.165 }
1.166
1.167 @@ -333,7 +344,9 @@
1.168 else if (capacity > kMaxCapacity)
1.169 capacity = kMaxCapacity;
1.170
1.171 - KE_ASSERT(IsPowerOfTwo(capacity));
1.172 + minCapacity_ = capacity;
1.173 +
1.174 + assert(IsPowerOfTwo(capacity));
1.175 capacity_ = capacity;
1.176
1.177 table_ = createTable(capacity_);
1.178 @@ -359,9 +372,52 @@
1.179 *i = payload;
1.180 return true;
1.181 }
1.182 +
1.183 + bool checkDensity() {
1.184 + if (underloaded())
1.185 + return shrink();
1.186 + if (overloaded())
1.187 + return grow();
1.188 + return true;
1.189 + }
1.190 +
1.191 + public:
1.192 + class iterator
1.193 + {
1.194 + HashTable *table_;
1.195 + Entry *i_;
1.196 + Entry *end_;
1.197 +
1.198 + public:
1.199 + iterator(HashTable *table)
1.200 + : table_(table),
1.201 + i_(table->table_),
1.202 + end_(table->table_ + table->capacity_)
1.203 + {
1.204 + while (i_ < end_ && !i_->isLive())
1.205 + i_++;
1.206 + }
1.207 +
1.208 + bool empty() const {
1.209 + return i_ == end_;
1.210 + }
1.211 +
1.212 + void erase() {
1.213 + assert(!empty());
1.214 + table_->remove(*i_);
1.215 + }
1.216 +
1.217 + const Payload &operator *() const {
1.218 + return i_->payload();
1.219 + }
1.220 +
1.221 + void next() {
1.222 + while (i_ < end_ && !i_->isLive())
1.223 + i_++;
1.224 + }
1.225 + };
1.226 };
1.227
1.228 }
1.229
1.230 #endif // _INCLUDE_KEIMA_HASHTABLE_H_
1.231 -
