Slices: A growable list of pointers.
authorDan Cross <crossd@gmail.com>
Fri, 22 Jan 2016 19:26:11 +0000 (14:26 -0500)
committerBarret Rhoden <brho@cs.berkeley.edu>
Mon, 25 Jan 2016 16:02:20 +0000 (11:02 -0500)
Introduce the slice library; a growable list of pointers.
Loosely modeled after the 'slice' abstraction in the Go
programming language.

Signed-off-by: Dan Cross <crossd@gmail.com>
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
kern/include/slice.h [new file with mode: 0644]
kern/lib/Kbuild
kern/lib/slice.c [new file with mode: 0644]

diff --git a/kern/include/slice.h b/kern/include/slice.h
new file mode 100644 (file)
index 0000000..7405cb5
--- /dev/null
@@ -0,0 +1,26 @@
+/*
+ * Copyright (C) 2016 Google Inc.
+ * Dan Cross <crossd@gmail.com>
+ * See LICENSE for license details.
+ */
+
+#pragma once
+
+/*
+ * A tracking structure for growing lists of pointers.
+ */
+struct slice {
+       void **ptrs;
+       size_t len;
+       size_t capacity;
+};
+
+void slice_init(struct slice *slice);
+void slice_clear(struct slice *slice);
+void *slice_get(struct slice *slice, size_t i);
+bool slice_put(struct slice *slice, size_t i, void *p);
+bool slice_del(struct slice *slice, size_t i);
+void slice_append(struct slice *s, void *p);
+size_t slice_len(struct slice *slice);
+void **slice_finalize(struct slice *slice);
+void slice_destroy(struct slice *slice);
index 1e3281b..6d332bb 100644 (file)
@@ -1,5 +1,6 @@
 obj-y                                          += address_range.o
+obj-y                                          += circular_buffer.o
+obj-y                                          += slice.o
 obj-y                                          += sort.o
 obj-y                                          += zlib_deflate/
 obj-y                                          += zlib_inflate/
-obj-y                                          += circular_buffer.o
diff --git a/kern/lib/slice.c b/kern/lib/slice.c
new file mode 100644 (file)
index 0000000..a92b588
--- /dev/null
@@ -0,0 +1,89 @@
+/*
+ * Copyright (C) 2016 Google Inc.
+ * Dan Cross <crossd@gmail.com>
+ * See LICENSE for license details.
+ */
+
+#include <kmalloc.h>
+#include <assert.h>
+#include <error.h>
+#include <slice.h>
+
+void slice_init(struct slice *slice)
+{
+       memset(slice, 0, sizeof(*slice));
+}
+
+void slice_clear(struct slice *slice)
+{
+       slice->len = 0;
+       memset(slice->ptrs, 0, sizeof(*slice->ptrs) * slice->capacity);
+}
+
+void *slice_get(struct slice *slice, size_t i)
+{
+       if (i >= slice->len)
+               return NULL;
+       return slice->ptrs[i];
+}
+
+bool slice_put(struct slice *slice, size_t i, void *p)
+{
+       if (i >= slice->len)
+               return FALSE;
+       slice->ptrs[i] = p;
+       return TRUE;
+}
+
+bool slice_del(struct slice *slice, size_t i)
+{
+       if (i >= slice->len)
+               return FALSE;
+       memmove(slice->ptrs + i, slice->ptrs + i + 1,
+               (slice->len - (i + 1)) * sizeof(void *));
+       slice->len--;
+       return TRUE;
+}
+
+void slice_append(struct slice *s, void *p)
+{
+       void **ps;
+
+       assert(p != NULL);
+       if (s->len == s->capacity) {
+               if (s->capacity == 0)
+                       s->capacity = 4;
+               s->capacity *= 2;
+               ps = kreallocarray(s->ptrs, s->capacity, sizeof(void *), KMALLOC_WAIT);
+               assert(ps != NULL);             /* XXX: if size*sizeof(void*) overflows. */
+               s->ptrs = ps;
+       }
+       s->ptrs[s->len] = p;
+       s->len++;
+}
+
+size_t slice_len(struct slice *slice)
+{
+       return slice->len;
+}
+
+void **slice_finalize(struct slice *slice)
+{
+       void **ps;
+
+       ps = kreallocarray(slice->ptrs, slice->len, sizeof(void *), KMALLOC_WAIT);
+       assert(ps != NULL);
+       slice->len = 0;
+       slice->capacity = 0;
+       slice->ptrs = NULL;
+
+       return ps;
+}
+
+void slice_destroy(struct slice *slice)
+{
+       kfree(slice->ptrs);
+       slice->ptrs = NULL;
+       slice->capacity = 0;
+       slice->len = 0;
+}