map.c File Reference

Zero space overhead maps. More...

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <stddef.h>
#include <stdlib.h>
#include <inttypes.h>
#include "startle/types.h"
#include "startle/macros.h"
#include "startle/error.h"
#include "startle/log.h"
#include "startle/support.h"
#include "startle/map.h"

Macros
#define	DEBUG   0
#define	MERGE_TEST(arr)
#define	find_test(map, key)   _find_test((map), #map, (key))
#define	M   2
#define	N   8

Functions
void	swap_block (pair_t *a, pair_t *b, size_t n)
	Swap two non-overlapping blocks of n pairs. More...
void	reverse (pair_t *a, size_t n)
	Reverse n pairs. More...
void	rotate (pair_t *a, pair_t *b, size_t n)
	O(n) in-place rotation by n pairs. More...
	TEST (merge)
size_t	map_size (map_t map)
	Return number of entries that can be stored in a map. More...
size_t *	map_cnt (map_t map)
	Return number of entries currently stored in a map. More...
void	map_clear (map_t map)
	Clear all entries from the map. More...
pair_t *	map_elems (map_t map)
void	map_sort_full (map_t map)
	Fully sort map. More...
void	string_map_sort_full (map_t map)
	Fully sort a map with string keys. More...
	TEST (map_sort_full)
bool	map_insert (map_t map, pair_t x)
	Insert an entry into a map. More...
bool	string_map_insert (map_t map, pair_t x)
	Insert an entry into a string map. More...
bool	map_merge (map_t map, pair_t *x, size_t n)
	Merge n sorted entries at x into the map. More...
bool	string_map_merge (map_t map, pair_t *x, size_t n)
	Merge n sorted string entries at x into the map. More...
bool	_map_union (map_t a, map_t b, cmp_t cmp)
bool	map_union (map_t a, map_t b)
	Merge both maps into a. More...
bool	string_map_union (map_t a, map_t b)
	Merge both string maps into a. More...
	TEST (map_union)
	TEST (map_merge)
bool	map_replace_insert (map_t map, pair_t x)
	Insert into a map, replacing any entry with the same key. More...
bool	string_map_replace_insert (map_t map, pair_t x)
	Insert into a string map, replacing any entry with the same key. More...
pair_t *	map_find (map_t map, uintptr_t key)
	Look up an entry in a map. More...
uintptr_t	map_get (map_t map, uintptr_t key)
	Return the value for a key in a map. More...
pair_t *	string_map_find (map_t map, const char *key)
	Look up an entry in a string map. More...
pair_t *	seg_map_find (map_t map, seg_t key)
	Look up an entry in a string segment map. More...
pair_t *	map_find_value (map_t map, uintptr_t value)
	Look up a value in a map. More...
void	_print_map (char *name, map_t map)
void	_print_string_map (char *name, map_t map)
pair_t *	_find_test (map_t map, char *name, uintptr_t key)
	TEST (map)
	TEST (map_stack_behavior)
	TEST (rotate)
	TEST (string_map)
bool	check_order (pair_t *elems, size_t size, cmp_t cmp)
bool	check_map (map_t map, cmp_t cmp)

Detailed Description

Zero space overhead maps.

Macro Definition Documentation

MERGE_TEST

#define MERGE_TEST

(

arr

)

Value:

do {                                                                  \
    merge((arr), (arr) + (LENGTH(arr) >> 1), LENGTH(arr), key_cmp);     \
    printf(#arr ": ");                                                  \
    print_pairs((arr), LENGTH(arr));                                    \
  } while(0)

Function Documentation

map_clear()

void map_clear

(

map_t

map

)

Clear all entries from the map.

map_cnt()

size_t* map_cnt

(

map_t

map

)

Return number of entries currently stored in a map.

map_find()

pair_t* map_find	(	map_t	map,
		uintptr_t	key
	)

Look up an entry in a map.

O((log n)^2) time O(log n) time if the map is fully sorted.

See also

map_sort_full

Returns

a pointer to the entry if found, otherwise NULL.

map_find_value()

pair_t* map_find_value	(	map_t	map,
		uintptr_t	value
	)

Look up a value in a map.

O(n) time

Returns

pointer to the value if found, otherwise NULL

map_get()

uintptr_t map_get	(	map_t	map,
		uintptr_t	key
	)

Return the value for a key in a map.

Raises an error if the key in not found.

map_insert()

bool map_insert	(	map_t	map,
		pair_t	x
	)

Insert an entry into a map.

O(log n) average time, up to O(n).

Returns

true if inserted

  int ret = 0;
  MAP(map, 32);
  int elems[] = {2, 5, 8, 3, 1, 0, 4, 7, 6, 9, 10, 15, 13, 11, 12};
  FOREACH(i, elems) {
    pair_t p = {elems[i], i};
    map_insert(map, p);
  }
  print_map(map);

map_merge()

bool map_merge	(	map_t	map,
		pair_t *	x,
		size_t	n
	)

Merge n sorted entries at x into the map.

map_replace_insert()

bool map_replace_insert	(	map_t	map,
		pair_t	x
	)

Insert into a map, replacing any entry with the same key.

map_size()

size_t map_size

(

map_t

map

)

Return number of entries that can be stored in a map.

map_sort_full()

void map_sort_full

(

map_t

map

)

Fully sort map.

Takes O(log n) time. Lookup will be O(log n) afterwards.

map_union()

bool map_union	(	map_t	a,
		map_t	b
	)

Merge both maps into a.

reverse()

void reverse	(	pair_t *	a,
		size_t	n
	)

Reverse n pairs.

rotate()

void rotate	(	pair_t *	a,
		pair_t *	b,
		size_t	n
	)

O(n) in-place rotation by n pairs.

seg_map_find()

pair_t* seg_map_find	(	map_t	map,
		seg_t	key
	)

Look up an entry in a string segment map.

O((log n)^2) time O(log n) time if the map is fully sorted.

See also

map_sort_full

Returns

pointer to the entry if found, otherwise NULL

string_map_find()

pair_t* string_map_find	(	map_t	map,
		const char *	key
	)

Look up an entry in a string map.

O((log n)^2) time O(log n) time if the map is fully sorted.

See also

map_sort_full

Returns

pointer to the entry if found, otherwise NULL

string_map_insert()

bool string_map_insert	(	map_t	map,
		pair_t	x
	)

Insert an entry into a string map.

string_map_merge()

bool string_map_merge	(	map_t	map,
		pair_t *	x,
		size_t	n
	)

Merge n sorted string entries at x into the map.

string_map_replace_insert()

bool string_map_replace_insert	(	map_t	map,
		pair_t	x
	)

Insert into a string map, replacing any entry with the same key.

string_map_sort_full()

void string_map_sort_full

(

map_t

map

)

Fully sort a map with string keys.

string_map_union()

bool string_map_union	(	map_t	a,
		map_t	b
	)

Merge both string maps into a.

swap_block()

void swap_block	(	pair_t *	a,
		pair_t *	b,
		size_t	n
	)

Swap two non-overlapping blocks of n pairs.