set.ts

/// <reference path="./rt/index.d.ts" />

import{HASH}from"./util/hash";

// A deterministic hash set based on CloseTable from https://github.com/jorendorff/dht

// @ts-ignore: decorator
@inlineconstINITIAL_CAPACITY=4;

// @ts-ignore: decorator
@inlineconstFILL_FACTOR_N=8;

// @ts-ignore: decorator
@inlineconstFILL_FACTOR_D=3;

// @ts-ignore: decorator
@inlineconstFREE_FACTOR_N=3;

// @ts-ignore: decorator
@inlineconstFREE_FACTOR_D=4;

/** Structure of a set entry. */
@unmanagedclassSetEntry<K>{
key: K;
taggedNext: usize;// LSB=1 indicates EMPTY
}

/** Empty bit. */
// @ts-ignore: decorator
@inlineconstEMPTY: usize=1<<0;

/** Size of a bucket. */
// @ts-ignore: decorator
@inlineconstBUCKET_SIZE=sizeof<usize>();

/** Computes the alignment of an entry. */
// @ts-ignore: decorator
@inline
functionENTRY_ALIGN<T>(): usize{
// can align to 4 instead of 8 if 32-bit and K is <= 32-bits
constalign=(sizeof<T>()>sizeof<usize>() ? sizeof<T>() : sizeof<usize>())-1;
returnalign;
}

/** Computes the aligned size of an entry. */
// @ts-ignore: decorator
@inline
functionENTRY_SIZE<T>(): usize{
constalign=ENTRY_ALIGN<T>();
constsize=(offsetof<SetEntry<T>>()+align)&~align;
returnsize;
}

