generics.collections

Units

Class Hierarchy

Classes, Interfaces, Objects and Records

Types

Variables

Constants

Functions and Procedures

Identifiers

Class TDeamortizedDArrayCuckooMap

Description
Hierarchy
Internal Classes and Records
Internal Types
Fields
Methods
Properties

Unit

Generics.Collections

Declaration

type TDeamortizedDArrayCuckooMap<TKey,TValue,THashFactory,TCuckooCfg> = class(TCustomDictionary<TKey,TValue,THashFactory>)

Description

more info : http://arxiv.org/abs/0903.0391

Hierarchy

Overview

Internal Classes and Records

Private TCDM = class(TOpenAddressingSH<TKey,TEmptyRecord,TDefaultHashFactory,TLinearProbing>)
Private TItem = record
Public TKeyCollection = class(TDictionaryEnumerable<TKeyEnumerator,TPKeyEnumerator,TKey,TKey,TValue,THashFactory>)
Public TKeyEnumerator = class(TDeamortizedDArrayCuckooMapEnumerator<TKey,TKey,TValue,THashFactory,TCuckooCfg>)
Public TPairEnumerator = class(TDeamortizedDArrayCuckooMapEnumerator<TDictionaryPair,TKey,TValue,THashFactory,TCuckooCfg>)
Public TPKeyEnumerator = class(TDeamortizedDArrayCuckooMapEnumerator<PKey,TKey,TValue,THashFactory,TCuckooCfg>)
Private TPointersEnumerator = class(TDeamortizedDArrayPointersEnumerator<TCuckooCfg,TItemsArray,TItemsDArray,TQueueDictionary,PDictionaryPair>)
Public TPValueEnumerator = class(TDeamortizedDArrayCuckooMapEnumerator<PValue,TKey,TValue,THashFactory,TCuckooCfg>)
Private TQueueDictionary = class(TOpenAddressingLP<TKey,TValueForQueue,TDefaultHashFactory,TLinearProbing>)
Public TValueCollection = class(TDictionaryEnumerable<TValueEnumerator,TPValueEnumerator,TValue,TKey,TValue,THashFactory>)
Public TValueEnumerator = class(TDeamortizedDArrayCuckooMapEnumerator<TValue,TKey,TValue,THashFactory,TCuckooCfg>)

Internal Types

Private PItem = ˆTItem;
Public PPointersCollection = ˆTPointersCollection;
Private TItemsArray = array of TItem;
Private TItemsDArray = array[0..Pred(TCuckooCfg.D)] of TItemsArray;
Private TPointersCollection = TDeamortizedDArrayPointersCollection<TPointersEnumerator, TItemsDArray, TQueueDictionary, PDictionaryPair>;
Private TValueForQueue = TItem;

Fields

Private internal const LR_NIL = -1;
Private internal const LR_QUEUE = -2;
Private var FItems: TItemsDArray;
Private FQueue: TQueueDictionary;
Private FCDM: TCDM;
Private FItemsThreshold: SizeInt;
Private var CUCKOO_SIGN: UInt32;
Private var CUCKOO_INDEX_SIZE: UInt32;
Private var CUCKOO_HASH_SIGN: UInt32;

Methods

