# HG changeset patch # User David Anderson # Date 1356487982 28800 # Node ID e3c851a14f166a8986a7c1e919743985124fe9a0 # Parent 572668ef742b5361b4d5335fec834353e0aea54d Add weak hashtable to manage qual types. diff -r 572668ef742b -r e3c851a14f16 src/Handles.h --- a/src/Handles.h Tue Dec 25 17:02:07 2012 -0800 +++ b/src/Handles.h Tue Dec 25 18:13:02 2012 -0800 @@ -73,7 +73,7 @@ T *operator *() { return *thingp_; } - operator T *() { return *thingp_; } + operator T *() const { return *thingp_; } operator bool() const { return thingp_ && *thingp_; } diff -r 572668ef742b -r e3c851a14f16 src/Heap.cpp --- a/src/Heap.cpp Tue Dec 25 17:02:07 2012 -0800 +++ b/src/Heap.cpp Tue Dec 25 18:13:02 2012 -0800 @@ -350,7 +350,7 @@ Heap::sweep() { // Before destroying mark bits, sweep weak roots. - zone_->symbols()->sweep(); + zone_->sweepWeakRoots(); // Note: we don't bother sweeping the LIFO space. SweepOldSpace(&mapSpace_); diff -r 572668ef742b -r e3c851a14f16 src/TypeManager.cpp --- a/src/TypeManager.cpp Tue Dec 25 17:02:07 2012 -0800 +++ b/src/TypeManager.cpp Tue Dec 25 18:13:02 2012 -0800 @@ -28,7 +28,8 @@ TypeManager::TypeManager(Zone *zone) - : zone_(zone) + : zone_(zone), + qualTable_(ZoneAllocatorPolicy()) { } @@ -65,6 +66,9 @@ return false; } + if (!qualTable_.init(32)) + return false; + return true; } @@ -97,6 +101,32 @@ return EnumType::New(zone_, name); } +Type * +TypeManager::qualify(Handle type, TypeQualifiers quals) +{ + assert(!type->hasTypeQualifiers()); + + LookupKey key(type, quals); + + // We can't use findForAdd because a GC could rehash the table. + TypeHashTable::Result r = qualTable_.find(key); + if (r.found()) + return *r; + + Type *quald = Type::NewQualified(zone_, quals, type); + if (!quald) + return NULL; + + // :TODO: assert-no-gc + TypeHashTable::Insert i = qualTable_.findForAdd(key); + assert(!i.found()); + + if (!qualTable_.add(i, quald)) + return NULL; + + return quald; +} + void TypeManager::accept(VirtualObjectVisitor *visitor) { @@ -108,3 +138,17 @@ visitor->visit(referenceTypes_[i].address()); } } + +void +TypeManager::sweep() +{ + for (TypeHashTable::iterator i(&qualTable_); !i.empty(); i.next()) { + Type *obj = *i; + MarkBit bits = HeapChunk::GetMarkBit(obj); + if (HeapChunk::IsWhite(bits)) + i.erase(); + else + assert(HeapChunk::IsBlack(bits)); + } + qualTable_.checkDensity(); +} diff -r 572668ef742b -r e3c851a14f16 src/TypeManager.h --- a/src/TypeManager.h Tue Dec 25 17:02:07 2012 -0800 +++ b/src/TypeManager.h Tue Dec 25 18:13:02 2012 -0800 @@ -21,6 +21,8 @@ #include "Barriers.h" #include "Types.h" +#include "HashTable.h" +#include "AllocatorPolicies.h" #include "VirtualObjectVisitor.h" namespace ke { @@ -29,14 +31,35 @@ class TypeManager { - Zone *zone_; + struct LookupKey + { + Handle type; + TypeQualifiers quals; + + LookupKey(Handle type, TypeQualifiers quals) + : type(type), + quals(quals) + { + } + }; - // Primitive type cache. - Unbarriered voidType_; - Unbarriered stringType_; - Unbarriered uncheckedType_; - Unbarriered primitiveTypes_[PrimitiveTypes_Total]; - Unbarriered referenceTypes_[PrimitiveTypes_Total]; + struct Policy + { + typedef Type * Payload; + + static uint32 hash(const LookupKey &key) { + // We'll need to rehash with moving GC. + return HashPointer(key.type); + } + + static bool matches(const LookupKey &key, Type *type) { + assert(type->hasTypeQualifiers()); + return key.type == type->unqualified() && + key.quals == type->quals(); + } + }; + + typedef HashTable TypeHashTable; public: TypeManager(Zone *zone); @@ -62,6 +85,21 @@ EnumType *newEnum(Handle name); void accept(VirtualObjectVisitor *visitor); + void sweep(); + + Type *qualify(Handle type, TypeQualifiers quals); + + private: + Zone *zone_; + + // Primitive type cache. + Unbarriered voidType_; + Unbarriered stringType_; + Unbarriered uncheckedType_; + Unbarriered primitiveTypes_[PrimitiveTypes_Total]; + Unbarriered referenceTypes_[PrimitiveTypes_Total]; + + TypeHashTable qualTable_; }; } diff -r 572668ef742b -r e3c851a14f16 src/Types.cpp --- a/src/Types.cpp Tue Dec 25 17:02:07 2012 -0800 +++ b/src/Types.cpp Tue Dec 25 18:13:02 2012 -0800 @@ -26,10 +26,10 @@ using namespace ke; void -Type::init(Kind kind) +Type::init(Kind kind, Type *root) { this->kind_ = kind; - this->root_ = this; + this->root_ = root ? root : this; } Type * @@ -77,6 +77,18 @@ return type; } +Type * +Type::NewQualified(Zone *zone, TypeQualifiers qual, Handle root) +{ + Local type(zone, Type::cast(zone->allocate(MapKind_Type, sizeof(Type), Heap::Tenure_Old))); + if (!type) + return NULL; + + type->init(QUALTYPE, root); + type->quals_ = qual; + return type; +} + ArrayType * ArrayType::New(Zone *zone, Handle contained, int elements) { @@ -235,4 +247,3 @@ return ""; } } - diff -r 572668ef742b -r e3c851a14f16 src/Types.h --- a/src/Types.h Tue Dec 25 17:02:07 2012 -0800 +++ b/src/Types.h Tue Dec 25 18:13:02 2012 -0800 @@ -140,7 +140,7 @@ STRUCT }; - void init(Kind kind); + void init(Kind kind, Type *root = NULL); private: Kind kind() { @@ -152,6 +152,7 @@ static Type *NewUnchecked(Zone *zone); static Type *NewPrimitive(Zone *zone, PrimitiveType type); static Type *NewString(Zone *zone); + static Type *NewQualified(Zone *zone, TypeQualifiers qual, Handle type); static Type *cast(Object *obj) { assert(!obj || diff -r 572668ef742b -r e3c851a14f16 src/Zone.cpp --- a/src/Zone.cpp Tue Dec 25 17:02:07 2012 -0800 +++ b/src/Zone.cpp Tue Dec 25 18:13:02 2012 -0800 @@ -180,6 +180,13 @@ stack_.accept(visitor); } +void +Zone::sweepWeakRoots() +{ + symbols_->sweep(); + types()->sweep(); +} + String * Zone::makeSymbol(const char *str, size_t length) { diff -r 572668ef742b -r e3c851a14f16 src/Zone.h --- a/src/Zone.h Tue Dec 25 17:02:07 2012 -0800 +++ b/src/Zone.h Tue Dec 25 18:13:02 2012 -0800 @@ -145,6 +145,7 @@ void endCompilationErrors(); void accept(VirtualObjectVisitor *visitor); + void sweepWeakRoots(); void setPublicFunctionListener(Ke::IPublicFunctionListener *listener); void registerPublic(Handle fun);