From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: mail-a.sr.ht; dkim=pass header.d=maniero.me header.i=@maniero.me Received: from skyblue.cherry.relay.mailchannels.net (skyblue.cherry.relay.mailchannels.net [23.83.223.167]) by mail-a.sr.ht (Postfix) with ESMTPS id 9DC74200F6 for <~johnnyrichard/olang-devel@lists.sr.ht>; Tue, 20 Feb 2024 23:37:20 +0000 (UTC) X-Sender-Id: hostingeremail|x-authuser|carlos@maniero.me Received: from relay.mailchannels.net (localhost [127.0.0.1]) by relay.mailchannels.net (Postfix) with ESMTP id E60C3801444 for <~johnnyrichard/olang-devel@lists.sr.ht>; Tue, 20 Feb 2024 23:37:18 +0000 (UTC) Received: from fr-int-smtpout5.hostinger.io (unknown [127.0.0.6]) (Authenticated sender: hostingeremail) by relay.mailchannels.net (Postfix) with ESMTPA id 350B98012EC for <~johnnyrichard/olang-devel@lists.sr.ht>; Tue, 20 Feb 2024 23:37:18 +0000 (UTC) ARC-Seal: i=1; s=arc-2022; d=mailchannels.net; t=1708472238; a=rsa-sha256; cv=none; b=SoFJigr1/Ji1065T+wpGImqsEINoKEA8x7D2D/WQ/APsBg3oEw+NpXbd8QgLWLjq2PQqm6 W9RhXFOxSbdM9k7OGHnb+GpCYnp91sYEfWl/60Sd5ITyPKtyXrUl/5yODP2BmeTIWFfv5C mgHAvV++ZTj5IuHsLGpj0R2NWg9dFKqOXvAHLD1vU3MaWGsj394U0aXWV8aingxCLY6Qfu nmKS0e5UPr23TMAQrXLLwXp2lzCqFu1R4pdl0xKxBMZtMWPABtOks1hMwb+LE8JD8iixah uyMkZHusUlsaZQ4LVdLVSHqPtGphMARTwY2ZvYPhje2oI8tfdbn3lJSzMoWGMQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=mailchannels.net; s=arc-2022; t=1708472238; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding:dkim-signature; bh=OgULNZWtocvAGbdkjhD8H5B4pzbVBgDF3dGQ1jjbuiI=; b=0u7NwcQ4tF8u0uPxFL41ZhGYfr0lAtn/ITB4vmtISXz5gha/69etgY0uVTLt0Mwrgel2SR pMTFNEIaTi+4uHWhdPZmaPB6laKAHC0RnCn0+Y/EquJmfAZ2n3X25Lx3tfywySD4vmSnL9 aR7wisGg4oZULuMZcYBehm27EPNIpw0S5lsaD4XHKnvq0caIsPQwNXzp39FRO8c+IceuFk uG+lYXTNph39OvxQ1SuyTJCwirtUSaIz5RdPVXAh2woHJeobXOLxiVKg/AaYjIKIV8Yxp4 iic0WXfppMBG1hSCPdDL9VWkOp0oKwWUar1O7IJOAgv7J0UvJnCMiDkVwlQOhw== ARC-Authentication-Results: i=1; rspamd-55b4bfd7cb-785rt; auth=pass smtp.auth=hostingeremail smtp.mailfrom=carlos@maniero.me X-Sender-Id: hostingeremail|x-authuser|carlos@maniero.me X-MC-Relay: Neutral X-MailChannels-SenderId: hostingeremail|x-authuser|carlos@maniero.me X-MailChannels-Auth-Id: hostingeremail X-Society-Invention: 7d5f96a3602bd502_1708472238765_3844645385 X-MC-Loop-Signature: 1708472238765:1782385512 X-MC-Ingress-Time: 1708472238764 Received: from fr-int-smtpout5.hostinger.io ([UNAVAILABLE]. [89.116.146.168]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384) by 100.126.119.160 (trex/6.9.2); Tue, 20 Feb 2024 23:37:18 +0000 From: Carlos Maniero DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=maniero.me; s=hostingermail1; t=1708472236; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding; bh=OgULNZWtocvAGbdkjhD8H5B4pzbVBgDF3dGQ1jjbuiI=; b=dwN3jKfmCZSQjh0v2JAxRugily0UJHk3OFUgANyflnC6Q6dNbLCXt7BvylRYpO4QxoJi+9 EjCV6RTKRXK/eelmKwvtQcDzTSQBMvTfYX4zXWBwaadGMEvmj8DkVY0F6fYqMgvmyV2ExL +Ka+/TwRyTuMKMPp6tHO1/nEjTgyz3wXsYAkdbw3IAQWUWyK1slYB4luAH1WJHWdakFcyN vEuPB6ZUVx1Ccp5iQNdAf34mKoo2DBQESiwYJIDOifCIKyxrqGmEcov59MN0bf4O/sRRkY 1NLyQ7bNgpniDlyuVhXzJ0PbVlVwdssjIRkn9QwaXGQiLZUIIvsicj0UnMEr3g== To: ~johnnyrichard/olang-devel@lists.sr.ht Cc: Carlos Maniero Subject: [PATCH olang] utils: add linked-list Date: Tue, 20 Feb 2024 20:37:08 -0300 Message-Id: <20240220233708.2941689-1-carlos@maniero.me> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-CM-Envelope: MS4xfDa+a1kuLnka5De751sFyuv61iCpczSCzNxVJdY0o/htH72L1der+J1S4iIg5rnpt5fDZMlnDTa1Syd4oRyRu8uyiqdbfzpUb/YlaLZbVmafJAPZWFEk Y25ksXIT1FiZFFvAQLPFP1DadXfd5Ome2d3j99yRa6MdB9g6+CEV1uWZPbTFU6C4PuqQwO9W4W9Yue214sBdyNPBo1Kfz38pYe+yS6sY0n5xBTwGjYvqePMf X-CM-Analysis: v=2.4 cv=FdIxxo+6 c=1 sm=1 tr=0 ts=65d537ac a=5+VMC1FZ3J4mVPAKpPmAqg==:117 a=5+VMC1FZ3J4mVPAKpPmAqg==:17 a=MKtGQD3n3ToA:10 a=1oJP67jkp3AA:10 a=BXDaF_L80NYA:10 a=mDV3o1hIAAAA:8 a=6UXksaweZG04aP1sXPQA:9 a=rCLzwUJb8W8K_zSsa4A9:22 a=_FVE-zBwftR9WsbkzFJk:22 X-AuthUser: carlos@maniero.me X-TUID: lXKT7hSRgE93 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 --- 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 . + */ +#include "list.h" +#include + +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 . + */ +#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 . + */ +#define MUNIT_ENABLE_ASSERT_ALIASES +#include "arena.h" +#include "list.h" +#include "munit.h" +#include + +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