[PATCH olang] utils: add linked-list

[PATCH olang] utils: add linked-list

[Carlos Maniero]

Add a append only linked list. Since there is no reason to remove an
item from the list, this is a append-only list, that can be access by
index or by walked-trough using list_next.

The next api can be used like this:

    list_item_t *item = list_head(&list);

    while(true) {
        if (item == NULL) {
            break;
        }
        printf("item %d\n", *((int*)item->value));
        item = list_next(item);
    }

Signed-off-by: Carlos Maniero <carlos@maniero.me>
---
 src/list.c             |  84 +++++++++++++++++++++++++++++++
 src/list.h             |  52 +++++++++++++++++++
 tests/unit/list_test.c | 110 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 246 insertions(+)
 create mode 100644 src/list.c
 create mode 100644 src/list.h
 create mode 100644 tests/unit/list_test.c

diff --git a/src/list.c b/src/list.c
new file mode 100644
index 0000000..a3dd3fe
--- /dev/null
+++ b/src/list.c
@@ -0,0 +1,84 @@
+/*
+ * Copyright (C) 2024 olang maintainers
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+#include "list.h"
+#include <assert.h>
+
+void
+list_init(list_t *list, arena_t *arena)
+{
+    assert(list != NULL);
+    list->size = 0;
+    list->arena = arena;
+    list->head = NULL;
+}
+
+void
+list_append(list_t *list, void *value)
+{
+    assert(list != NULL);
+    list_item_t *item = arena_alloc(list->arena, sizeof(list_item_t));
+    item->value = value;
+    item->next = NULL;
+    list->size++;
+
+    if (list->size == 1) {
+        list->head = item;
+        list->tail = item;
+        return;
+    }
+
+    list->tail->next = item;
+    list->tail = item;
+}
+
+list_item_t *
+list_get(list_t *list, size_t index)
+{
+    assert(list != NULL);
+    assert(index < list->size);
+
+    list_item_t *item = list->head;
+
+    while (index != 0) {
+        item = item->next;
+
+        index--;
+    }
+
+    return item;
+}
+
+list_item_t *
+list_head(list_t *list)
+{
+    assert(list != NULL);
+    return list->head;
+}
+
+list_item_t *
+list_next(list_item_t *item)
+{
+    assert(item != NULL);
+    return item->next;
+}
+
+size_t
+list_size(list_t *list)
+{
+    assert(list != NULL);
+    return list->size;
+}
diff --git a/src/list.h b/src/list.h
new file mode 100644
index 0000000..901d27e
--- /dev/null
+++ b/src/list.h
@@ -0,0 +1,52 @@
+/*
+ * Copyright (C) 2024 olang maintainers
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+#ifndef LIST_H
+#define LIST_H
+#include "arena.h"
+
+typedef struct list_item
+{
+    void *value;
+    struct list_item *next;
+} list_item_t;
+
+typedef struct list
+{
+    size_t size;
+    arena_t *arena;
+    list_item_t *head;
+    list_item_t *tail;
+} list_t;
+
+void
+list_init(list_t *list, arena_t *arena);
+
+void
+list_append(list_t *list, void *value);
+
+list_item_t *
+list_get(list_t *list, size_t index);
+
+list_item_t *
+list_head(list_t *list);
+
+list_item_t *
+list_next(list_item_t *item);
+
+size_t
+list_size(list_t *list);
+#endif
diff --git a/tests/unit/list_test.c b/tests/unit/list_test.c
new file mode 100644
index 0000000..33d867b
--- /dev/null
+++ b/tests/unit/list_test.c
@@ -0,0 +1,110 @@
+/*
+ * Copyright (C) 2024 olang maintainers
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+#define MUNIT_ENABLE_ASSERT_ALIASES
+#include "arena.h"
+#include "list.h"
+#include "munit.h"
+#include <stdio.h>
+
+static MunitResult
+list_append_test(const MunitParameter params[], void *user_data_or_fixture)
+{
+    arena_t arena = arena_new(sizeof(list_item_t));
+
+    list_t list;
+    list_init(&list, &arena);
+
+    munit_assert_int(list_size(&list), ==, 0);
+
+    int value = 42;
+    list_append(&list, &value);
+
+    munit_assert_int(list_size(&list), ==, 1);
+
+    arena_free(&arena);
+
+    return MUNIT_OK;
+}
+
+static MunitResult
+list_get_test(const MunitParameter params[], void *user_data_or_fixture)
+{
+    arena_t arena = arena_new(sizeof(list_item_t) * 3);
+
+    list_t list;
+    list_init(&list, &arena);
+
+    int a = 1;
+    int b = 2;
+    int c = 3;
+
+    list_append(&list, &a);
+    list_append(&list, &b);
+    list_append(&list, &c);
+
+    munit_assert_ptr_equal(list_get(&list, 0)->value, (void *)&a);
+    munit_assert_ptr_equal(list_get(&list, 1)->value, (void *)&b);
+    munit_assert_ptr_equal(list_get(&list, 2)->value, (void *)&c);
+
+    arena_free(&arena);
+
+    return MUNIT_OK;
+}
+
+static MunitResult
+list_next_test(const MunitParameter params[], void *user_data_or_fixture)
+{
+    arena_t arena = arena_new(sizeof(list_item_t) * 3);
+
+    list_t list;
+    list_init(&list, &arena);
+
+    int a = 1;
+    int b = 2;
+    int c = 3;
+
+    list_append(&list, &a);
+    list_append(&list, &b);
+    list_append(&list, &c);
+
+    list_item_t *item_a = list_head(&list);
+    list_item_t *item_b = list_next(item_a);
+    list_item_t *item_c = list_next(item_b);
+
+    munit_assert_ptr_equal(item_a->value, (void *)&a);
+    munit_assert_ptr_equal(item_b->value, (void *)&b);
+    munit_assert_ptr_equal(item_c->value, (void *)&c);
+    munit_assert_ptr_null(list_next(item_c));
+
+    arena_free(&arena);
+
+    return MUNIT_OK;
+}
+
+static MunitTest tests[] = { { "/list_append_test", list_append_test, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+                             { "/list_get_test", list_get_test, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+                             { "/list_next_test", list_next_test, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+                             { NULL, NULL, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL } };
+
+static const MunitSuite suite = { "/cli_test", tests, NULL, 1, MUNIT_SUITE_OPTION_NONE };
+
+int
+main(int argc, char *argv[])
+{
+    return munit_suite_main(&suite, NULL, argc, argv);
+    return EXIT_SUCCESS;
+}
-- 
2.34.1

[olang/patches/.build.yml] build success

[builds.sr.ht]

olang/patches/.build.yml: SUCCESS in 35s

[utils: add linked-list][0] from [Carlos Maniero][1]

[0]: https://lists.sr.ht/~johnnyrichard/olang-devel/patches/49714
[1]: mailto:carlos@maniero.me

✓ #1154366 SUCCESS olang/patches/.build.yml https://builds.sr.ht/~johnnyrichard/job/1154366

Re: [PATCH olang] utils: add linked-list

[Johnny Richard]

Looks good! Applied.

To git.sr.ht:~johnnyrichard/olang
   08d63bc..60eacac  main -> main