summaryrefslogtreecommitdiffstats
path: root/src/fixedmap.h
diff options
context:
space:
mode:
authorMatt Dunwoodie <ncon@mail.noconroy.net>2019-08-22 22:03:23 +1000
committerMatt Dunwoodie <ncon@mail.noconroy.net>2019-08-22 22:32:02 +1000
commitcba35db712513a4d16e19021f6c50fd37c31fbb9 (patch)
tree9f239047aa4f08bac1f70f3aca1cf3d012ecfe55 /src/fixedmap.h
parentAdd bloombucket.h for ratelimiting. (diff)
downloadwireguard-openbsd-cba35db712513a4d16e19021f6c50fd37c31fbb9.tar.xz
wireguard-openbsd-cba35db712513a4d16e19021f6c50fd37c31fbb9.zip
Add fixedmap.h, with the intention to replace hashmap.h
Diffstat (limited to 'src/fixedmap.h')
-rw-r--r--src/fixedmap.h151
1 files changed, 151 insertions, 0 deletions
diff --git a/src/fixedmap.h b/src/fixedmap.h
new file mode 100644
index 00000000000..aa7430c3ed9
--- /dev/null
+++ b/src/fixedmap.h
@@ -0,0 +1,151 @@
+/*
+ * Copyright (c) 2019 Matt Dunwoodie <ncon@noconroy.net>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef __FIXEDMAP_H__
+#define __FIXEDMAP_H__
+
+#include <sys/types.h>
+#include <sys/rwlock.h>
+
+struct fixed_map {
+ struct rwlock lock;
+ uint8_t bits;
+ struct map_item {
+ enum {
+ FM_ITEM_EMPTY = 0,
+ FM_ITEM_RESERVED,
+ FM_ITEM_FILLED,
+ } state;
+ uint32_t key;
+ void *value;
+ } *map;
+};
+
+void fm_init(struct fixed_map *);
+void fm_destroy(struct fixed_map *);
+void fm_resize(struct fixed_map *, size_t);
+uint32_t fm_reserve(struct fixed_map *);
+void fm_set(struct fixed_map *, uint32_t, void *);
+uint32_t fm_insert(struct fixed_map *, void *);
+void *fm_lookup(struct fixed_map *, uint32_t);
+void fm_remove(struct fixed_map *, uint32_t);
+
+#define fm_size(fm) (1 << (fm)->bits)
+#define fm_item(fm, k) ((fm)->map[(k) & ((fm)->bits - 1)])
+
+void
+fm_init(struct fixed_map *fm)
+{
+ rw_init(&fm->lock, "fixed_map");
+ fm->bits = 0;
+ fm->map = NULL;
+}
+
+void
+fm_destroy(struct fixed_map *fm)
+{
+ free(fm->map, M_DEVBUF, 0);
+}
+
+void
+fm_resize(struct fixed_map *fm, size_t size)
+{
+ struct map_item *old_map;
+ size_t old_size, i;
+
+ if (size <= fm_size(fm))
+ return;
+
+ rw_enter_write(&fm->lock);
+ old_size = fm_size(fm);
+ old_map = fm->map;
+
+ for(fm->bits = 1; size >>= 1; fm->bits++);
+ fm->map = mallocarray(fm_size(fm), sizeof(*fm->map), M_DEVBUF, M_WAITOK | M_ZERO);
+
+ if (old_map != NULL) {
+ for (i = 0; i < old_size; i++)
+ fm_item(fm, old_map[i].key) = old_map[i];
+ free(old_map, M_DEVBUF, 0);
+ }
+ rw_exit_write(&fm->lock);
+}
+
+uint32_t
+fm_reserve(struct fixed_map *fm)
+{
+ size_t i;
+ struct map_item *item = NULL;
+
+ rw_enter_write(&fm->lock);
+ for (i = 0; i < fm_size(fm); i++) {
+ if (fm->map[i].state == FM_ITEM_EMPTY) {
+ item = &fm->map[i];
+ break;
+ }
+ }
+
+ if (item == NULL)
+ panic("unable to find space in fixed map");
+
+ item->key = (arc4random() << fm->bits) + i;
+ item->state = FM_ITEM_RESERVED;
+ rw_exit_write(&fm->lock);
+
+ return item->key;
+}
+
+void
+fm_set(struct fixed_map *fm, uint32_t k, void *v)
+{
+ rw_enter_write(&fm->lock);
+ if (fm_item(fm, k).key == k ) {
+ fm_item(fm, k).value = v;
+ fm_item(fm, k).state = FM_ITEM_FILLED;
+ }
+ rw_exit_write(&fm->lock);
+}
+
+uint32_t
+fm_insert(struct fixed_map *fm, void *v)
+{
+ uint32_t k = fm_reserve(fm);
+ fm_set(fm, k, v);
+ return k;
+}
+
+void *
+fm_lookup(struct fixed_map *fm, uint32_t k)
+{
+ void *v;
+ rw_enter_read(&fm->lock);
+ v = fm_item(fm, k).key == k ? fm_item(fm, k).value : NULL;
+ rw_exit_read(&fm->lock);
+ return v;
+}
+
+void
+fm_remove(struct fixed_map *fm, uint32_t k)
+{
+ rw_enter_write(&fm->lock);
+ if (fm_item(fm, k).key == k) {
+ fm_item(fm, k).value = NULL;
+ fm_item(fm, k).state = FM_ITEM_EMPTY;
+ }
+ rw_exit_write(&fm->lock);
+}
+
+#endif /* __FIXEDMAP_H__ */