AtomTable
From OpenCog
class AtomTable {
private:
// linked lists for each kind of index
Handle* typeIndex;
Handle* targetTypeIndex;
Handle* nameIndex;
Handle* importanceIndex;
HandleIterator** iterators;
int iteratorsSize;
void lockIterators();
void unlockIterators();
public:
AtomTable();
void registerIterator(HandleIterator*);
void unregisterIterator(HandleIterator*);
HandleIterator* getHandleIterator();
HandleIterator* getHandleIterator(Type, bool subclass = false);
HandleEntry* makeSet(HandleEntry*, Handle, int);
HandleEntry* buildSet(Type, bool, Handle(AtomTable::*)(Type), int);
Handle getTypeIndexHead(Type);
Handle getTargetTypeIndexHead(Type);
Handle getNameIndexHead(char*);
Handle getImportanceIndexHead(int);
Handle getHandle(char*, Type);
HandleEntry* getHandleSet(Type, bool subclass = false);
HandleEntry* getHandleSet(Type, Type, bool subclass = false,
bool targetSubclass = false);
HandleEntry* getHandleSet(Handle, Type type = ATOM,
bool subclass = true);
HandleEntry* getHandleSet(Handle*, Type*, bool*, Arity,
Type type = ATOM, bool subclass = true);
HandleEntry* getHandleSet(char*, Type type = ATOM,
bool subclass = true);
HandleEntry* getHandleSet(char*, Type, Type type = ATOM,
bool subclass = true);
HandleEntry* getHandleSet(char**, Type*, bool*, Arity,
Type type = ATOM, bool subclass = true);
HandleEntry* getHandleSet(float, float upperBound = 1);
void updateImportanceIndex(Atom*, int);
Handle add(Atom*);
void merge(Atom*, Atom*);
void remove(Handle);
static unsigned int importanceBin(float);
static float importanceBinMeanValue(unsigned int);
};
The searching indexes are single linked lists which contain Atoms that share some property. There are four different properties:
- Atom's type
There is one linked list for each possible Atom type. The heads of each list is stored in an array indexed by the type itself.
- Atom's name
Atoms are inserted in a hash map which uses Atom's name as key. All the unnamed Atoms are kept in the same bucket. Collisions inside buckets are managed with linked lists.
- Atom's importance
Importance is divided in several ranges and there is one linked lists for each range containing all Atoms which have its importance falling in that range.
- Outgoing type
Type of the atoms in the outgoing set of the Atom (referred in code comments as "target type").
Again, there is one linked list for each possible Atom type. The heads of each list are stored in an array indexed by the type itself. All the linked lists uses Atoms directly. Atoms have fields to keep the next element of each list. Thus, each Atom participate in several linked lists. The first three indexes are very simple, each Atom has a pointer to the next Atom of the same type, another one to the next Atom in the same bucket in the name hash map and another one to the next Atom in the same importance range list. The last index is trickier but can be clarified using an example: a Link which links a PredicateNode to two WordSenseNodes (arity = 3) will have an array with 2 positions; in one of its positions, it keeps a pointer to the next Atom which have a PredicateNode as a target type and in the other position it keeps a pointer to the next Atom which have a WordSenseNode as a target type.
