hash_table.c File Reference

#include "hash_table.h"
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

Go to the source code of this file.

Classes
struct	hash_table
struct	ht_slot_t

Macros
#define	HT_INITIAL_CAPACITY   16
#define	HT_MAX_LOAD   0.75

Enumerations
enum	slot_state_t { SLOT_EMPTY , SLOT_OCCUPIED , SLOT_TOMBSTONE }

Functions
static uint64_t	djb2 (const char *s)
size_t	ht_capacity (const hash_table_t *ht)
bool	ht_contains (const hash_table_t *ht, const char *key)
hash_table_t *	ht_create (void)
void	ht_destroy (hash_table_t *ht)
bool	ht_get (const hash_table_t *ht, const char *key, int *out)
bool	ht_remove (hash_table_t *ht, const char *key)
static bool	ht_resize (hash_table_t *ht, size_t new_cap)
bool	ht_set (hash_table_t *ht, const char *key, int value)
size_t	ht_size (const hash_table_t *ht)
static size_t	probe (const ht_slot_t *slots, size_t cap, const char *key)

Detailed Description

Open-addressing hash table with linear probing and tombstone deletion. Capacity is a power of two so we can replace % capacity with a mask.

Definition in file hash_table.c.

Macro Definition Documentation

HT_INITIAL_CAPACITY

#define HT_INITIAL_CAPACITY   16

Definition at line 13 of file hash_table.c.

HT_MAX_LOAD

#define HT_MAX_LOAD   0.75

Definition at line 14 of file hash_table.c.

Enumeration Type Documentation

slot_state_t

enum slot_state_t

Enumerator
SLOT_EMPTY
SLOT_OCCUPIED
SLOT_TOMBSTONE

Definition at line 16 of file hash_table.c.

Function Documentation

djb2()

static uint64_t djb2 ( const char *  s )

static

Definition at line 31 of file hash_table.c.

Referenced by probe().

ht_capacity()

size_t ht_capacity

(

const hash_table_t *

ht

)

Definition at line 123 of file hash_table.c.

References hash_table::capacity.

Referenced by main().

ht_contains()

bool ht_contains	(	const hash_table_t *	ht,
		const char *	key
	)

Definition at line 118 of file hash_table.c.

References ht_get().

ht_create()

hash_table_t * ht_create

(

void

)

Definition at line 40 of file hash_table.c.

References hash_table::capacity, HT_INITIAL_CAPACITY, hash_table::size, and hash_table::slots.

Referenced by main().

ht_destroy()

void ht_destroy

(

hash_table_t *

ht

)

Definition at line 50 of file hash_table.c.

References hash_table::capacity, ht_slot_t::key, SLOT_OCCUPIED, hash_table::slots, and ht_slot_t::state.

Referenced by main().

ht_get()

bool ht_get	(	const hash_table_t *	ht,
		const char *	key,
		int *	out
	)

Writes *out and returns true if found, otherwise false.

Definition at line 99 of file hash_table.c.

References hash_table::capacity, probe(), SLOT_OCCUPIED, hash_table::slots, ht_slot_t::state, and ht_slot_t::value.

Referenced by ht_contains(), and main().

ht_remove()

bool ht_remove	(	hash_table_t *	ht,
		const char *	key
	)

Definition at line 107 of file hash_table.c.

References hash_table::capacity, ht_slot_t::key, probe(), hash_table::size, SLOT_OCCUPIED, SLOT_TOMBSTONE, hash_table::slots, and ht_slot_t::state.

Referenced by main().

ht_resize()

static bool ht_resize ( hash_table_t *  ht, size_t  new_cap  )

static

Definition at line 125 of file hash_table.c.

References hash_table::capacity, ht_slot_t::key, probe(), SLOT_OCCUPIED, hash_table::slots, and ht_slot_t::state.

Referenced by ht_set().

ht_set()

bool ht_set	(	hash_table_t *	ht,
		const char *	key,
		int	value
	)

Inserts or updates key → value. Returns false on allocation failure.

Definition at line 77 of file hash_table.c.

References hash_table::capacity, HT_MAX_LOAD, ht_resize(), ht_slot_t::key, probe(), hash_table::size, SLOT_OCCUPIED, hash_table::slots, ht_slot_t::state, and ht_slot_t::value.

Referenced by main().

ht_size()

size_t ht_size

(

const hash_table_t *

ht

)

Definition at line 122 of file hash_table.c.

References hash_table::size.

Referenced by main().

probe()

static size_t probe ( const ht_slot_t *  slots, size_t  cap, const char *  key  )

static

Returns the slot index for key (insert position or existing match).

Definition at line 60 of file hash_table.c.

References djb2(), SLOT_EMPTY, SLOT_OCCUPIED, and SLOT_TOMBSTONE.

Referenced by ht_get(), ht_remove(), ht_resize(), and ht_set().