exportclassSet<T>{

// buckets referencing their respective first entry, usize[bucketsMask + 1]
privatebuckets: ArrayBuffer=newArrayBuffer(INITIAL_CAPACITY*<i32>BUCKET_SIZE);
privatebucketsMask: u32=INITIAL_CAPACITY-1;

// entries in insertion order, SetEntry<K>[entriesCapacity]
privateentries: ArrayBuffer=newArrayBuffer(INITIAL_CAPACITY*<i32>ENTRY_SIZE<T>());
privateentriesCapacity: i32=INITIAL_CAPACITY;
privateentriesOffset: i32=0;
privateentriesCount: i32=0;

constructor(){
/* nop */
}

getsize(): i32{
returnthis.entriesCount;
}

clear(): void{
this.buckets=newArrayBuffer(INITIAL_CAPACITY*<i32>BUCKET_SIZE);
this.bucketsMask=INITIAL_CAPACITY-1;
this.entries=newArrayBuffer(INITIAL_CAPACITY*<i32>ENTRY_SIZE<T>());
this.entriesCapacity=INITIAL_CAPACITY;
this.entriesOffset=0;
this.entriesCount=0;
}

privatefind(key: T,hashCode: u32): SetEntry<T>|null{
letentry=load<SetEntry<T>>(// unmanaged!
changetype<usize>(this.buckets)+<usize>(hashCode&this.bucketsMask)*BUCKET_SIZE
);
while(entry){
lettaggedNext=entry.taggedNext;
if(!(taggedNext&EMPTY)&&entry.key==key)returnentry;
entry=changetype<SetEntry<T>>(taggedNext&~EMPTY);
}
returnnull;
}

 @operator("[]")
has(key: T): bool{
returnthis.find(key,HASH<T>(key))!=null;
}

add(key: T): this {
lethashCode=HASH<T>(key);
letentry=this.find(key,hashCode);// unmanaged!
if(!entry){
// check if rehashing is necessary
if(this.entriesOffset==this.entriesCapacity){
this.rehash(
this.entriesCount<this.entriesCapacity*FREE_FACTOR_N/FREE_FACTOR_D
 ? this.bucketsMask// just rehash if 1/4+ entries are empty
 : (this.bucketsMask<<1)|1// grow capacity to next 2^N
);
}
// append new entry
entry=changetype<SetEntry<T>>(changetype<usize>(this.entries)+<usize>(this.entriesOffset++)*ENTRY_SIZE<T>());
entry.key=key;
if(isManaged<T>()){
__link(changetype<usize>(this),changetype<usize>(key),true);
}
++this.entriesCount;
// link with previous entry in bucket
letbucketPtrBase=changetype<usize>(this.buckets)+<usize>(hashCode&this.bucketsMask)*BUCKET_SIZE;
entry.taggedNext=load<usize>(bucketPtrBase);
store<usize>(bucketPtrBase,changetype<usize>(entry));
}
returnthis;
}

 @operator("[]=")
private__set(key: T,value: bool): void{
if(value)this.add(key);
elsethis.delete(key);
}

delete(key: T): bool{
letentry=this.find(key,HASH<T>(key));// unmanaged!
if(!entry)returnfalse;
entry.taggedNext|=EMPTY;
--this.entriesCount;
// check if rehashing is appropriate
lethalfBucketsMask=this.bucketsMask>>1;
if(
halfBucketsMask+1>=max<u32>(INITIAL_CAPACITY,this.entriesCount)&&
this.entriesCount<this.entriesCapacity*FREE_FACTOR_N/FREE_FACTOR_D
)this.rehash(halfBucketsMask);
returntrue;
}

privaterehash(newBucketsMask: u32): void{
letnewBucketsCapacity=<i32>(newBucketsMask+1);
letnewBuckets=newArrayBuffer(newBucketsCapacity*<i32>BUCKET_SIZE);
letnewEntriesCapacity=newBucketsCapacity*FILL_FACTOR_N/FILL_FACTOR_D;
letnewEntries=newArrayBuffer(newEntriesCapacity*<i32>ENTRY_SIZE<T>());

// copy old entries to new entries
letoldPtr=changetype<usize>(this.entries);
letoldEnd=oldPtr+<usize>this.entriesOffset*ENTRY_SIZE<T>();
letnewPtr=changetype<usize>(newEntries);
while(oldPtr!=oldEnd){
letoldEntry=changetype<SetEntry<T>>(oldPtr);// unmanaged!
if(!(oldEntry.taggedNext&EMPTY)){
letnewEntry=changetype<SetEntry<T>>(newPtr);// unmanaged!
letoldEntryKey=oldEntry.key;
newEntry.key=oldEntryKey;
letnewBucketIndex=HASH<T>(oldEntryKey)&newBucketsMask;
letnewBucketPtrBase=changetype<usize>(newBuckets)+<usize>newBucketIndex*BUCKET_SIZE;
newEntry.taggedNext=load<usize>(newBucketPtrBase);
store<usize>(newBucketPtrBase,newPtr);
newPtr+=ENTRY_SIZE<T>();
}
oldPtr+=ENTRY_SIZE<T>();
}

this.buckets=newBuckets;
this.bucketsMask=newBucketsMask;
this.entries=newEntries;
this.entriesCapacity=newEntriesCapacity;
this.entriesOffset=this.entriesCount;
}

values(): T[]{
// FIXME: this is preliminary, needs iterators/closures
letstart=changetype<usize>(this.entries);
letsize=this.entriesOffset;
letvalues=newArray<T>(size);
letlength=0;
for(leti=0;i<size;++i){
letentry=changetype<SetEntry<T>>(start+<usize>i*ENTRY_SIZE<T>());
if(!(entry.taggedNext&EMPTY)){
unchecked(values[length++]=entry.key);
}
}
values.length=length;
returnvalues;
}

toString(): string{
return"[object Set]";
}

// RT integration

 @unsafeprivate__visit(cookie: u32): void{
__visit(changetype<usize>(this.buckets),cookie);
letentries=changetype<usize>(this.entries);
if(isManaged<T>()){
letcur=entries;
letend=cur+<usize>this.entriesOffset*ENTRY_SIZE<T>();
while(cur<end){
letentry=changetype<SetEntry<T>>(cur);
if(!(entry.taggedNext&EMPTY)){
letval=changetype<usize>(entry.key);
if(isNullable<T>()){
if(val)__visit(val,cookie);
}else__visit(val,cookie);
}
cur+=ENTRY_SIZE<T>();
}
}
__visit(entries,cookie);
}
}