Private procedure Resize(ANewSize: SizeInt);
Private procedure Rehash(ASizePow2: SizeInt);
Private procedure PrepareAddingItem;
Protected procedure UpdateItemsThreshold(ASize: SizeInt); override;
Protected function Lookup(constref AKey: TKey; var AHashListOrIndex: PUInt32): SizeInt; inline; overload;
Protected function Lookup(constref AItems: TItemsDArray; constref AKey: TKey; var AHashListOrIndex: PUInt32): SizeInt; virtual; overload;
Public function GetEnumerator: TPairEnumerator; reintroduce;
Private function GetKeys: TKeyCollection;
Private function GetValues: TValueCollection;
Private function GetPointers: PPointersCollection; inline;
Private function GetItem(const AKey: TKey): TValue; inline;
Private procedure SetItem(const AKey: TKey; const AValue: TValue); overload; inline;
Private procedure SetItem(constref AValue: TValue; const AHashListOrIndex: PUInt32; ALookupResult: SizeInt); overload;
Private procedure AddItem(constref AItems: TItemsDArray; constref AKey: TKey; constref AValue: TValue; const AHashList: PUInt32); overload;
Private procedure DoAdd(const AKey: TKey; const AValue: TValue; const AHashList: PUInt32); overload; inline;
Private function DoRemove(const AHashListOrIndex: PUInt32; ALookupResult: SizeInt; ACollectionNotification: TCollectionNotification): TValue;
Private function GetQueueCount: SizeInt;
Protected procedure SetCapacity(ACapacity: SizeInt); override;
Protected function DoGetEnumerator: TEnumerator<TDictionaryPair>; override;
Protected procedure SetMaxLoadFactor(AValue: single); override;
Protected function GetLoadFactor: single; override;
Protected function GetCapacity: SizeInt; override;
Public constructor Create; override; overload;
Public constructor Create(ACapacity: SizeInt); override; overload;
Public constructor Create(ACollection: TEnumerable<TDictionaryPair>); override; overload;
Public constructor Create(ACapacity: SizeInt; const AComparer: IExtendedEqualityComparer<TKey>); virtual; overload;
Public constructor Create(const AComparer: IExtendedEqualityComparer<TKey>); overload;
Public constructor Create(ACollection: TEnumerable<TDictionaryPair>; const AComparer: IExtendedEqualityComparer<TKey>); virtual; overload;
Public destructor Destroy; override;
Public procedure Add(constref APair: TPair<TKey, TValue>); override; overload;
Public procedure Add(constref AKey: TKey; constref AValue: TValue); overload;
Public procedure Remove(constref AKey: TKey);
Public function ExtractPair(constref AKey: TKey): TPair<TKey, TValue>;
Public procedure Clear; override;
Public procedure TrimExcess;
Public function TryGetValue(constref AKey: TKey; out AValue: TValue): Boolean;
Public procedure AddOrSetValue(constref AKey: TKey; constref AValue: TValue);
Public function ContainsKey(constref AKey: TKey): Boolean; inline;
Public function ContainsValue(constref AValue: TValue): Boolean; overload;
Public function ContainsValue(constref AValue: TValue; const AEqualityComparer: IEqualityComparer<TValue>): Boolean; virtual; overload;
Public procedure GetMemoryLayout(const AOnGetMemoryLayoutKeyPosition: TOnGetMemoryLayoutKeyPosition);

Properties

Public property Items[Index:TKey]: TValue read GetItem write SetItem;
Public property Keys: TKeyCollection read GetKeys;
Public property Values: TValueCollection read GetValues;
Public property Ptr: PPointersCollection read GetPointers;
Public property QueueCount: SizeInt read GetQueueCount;

Description

Internal Types

Private PItem = ˆTItem;
 
Public PPointersCollection = ˆTPointersCollection;
 
Private TItemsArray = array of TItem;
 
Private TItemsDArray = array[0..Pred(TCuckooCfg.D)] of TItemsArray;
 
Private TPointersCollection = TDeamortizedDArrayPointersCollection<TPointersEnumerator, TItemsDArray, TQueueDictionary, PDictionaryPair>;
 
Private TValueForQueue = TItem;
 

Fields

Private internal const LR_NIL = -1;

Lookup Result

Private internal const LR_QUEUE = -2;
 
Private var FItems: TItemsDArray;
 
Private FQueue: TQueueDictionary;
 
Private FCDM: TCDM;

probably can be optimized - hash TItem give information from TItem.Hash for cuckoo ... currently is kept in "TQueueDictionary = class(TOpenAddressingSH<TKey, TItem, ...>"

Private FItemsThreshold: SizeInt;

cycle-detection mechanism

Private var CUCKOO_SIGN: UInt32;

class

Private var CUCKOO_INDEX_SIZE: UInt32;

class

Private var CUCKOO_HASH_SIGN: UInt32;

class

Methods

Private procedure Resize(ANewSize: SizeInt);

CUCKOO_MAX_ITEMS_LENGTH: <- to do : calc max length for items based on CUCKOO sign maybe some CDM bloom filter?

