cachetable

README

CacheTable

A quick and naive golang implementation of a CacheTable as described in Fabian "ryg" Giesen's blog

Based on the naive hashmap code of Prakhar Srivastav.

Purpose

It's a Hashtable like the golang map with constrained or constant memory use and an upper bound on lookup time.

The downside, is that older elements will get overwritten in time.

Usage

package main

import (
    "fmt"
    "github.com/btittelbach/cachetable"
)

func main() {
    /// create the cachetable with
    /// - 100 buckets
    /// - max 20 elements per bucket
    /// - immediately allocated memory for all buckets
    h, _ := cachetable.NewCacheTable(100,20,true)
    keys := []string{"alpha", "beta", "charlie", "gamma", "delta"}

    // add the keys
    for _, key := range keys {
        h.Set(key, len(key))
    }

    fmt.Println("The load factor is:", h.Load())

    // retrieve the keys
    for _, key := range keys {
        val, present := h.Get(key)
        if present {
            fmt.Println("Key:", key, "->", "Value:", val.Value.(int))
        } else {
            fmt.Println(key, "is not present")
        }
    }

    // delete a key
    fmt.Println(h.Delete("alpha"))
    _, present := h.Get("alpha")
    if present {
        fmt.Println("The key's still there")
    } else {
        fmt.Println("Value associated with alpha deleted")
    }
}

Documentation

Index

• Constants
• type CacheTable
  • func NewCacheTable(numbuckets, bucketcapacity int, preallocatemem bool) (*CacheTable, error)
  • func (h *CacheTable) BucketCapacity() int
  • func (h *CacheTable) Capacity() int
  • func (h *CacheTable) Delete(key string) (*Node, bool)
  • func (h *CacheTable) Get(key string) (*Node, bool)
  • func (h *CacheTable) Len() int
  • func (h *CacheTable) Load() float32
  • func (h *CacheTable) Set(key string, value interface{})
• type Node

Constants

const MaxUint uint = 1<<bits.UintSize - 1

Types

type CacheTable

type CacheTable struct {
	// contains filtered or unexported fields
}

CacheTable implemented with a fixed bucketcapacity. removes oldest element in bucket once bucket reaches bucketcapacity

func NewCacheTable

func NewCacheTable(numbuckets, bucketcapacity int, preallocatemem bool) (*CacheTable, error)

NewCacheTable is the constuctor that returns a new CacheTable of a fixed size returns an error when a size of 0 is provided

func (*CacheTable) BucketCapacity

func (h *CacheTable) BucketCapacity() int

BucketCapacity returns the bucket size of the cachetable

func (*CacheTable) Capacity

func (h *CacheTable) Capacity() int

Capacity returns the overall size of the cachetable

func (*CacheTable) Delete

func (h *CacheTable) Delete(key string) (*Node, bool)

Delete the value associated with key in the cachetable

func (*CacheTable) Get

func (h *CacheTable) Get(key string) (*Node, bool)

Get returns the value associated with a key in the cachetable, and an error indicating whether the value exists

func (*CacheTable) Len

func (h *CacheTable) Len() int

Len returns the count of the elements in the cachetable

func (*CacheTable) Load

func (h *CacheTable) Load() float32

Load returns the load factor of the cachetable

func (*CacheTable) Set

func (h *CacheTable) Set(key string, value interface{})

Set the value for an associated key in the cachetable this always success as it will just overwrite the oldest element in the bucket

type Node

type Node struct {
	Value interface{}
	// contains filtered or unexported fields
}

Node which is stored at each level