1 // Hash table datastructure with methods and type information
7 #include <string.h> // IWYU pragma: export
14 #define EMPTY_TABLE ((Table_t){.entries.data = &_EMPTY_LIST_SENTINEL})
16 #define Table(key_t, val_t, key_info, value_info, fb, N, ...) \
21 } ents[N] = {__VA_ARGS__}; \
22 Table_t table = Table$from_entries( \
24 .data = memcpy(GC_MALLOC(sizeof(ents)), ents, sizeof(ents)), \
25 .length = sizeof(ents) / sizeof(ents[0]), \
26 .stride = (void *)&ents[1] - (void *)&ents[0], \
28 Table$info(key_info, value_info)); \
29 table.fallback = fb; \
33 Table_t Table$from_entries(List_t entries, const TypeInfo_t *type);
34 void *Table$get(Table_t t, const void *key, const TypeInfo_t *type);
35 #define Table$get_optional(table_expr, key_t, val_t, key_expr, nonnull_var, nonnull_expr, null_expr, info_expr) \
37 const Table_t t = table_expr; \
38 const key_t k = key_expr; \
39 val_t *nonnull_var = Table$get(t, &k, info_expr); \
40 nonnull_var ? nonnull_expr : null_expr; \
42 #define Table$get_checked(table_expr, key_t, val_t, key_expr, start, end, info_expr) \
44 const Table_t t = table_expr; \
45 const key_t key = key_expr; \
46 const TypeInfo_t *info = info_expr; \
47 val_t *value = Table$get(t, &key, info); \
48 if (unlikely(value == NULL)) \
49 fail_source(__SOURCE_FILE__, start, end, \
50 Text$concat(Text("This key was not found in the table: "), \
51 generic_as_text(&key, false, info->TableInfo.key), Text("\n"))); \
54 #define Table$get_or_setdefault(table_expr, key_t, val_t, key_expr, default_expr, info_expr) \
56 Table_t *t = table_expr; \
57 const key_t k = key_expr; \
58 if (t->entries.data_refcount > 0) \
59 List$compact(&t->entries, sizeof(struct { \
63 val_t *v = Table$get(*t, &k, info_expr); \
64 v ? v : (val_t *)Table$reserve(t, &k, (val_t[1]){default_expr}, info_expr); \
66 #define Table$get_or_default(table_expr, key_t, val_t, key_expr, default_expr, info_expr) \
68 const Table_t t = table_expr; \
69 const key_t k = key_expr; \
70 val_t *v = Table$get(t, &k, info_expr); \
71 v ? *v : default_expr; \
73 #define Table$has_value(table_expr, key_expr, info_expr) \
75 const Table_t t = table_expr; \
76 __typeof(key_expr) k = key_expr; \
77 (Table$get(t, &k, info_expr) != NULL); \
79 PUREFUNC void *Table$get_raw(Table_t t, const void *key, const TypeInfo_t *type);
80 CONSTFUNC void *Table$entry(Table_t t, int64_t n);
81 void *Table$reserve(Table_t *t, const void *key, const void *value, const TypeInfo_t *type);
82 void Table$set(Table_t *t, const void *key, const void *value, const TypeInfo_t *type);
83 #define Table$set_value(t, key_expr, value_expr, type) \
85 __typeof(key_expr) k = key_expr; \
86 __typeof(value_expr) v = value_expr; \
87 Table$set(t, &k, &v, type); \
89 void Table$remove(Table_t *t, const void *key, const TypeInfo_t *type);
90 #define Table$remove_value(t, key_expr, type) \
92 __typeof(key_expr) k = key_expr; \
93 Table$remove(t, &k, type); \
96 Table_t Table$intersection(Table_t a, Table_t b, const TypeInfo_t *type);
97 Table_t Table$with(Table_t a, Table_t b, const TypeInfo_t *type);
98 Table_t Table$without(Table_t a, Table_t b, const TypeInfo_t *type);
99 Table_t Table$difference(Table_t a, Table_t b, const TypeInfo_t *type);
100 Table_t Table$with_fallback(Table_t t, OptionalTable_t fallback);
102 void Table$clear(Table_t *t);
103 Table_t Table$sorted(Table_t t, const TypeInfo_t *type);
104 void Table$mark_copy_on_write(Table_t *t);
105 #define TABLE_INCREF(t) \
107 LIST_INCREF((t).entries); \
108 if ((t).bucket_info) \
109 (t).bucket_info->data_refcount += ((t).bucket_info->data_refcount < TABLE_MAX_DATA_REFCOUNT); \
111 #define TABLE_COPY(t) \
116 PUREFUNC int32_t Table$compare(const void *x, const void *y, const TypeInfo_t *type);
117 PUREFUNC bool Table$equal(const void *x, const void *y, const TypeInfo_t *type);
118 PUREFUNC uint64_t Table$hash(const void *t, const TypeInfo_t *type);
119 Text_t Table$as_text(const void *t, bool colorize, const TypeInfo_t *type);
120 PUREFUNC bool Table$is_none(const void *obj, const TypeInfo_t *);
122 CONSTFUNC void *Table$str_entry(Table_t t, int64_t n);
123 PUREFUNC void *Table$str_get(Table_t t, const char *key);
124 PUREFUNC void *Table$str_get_raw(Table_t t, const char *key);
125 void Table$str_set(Table_t *t, const char *key, const void *value);
126 void *Table$str_reserve(Table_t *t, const char *key, const void *value);
127 void Table$str_remove(Table_t *t, const char *key);
128 void Table$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type);
129 void Table$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type);
131 #define Table$length(t) ((t).entries.length)
133 extern const TypeInfo_t Present$$info;
134 extern const Present$$type PRESENT;
135 extern const TypeInfo_t CStrToVoidStarTable;
137 #define Table$metamethods \
139 .as_text = Table$as_text, \
140 .compare = Table$compare, \
141 .equal = Table$equal, \
142 .hash = Table$hash, \
143 .is_none = Table$is_none, \
144 .serialize = Table$serialize, \
145 .deserialize = Table$deserialize, \
148 #define Table$info(key_expr, value_expr) \
149 ((TypeInfo_t[1]){{.size = sizeof(Table_t), \
150 .align = __alignof__(Table_t), \
152 .TableInfo.key = key_expr, \
153 .TableInfo.value = value_expr, \
154 .metamethods = Table$metamethods}})
155 #define Set$info(item_info) \
156 ((TypeInfo_t[1]){{.size = sizeof(Table_t), \
157 .align = __alignof__(Table_t), \
159 .TableInfo.key = item_info, \
160 .TableInfo.value = &Void$info, \
161 .metamethods = Table$metamethods}})