Write-Once hash table for string to string mappings. More...

#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <zlib.h>
#include <errno.h>
#include "utils/log.h"
#include "utils/hashtable.h"

Include dependency graph for hashtable.c:

Data Structures
struct	hash_entry

struct	hash_table

Macros
#define	LINE_BUFFER_SIZE 512
	maximum length of line for file or inline add More...

Functions
static unsigned int	hash_string_fnv (const char datum, unsigned int len)
	Hash a string, returning a 32bit value. More...

static nserror	process_line (struct hash_table hash, uint8_t ln, int lnlen)
	process a line of input. More...

static nserror	hash_add_inline_plain (struct hash_table ht, const uint8_t data, size_t size)
	adds key/value pairs to a hash from a memory area More...

static nserror	hash_add_inline_gzip (struct hash_table ht, const uint8_t data, size_t size)
	adds key/value pairs to a hash from a compressed memory area More...

struct hash_table *	hash_create (unsigned int chains)
	Create a new hash table. More...

void	hash_destroy (struct hash_table *ht)
	Destroys a hash table. More...

bool	hash_add (struct hash_table ht, const char key, const char *value)
	Adds a key/value pair to a hash table. More...

const char *	hash_get (struct hash_table ht, const char key)
	Looks up a the value associated with with a key from a specific hash table. More...

nserror	hash_add_file (struct hash_table ht, const char path)
	Add key/value pairs to a hash table with data from a file. More...

nserror	hash_add_inline (struct hash_table ht, const uint8_t data, size_t size)
	Add key/value pairs to a hash table with data from a memory buffer. More...

Detailed Description

Write-Once hash table for string to string mappings.

This implementation is unit tested, if you make changes please ensure the tests continute to pass and if possible, through valgrind to make sure there are no memory leaks or invalid memory accesses. If you add new functionality, please include a test for it that has good coverage along side the other tests.

Definition in file hashtable.c.

Macro Definition Documentation

◆ LINE_BUFFER_SIZE

#define LINE_BUFFER_SIZE 512

maximum length of line for file or inline add

Definition at line 54 of file hashtable.c.

Function Documentation

◆ hash_add()

bool hash_add	(	struct hash_table *	ht,
		const char *	key,
		const char *	value
	)

Adds a key/value pair to a hash table.

If the key you're adding is already in the hash table, it does not replace it, but it does take precedent over it. The old key/value pair will be inaccessable but still in memory until hash_destroy() is called on the hash table.

Parameters

ht	The hash table context to add the key/value pair to.
key	The key to associate the value with. A copy is made.
value	The value to associate the key with. A copy is made.

