summaryrefslogtreecommitdiff
path: root/include/libHX/map.h
blob: ecbf7037357add8852c43259fea41c9a18720288 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#ifndef _LIBHX_MAP_H
#define _LIBHX_MAP_H 1

#ifdef __cplusplus
#	include <cstddef>
#else
#	include <stdbool.h>
#	include <stddef.h>
#endif

#ifdef __cplusplus
extern "C" {
#endif

/**
 * Abstract:
 * %HXMAPT_DEFAULT:	whatever is fast and maps k-v, without preference
 * %HXMAPT_ORDERED:	anything ordered, no further preference
 *
 * Specific:
 * %HXMAPT_HASH:	map based on hash
 * %HXMAPT_RBTREE:	map based on red-black binary tree
 */
enum HXmap_type {
	HXMAPT_HASH = 1,
	HXMAPT_RBTREE,

	/* aliases - assignments may change */
	HXMAPT_DEFAULT = HXMAPT_HASH,
	HXMAPT_ORDERED = HXMAPT_RBTREE,
};

/**
 * Flags changable at runtime:
 * %HXMAP_NOREPLACE:	Calling HXmap_add() for an already existing key will
 * 			throw an error (no-overwrite semantics)
 *
 * Initialization-time flags only:
 * %HXMAP_NONE:		mnemonic for no flags
 * %HXMAP_SINGULAR:	Instead of an associative map, provide a set
 * %HXMAP_SKEY:		Key will be a C-style string (sets ops->k_*)
 * %HXMAP_CKEY:		Make a copy of the key on HXmap_add
 * %HXMAP_SDATA:	Data will be a C-style string (presets ops->d_*)
 * %HXMAP_CDATA:	Make a copy of the data on HXmap_add
 */
enum {
	HXMAP_NONE      = 0,
	HXMAP_NOREPLACE = 1 << 0,
	HXMAP_SINGULAR  = 1 << 1,
	HXMAP_SKEY      = 1 << 2,
	HXMAP_CKEY      = 1 << 3,
	HXMAP_SDATA     = 1 << 4,
	HXMAP_CDATA     = 1 << 5,

	HXMAP_SCKEY     = HXMAP_SKEY | HXMAP_CKEY,
	HXMAP_SCDATA    = HXMAP_SDATA | HXMAP_CDATA,
};

/**
 * Flags for the traverser
 * %HXMAP_NOFLAGS:	Mnemonic for no flags
 * %HXMAP_DTRAV:	Support deletion of elements while traversing
 */
enum {
	HXMAP_NOFLAGS   = 0,
	HXMAP_DTRAV     = 1 << 0,
};

struct HXmap_trav;

/**
 * @items:	number of items in the map
 * @flags:	flags for this map
 */
struct HXmap {
	unsigned int items, flags;
};

struct HXmap_ops {
	/* k_compare: the size argument is needed for memcmp. */
	int (*k_compare)(const void *, const void *, size_t);
	void *(*k_clone)(const void *, size_t);
	void (*k_free)(void *);
	void *(*d_clone)(const void *, size_t);
	void (*d_free)(void *);
	unsigned long (*k_hash)(const void *, size_t);
};

struct HXmap_node {
	union {
		void *key;
		const char *const skey;
	};
	union {
		void *data;
		char *sdata;
	};
};

extern struct HXmap *HXmap_init(enum HXmap_type, unsigned int);
extern struct HXmap *HXmap_init5(enum HXmap_type, unsigned int,
	const struct HXmap_ops *, size_t, size_t);

extern int HXmap_add(struct HXmap *, const void *, const void *);
extern const struct HXmap_node *HXmap_find(const struct HXmap *, const void *);
extern void *HXmap_get(const struct HXmap *, const void *);
extern void *HXmap_del(struct HXmap *, const void *);
extern struct HXmap_node *HXmap_keysvalues(const struct HXmap *);
extern struct HXmap_trav *HXmap_travinit(const struct HXmap *, unsigned int);
extern const struct HXmap_node *HXmap_traverse(struct HXmap_trav *);
extern void HXmap_travfree(struct HXmap_trav *);
extern void HXmap_qfe(const struct HXmap *,
	bool (*)(const struct HXmap_node *, void *), void *);
extern void HXmap_free(struct HXmap *);

extern unsigned long HXhash_jlookup3(const void *, size_t);
extern unsigned long HXhash_jlookup3s(const void *, size_t);
extern unsigned long HXhash_djb2(const void *, size_t);

#ifdef __cplusplus
} /* extern "C" */

extern "C++" {

template<typename type> static __inline__ type
HXmap_get(const struct HXmap *map, const void *key)
{
	return reinterpret_cast<type>(HXmap_get(map, key));
}

template<typename type> static __inline__ type
HXmap_del(struct HXmap *map, const void *key)
{
	return reinterpret_cast<type>(HXmap_del(map, key));
}

}
#endif

#endif /* _LIBHX_MAP_H */