Private procedure Rehash(ASizePow2: SizeInt);
 
Private procedure PrepareAddingItem;
 
Protected procedure UpdateItemsThreshold(ASize: SizeInt); override;
 
Protected function Lookup(constref AKey: TKey; var AHashListOrIndex: PUInt32): SizeInt; inline; overload;
 
Protected function Lookup(constref AItems: TItemsDArray; constref AKey: TKey; var AHashListOrIndex: PUInt32): SizeInt; virtual; overload;
 
Public function GetEnumerator: TPairEnumerator; reintroduce;

bug #24283 - workaround related to lack of DoGetEnumerator

Private function GetKeys: TKeyCollection;
 
Private function GetValues: TValueCollection;
 
Private function GetPointers: PPointersCollection; inline;
 
Private function GetItem(const AKey: TKey): TValue; inline;
 
Private procedure SetItem(const AKey: TKey; const AValue: TValue); overload; inline;
 
Private procedure SetItem(constref AValue: TValue; const AHashListOrIndex: PUInt32; ALookupResult: SizeInt); overload;
 
Private procedure AddItem(constref AItems: TItemsDArray; constref AKey: TKey; constref AValue: TValue; const AHashList: PUInt32); overload;
 
Private procedure DoAdd(const AKey: TKey; const AValue: TValue; const AHashList: PUInt32); overload; inline;
 
Private function DoRemove(const AHashListOrIndex: PUInt32; ALookupResult: SizeInt; ACollectionNotification: TCollectionNotification): TValue;
 
Private function GetQueueCount: SizeInt;
 
Protected procedure SetCapacity(ACapacity: SizeInt); override;
 
Protected function DoGetEnumerator: TEnumerator<TDictionaryPair>; override;

bug #24283 - can't descadent from TEnumerable

Protected procedure SetMaxLoadFactor(AValue: single); override;
 
Protected function GetLoadFactor: single; override;
 
Protected function GetCapacity: SizeInt; override;
 
Public constructor Create; override; overload;

TODO: function TryFlushQueue(ACount: SizeInt): SizeInt;

Public constructor Create(ACapacity: SizeInt); override; overload;
 
Public constructor Create(ACollection: TEnumerable<TDictionaryPair>); override; overload;
 
Public constructor Create(ACapacity: SizeInt; const AComparer: IExtendedEqualityComparer<TKey>); virtual; overload;
 
Public constructor Create(const AComparer: IExtendedEqualityComparer<TKey>); overload;
 
Public constructor Create(ACollection: TEnumerable<TDictionaryPair>; const AComparer: IExtendedEqualityComparer<TKey>); virtual; overload;
 
Public destructor Destroy; override;
 
Public procedure Add(constref APair: TPair<TKey, TValue>); override; overload;
 
Public procedure Add(constref AKey: TKey; constref AValue: TValue); overload;
 
Public procedure Remove(constref AKey: TKey);
 
Public function ExtractPair(constref AKey: TKey): TPair<TKey, TValue>;
 
Public procedure Clear; override;
 
Public procedure TrimExcess;
 
Public function TryGetValue(constref AKey: TKey; out AValue: TValue): Boolean;
 
Public procedure AddOrSetValue(constref AKey: TKey; constref AValue: TValue);
 
Public function ContainsKey(constref AKey: TKey): Boolean; inline;
 
Public function ContainsValue(constref AValue: TValue): Boolean; overload;
 
Public function ContainsValue(constref AValue: TValue; const AEqualityComparer: IEqualityComparer<TValue>): Boolean; virtual; overload;
 
Public procedure GetMemoryLayout(const AOnGetMemoryLayoutKeyPosition: TOnGetMemoryLayoutKeyPosition);
 

Properties

Public property Items[Index:TKey]: TValue read GetItem write SetItem;
 
Public property Keys: TKeyCollection read GetKeys;
 
Public property Values: TValueCollection read GetValues;
 
Public property Ptr: PPointersCollection read GetPointers;
 
Public property QueueCount: SizeInt read GetQueueCount;
 
Generated by PasDoc 0.15.0.