Macros | Functions
table.c File Reference

Ordered hash map. More...

#include <string.h>
#include <kuroko/kuroko.h>
#include <kuroko/object.h>
#include <kuroko/value.h>
#include <kuroko/memory.h>
#include <kuroko/table.h>
#include <kuroko/vm.h>
#include <kuroko/threads.h>
#include <kuroko/util.h>
Include dependency graph for table.c:

Go to the source code of this file.

Macros

#define TABLE_MAX_LOAD   3 / 4
 

Functions

void krk_initTable (KrkTable *table)
 
void krk_freeTable (KrkTable *table)
 
int krk_hashValue (KrkValue value, uint32_t *hashOut)
 
void krk_tableAdjustCapacity (KrkTable *table, size_t capacity)
 
int krk_tableSet (KrkTable *table, KrkValue key, KrkValue value)
 
int krk_tableSetExact (KrkTable *table, KrkValue key, KrkValue value)
 
int krk_tableSetIfExists (KrkTable *table, KrkValue key, KrkValue value)
 
void krk_tableAddAll (KrkTable *from, KrkTable *to)
 
int krk_tableGet (KrkTable *table, KrkValue key, KrkValue *value)
 
int krk_tableGet_fast (KrkTable *table, KrkString *str, KrkValue *value)
 
int krk_tableDelete (KrkTable *table, KrkValue key)
 
int krk_tableDeleteExact (KrkTable *table, KrkValue key)
 
KrkString * krk_tableFindString (KrkTable *table, const char *chars, size_t length, uint32_t hash)
 

Detailed Description

Ordered hash map.

The original table implementation was derived from CLox. CLox's tables only supported string keys, but we support arbitrary values, so long as they are hashable.

This implementation maintains the same general API, but take its inspiration from CPython to keep insertion order. The "entries" table is still an array of key-value pairs, but no longer tracks the hash lookup for the map. Instead, the entries array keeps a strict insertion ordering, with deleted entries replaced with sentinel values representing gaps. A separate "indexes" table maps hash slots to their associated key-value pairs, or to -1 or -2 to represent unused and tombstone slots, respectively.

When resizing a table, the entries array is rewritten and gaps are removed. Simultaneously, the new index entries are populated.

Definition in file table.c.