Returns: true if the add succeeded, false otherwise. (Failure most likely indicates insufficent memory to make copies of the key and value.

Definition at line 303 of file hashtable.c.

References hash_table::chain, hash_string_fnv(), hash_entry::key_length, hash_table::nchains, hash_entry::next, NSLOG, and hash_entry::pairing.

Referenced by gtk_fetch_filetype_init(), messages_create_ctx(), monkey_fetch_filetype_init(), and process_line().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hash_add_file()

nserror hash_add_file	(	struct hash_table *	ht,
		const char *	path
	)

Add key/value pairs to a hash table with data from a file.

The file should be formatted as a series of lines terminated with newline character. Each line should contain a key/value pair separated by a colon. If a line is empty or starts with a # character it will be ignored.

The file may be optionally gzip compressed.

Parameters

ht	The hash table context to add the key/value pairs to.
path	Path to file with key/value pairs in.

Returns: NSERROR_OK on success else error code

Definition at line 363 of file hashtable.c.

References LINE_BUFFER_SIZE, NSERROR_BAD_PARAMETER, NSERROR_NOT_FOUND, NSERROR_OK, NSLOG, path(), and process_line().

Referenced by messages_load_ctx(), and nsgtk_accelerator_init().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hash_add_inline()

nserror hash_add_inline	(	struct hash_table *	ht,
		const uint8_t *	data,
		size_t	size
	)

Add key/value pairs to a hash table with data from a memory buffer.

The data format is the same as in hash_add_file() but held in memory

The data may optionally be gzip compressed.

Parameters

ht	The hash table context to add the key/value pairs to.
data	Source of key/value pairs
size	length of data

Returns: NSERROR_OK on success else error code

Definition at line 399 of file hashtable.c.

References hash_add_inline_gzip(), and hash_add_inline_plain().

Referenced by messages_add_from_inline(), and nsgtk_accelerator_init().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hash_add_inline_gzip()

static nserror hash_add_inline_gzip	(	struct hash_table *	ht,
		const uint8_t *	data,
		size_t	size
	)

static

adds key/value pairs to a hash from a compressed memory area

Definition at line 180 of file hashtable.c.

References LINE_BUFFER_SIZE, NSERROR_INVALID, NSERROR_OK, NSLOG, and process_line().

Referenced by hash_add_inline().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hash_add_inline_plain()

static nserror hash_add_inline_plain	(	struct hash_table *	ht,
		const uint8_t *	data,
		size_t	size
	)

static

adds key/value pairs to a hash from a memory area

Definition at line 141 of file hashtable.c.

References LINE_BUFFER_SIZE, NSERROR_OK, NSLOG, and process_line().

Referenced by hash_add_inline().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hash_create()

struct hash_table * hash_create ( unsigned int chains )

Create a new hash table.

Allocate a new hash table and return a context for it. The memory consumption of a hash table is approximately 8 + (nchains * 12) bytes if it is empty.

Parameters

chains Number of chains/buckets this hash table will have. This should be a prime number, and ideally a prime number just over a power of two, for best performance and distribution.

Returns: struct hash_table containing the context of this hash table or NULL if there is insufficent memory to create it and its chains.

Definition at line 254 of file hashtable.c.

References hash_table::chain, hash_table::nchains, and NSLOG.

Referenced by gtk_fetch_filetype_init(), messages_create_ctx(), monkey_fetch_filetype_init(), and nsgtk_accelerator_init().

Here is the caller graph for this function:

◆ hash_destroy()

void hash_destroy ( struct hash_table * ht )

Destroys a hash table.

Destroy a hash table freeing all memory associated with it.

Parameters

ht	Hash table to destroy. After the function returns, this will no longer be valid.

Definition at line 278 of file hashtable.c.

References hash_table::chain, hash_table::nchains, hash_entry::next, and hash_entry::pairing.

Referenced by gtk_fetch_filetype_fin(), messages_destroy_ctx(), messages_load_ctx(), and monkey_fetch_filetype_fin().

Here is the caller graph for this function:

◆ hash_get()

const char * hash_get	(	struct hash_table *	ht,
		const char *	key
	)

Looks up a the value associated with with a key from a specific hash table.

Parameters

ht	The hash table context to look up the key in.
key	The key to search for.

Returns: The value associated with the key, or NULL if it was not found.

Definition at line 339 of file hashtable.c.

References hash_table::chain, hash_string_fnv(), hash_entry::key_length, hash_table::nchains, hash_entry::next, and hash_entry::pairing.

Referenced by fetch_filetype(), messages_get_buff(), messages_get_ctx(), monkey_fetch_filetype(), and nsgtk_accelerator_get_desc().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hash_string_fnv()

static unsigned int hash_string_fnv	(	const char *	datum,
		unsigned int *	len
	)

inlinestatic

Hash a string, returning a 32bit value.

The hash algorithm used is Fowler Noll Vo - a very fast and simple hash, ideal for short strings. See http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash for more details.

Parameters

datum	The string to hash.
len	Pointer to unsigned integer to record datum's length in.

Returns: The calculated hash value for the datum.

Definition at line 65 of file hashtable.c.

Referenced by hash_add(), and hash_get().

Here is the caller graph for this function:

◆ process_line()

static nserror process_line	(	struct hash_table *	hash,
		uint8_t *	ln,
		int	lnlen
	)

static

process a line of input.

Parameters

hash	The hash table to add the line to
ln	The line to process
lnlen	The length of \ln

Returns: NSERROR_OK on success else NSERROR_INVALID

Definition at line 94 of file hashtable.c.

References hash_add(), NSERROR_INVALID, NSERROR_OK, and NSLOG.

Referenced by hash_add_file(), hash_add_inline_gzip(), and hash_add_inline_plain().

Here is the call graph for this function:

Here is the caller graph for this function:

Data Structures

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ LINE_BUFFER_SIZE

Function Documentation

◆ hash_add()

◆ hash_add_file()

◆ hash_add_inline()

◆ hash_add_inline_gzip()

◆ hash_add_inline_plain()

◆ hash_create()

◆ hash_destroy()

◆ hash_get()

◆ hash_string_fnv()

◆ process_line()