1/* interned names and open-addressing hash table */
 2
 3#ifndef ARUU_TCUTIL_TABLE_H
 4#define ARUU_TCUTIL_TABLE_H
 5
 6#include <stdint.h> /* uint32_t */
 7
 8/* interned name: chars and hash are immutable once allocated
 9 * equality is pointer identity (see equal_name) */
10struct Name {
11  const char *chars;
12  int         bytes;
13  uint32_t    hash;
14};
15
16const struct Name *alloc_name(const char *begin, const char *end, int make_copy);
17const struct Name *alloc_cname(const char *cstr);
18int                equal_name(const struct Name *name1, const struct Name *name2);
19
20/* for printf: printf("%.*s\n", names(name)) */
21#define NAMES(name) ((name)->bytes), ((name)->chars)
22
23/* open-addressing hash table with linear probing */
24struct TableEntry {
25  const struct Name *key;
26  void              *value;
27};
28
29struct Table {
30  struct TableEntry *entries;
31  int                capacity;
32  int                count;
33  int                used; /* includes tombstones */
34};
35
36struct Table *alloc_table(void);
37void          table_init(struct Table *table);
38void         *table_get(struct Table *table, const struct Name *key);
39int           table_try_get(struct Table *table, const struct Name *key, void **output);
40int           table_put(struct Table *table, const struct Name *key, void *value);
41int           table_delete(struct Table *table, const struct Name *key);
42int           table_iterate(
43    const struct Table *table, int iterator, const struct Name **name, void **value
44); /* returns -1 at end */
45
46#endif /* ARUU_TCUTIL_TABLE_H */