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 buffalo.tulip.relay.mailchannels.net (buffalo.tulip.relay.mailchannels.net [23.83.218.24]) by mail-a.sr.ht (Postfix) with ESMTPS id 30B8920195 for <~johnnyrichard/olang-devel@lists.sr.ht>; Tue, 27 Feb 2024 17:26:27 +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 7D6B22C3A99 for <~johnnyrichard/olang-devel@lists.sr.ht>; Tue, 27 Feb 2024 17:26:25 +0000 (UTC) Received: from uk-fast-smtpout2.hostinger.io (unknown [127.0.0.6]) (Authenticated sender: hostingeremail) by relay.mailchannels.net (Postfix) with ESMTPA id 7725E2C3C49 for <~johnnyrichard/olang-devel@lists.sr.ht>; Tue, 27 Feb 2024 17:26:24 +0000 (UTC) ARC-Seal: i=1; s=arc-2022; d=mailchannels.net; t=1709054784; a=rsa-sha256; cv=none; b=CiJ0qVBLt8nyZp6S6pEVMZ5gotxZJZtI4WErLWG2zQp9WHmZI5QlxWli9Hp2lnm62wY75w 2sfiyiv67Kq88K4WdkphkJSk1vfsHGbePHQurAazbGrmajKdRakhPa8a4k65NM4nmcRnLm NRN2LhpP0OMEXp1pbKLm4P57B8HzoL7kRmVL1uNptKB63M8zz2YeKFlwvwEBAeK4/Eqbj6 7mjIu1Wj+bVK7YSYXZVq4j1M7aoNwlcaKxhiUeHYLiGQ5GkN86VdyXlMPYBtZl6TaGAnpR fiIXTP19EVLLi6wxUmiLQcsSZR4dsp9N1NqVlfeGAA/IhLb7N9hTy+o136VMWA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=mailchannels.net; s=arc-2022; t=1709054784; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=Tgow4xAtWEN/VAs0rFwLEfx1QNpEfZy05iDmARO/LxI=; b=kA2wM1/gryVjqFt5TlmD9QZeTjkqC9auwOJMNHBNbn/VOZ7JlutEbf85IJ0mYjcAWDavyH YYEIEJZlpOnrilHIUZCQLnOL8SdSEk/yx87QNPB9xOnY8x7bpoOvN095EkJkWg3UVH7Qut 6g5DdfGXCkG6alUhuVt3cYnfcclANrD5Lo73LFpEU/cGbHtA5CUPttaSPiSWvkDdbCC4P3 00DXl0xrtEqkbbVIus1SjNL0yhuQ57J5RzBKJmTqQeT2XAgUHspO9hWZz0IuOWh9tPPPIM IsMbk7tgfUthcsbDKWijvb66wEVLhzn7npP1P4yEkZTgeaMHlT5G9/d/GD18Ew== ARC-Authentication-Results: i=1; rspamd-55b4bfd7cb-ctdpr; 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-Tangy-Illustrious: 7ca811d95785cab3_1709054785192_151978336 X-MC-Loop-Signature: 1709054785192:2008515872 X-MC-Ingress-Time: 1709054785192 Received: from uk-fast-smtpout2.hostinger.io (uk-fast-smtpout2.hostinger.io [31.220.23.36]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384) by 100.111.52.252 (trex/6.9.2); Tue, 27 Feb 2024 17:26:25 +0000 Mime-Version: 1.0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=maniero.me; s=hostingermail1; t=1709054783; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=jB0g7md1Rw91FYkf7Dd4OZVEh1rQKmFAtl+KV7XWvwI=; b=Oe1mPYDvrdPSS93pSIhunH2YVRdp9ZewTvU9OPA+v/VxrmpsqyQLP5m4/zrMizWE5eKnqu vQrpES3qQ/AeOBDw7jGfeXp3fJa/wG0dKpR1DuEJ1MQ1fAWzVsNhcRBCiUsFCSFa6lTF9d WUoIX5Jy6VLhdwUh1iTCnuHnsI90pYSBMtw8GFQ1MXLOmIhdfUB+Wvp1X45INpmX1quz4r EaG6IhCQAUfO1PTgtQWkBDs5jTKeoQcXWAQ1dzkZOqFLxuotK5P3dl757TLYafAUhs4veX yAxEi12cVg5RJATA7vxWLB7DwQzIY31/n4qT9EH/uorD4TXAHx/ynncO0vFKqQ== Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=UTF-8 Date: Tue, 27 Feb 2024 14:26:17 -0300 Message-Id: X-Sourcehut-Patchset-Update: NEEDS_REVISION Subject: Re: [PATCH olang 2/2] utils: create hash map data structure From: "Carlos Maniero" To: "Johnny Richard" , <~johnnyrichard/olang-devel@lists.sr.ht> X-Mailer: aerc 0.15.2-211-g37d5fc691aff References: <20240221222226.67254-1-johnny@johnnyrichard.com> <20240221222226.67254-3-johnny@johnnyrichard.com> In-Reply-To: <20240221222226.67254-3-johnny@johnnyrichard.com> X-CM-Envelope: MS4xfDMFNwbRGKDIUoZDhzg8ays/mB0sFy+Bz/Qb0kYYYq+Uupug7qXGanCIH2nswvXvay6X6CPuLRmWvsqkTqOODXxEZzMocvgIiGY6hvAZx8Vl5EJHDUvY d6P/SNgfblxHMGBhmFyDh5QWnuLLdOJNlk7EsilXWQtHmfHOFa9Ye752WK1qeixgJBXGUtnc70nnVYtG43pJoMcWUlOHxQVp8lumnAUg3NEOjq2w9YFyJBuy Lp24pmAow2AmpP5/Z6PHag== X-CM-Analysis: v=2.4 cv=WakKaVhX c=1 sm=1 tr=0 ts=65de1b3e a=5+VMC1FZ3J4mVPAKpPmAqg==:117 a=5+VMC1FZ3J4mVPAKpPmAqg==:17 a=IkcTkHD0fZMA:10 a=MKtGQD3n3ToA:10 a=1oJP67jkp3AA:10 a=BXDaF_L80NYA:10 a=4l1jnW7reBuPmyfzMzkA:9 a=QEXdDO2ut3YA:10 X-AuthUser: carlos@maniero.me X-TUID: F+XyElrB506l Nice work man! I've just a few suggestions. Changes I'm proposing: - replace __strdup with a arena function. - create a function to calculate the hash index. - some style changes on map_put ---->8---- diff --git a/src/arena.c b/src/arena.c index ae33e6a..d420002 100644 --- a/src/arena.c +++ b/src/arena.c @@ -17,6 +17,7 @@ #include "arena.h" #include #include +#include =20 arena_t arena_new(size_t size) @@ -51,3 +52,16 @@ arena_free(arena_t *arena) arena->size =3D 0; free(arena->region); } + +char * +arena_strdup(arena_t *arena, const char *s) +{ + size_t slen =3D strlen(s); + char *result =3D arena_alloc(arena, slen + 1); + if (result =3D=3D NULL) { + return NULL; + } + + memcpy(result, s, slen + 1); + return result; +} diff --git a/src/arena.h b/src/arena.h index 157165c..230eb5b 100644 --- a/src/arena.h +++ b/src/arena.h @@ -38,4 +38,7 @@ arena_release(arena_t *arena); void arena_free(arena_t *arena); =20 +char * +arena_strdup(arena_t *arena, const char *s); + #endif diff --git a/src/map.c b/src/map.c index 532ba3b..849130e 100644 --- a/src/map.c +++ b/src/map.c @@ -31,8 +31,8 @@ u32_fnv1a_hash(const char *s); static void map_init(map_t *map); =20 -static char * -__strdup(const char *s, arena_t *arena); +static uint32_t +map_index(map_t *map, uint32_t hash); =20 map_t * map_new(arena_t *arena) @@ -78,24 +78,27 @@ map_put(map_t *map, char *key, void *value) { assert(map && key); uint32_t hash =3D u32_fnv1a_hash(key); - map_entry_t *entry =3D &(map->entries[hash & (map->capacity - 1)]); + map_entry_t *entry =3D map->entries + map_index(map, hash); =20 - while (entry !=3D NULL) { + if (entry =3D=3D NULL) { + *entry =3D (map_entry_t){ .key =3D arena_strdup(map->arena, key), = .hash =3D hash, .value =3D value, .next =3D NULL }; + return true; + } + + do { if (entry->hash =3D=3D hash && strcmp(entry->key, key) =3D=3D 0) { entry->value =3D value; - return true; + break; } - if (entry->next =3D=3D NULL) + if (entry->next =3D=3D NULL) { + entry->next =3D (map_entry_t *)arena_alloc(map->arena, sizeof(= map_entry_t)); + *entry->next =3D + (map_entry_t){ .key =3D arena_strdup(map->arena, key), .ha= sh =3D hash, .value =3D value, .next =3D NULL }; + break; + } entry =3D entry->next; - } - - if (entry->key =3D=3D NULL) { - *entry =3D (map_entry_t){ .key =3D __strdup(key, map->arena), .has= h =3D hash, .value =3D value, .next =3D NULL }; - } else { - entry->next =3D (map_entry_t *)arena_alloc(map->arena, sizeof(map_= entry_t)); - *entry->next =3D (map_entry_t){ .key =3D __strdup(key, map->arena)= , .hash =3D hash, .value =3D value, .next =3D NULL }; - } + } while (entry !=3D NULL); =20 return true; } @@ -104,7 +107,7 @@ void * map_get(map_t *map, char *key) { uint32_t hash =3D u32_fnv1a_hash(key); - map_entry_t *entry =3D &map->entries[hash & (map->capacity - 1)]; + map_entry_t *entry =3D map->entries + map_index(map, hash); while (entry !=3D NULL) { if (entry->hash =3D=3D hash && strcmp(entry->key, key) =3D=3D 0) { return entry->value; @@ -114,15 +117,9 @@ map_get(map_t *map, char *key) return NULL; } =20 -static char * -__strdup(const char *s, arena_t *arena) +static uint32_t +map_index(map_t *map, uint32_t hash) { - size_t slen =3D strlen(s); - char *result =3D arena_alloc(arena, slen + 1); - if (result =3D=3D NULL) { - return NULL; - } - - memcpy(result, s, slen + 1); - return result; + uint32_t capacity_mask =3D map->capacity - 1; + return hash & capacity_mask; } diff --git a/tests/unit/map_test.c b/tests/unit/map_test.c index 3eb9acd..fab4c69 100644 --- a/tests/unit/map_test.c +++ b/tests/unit/map_test.c @@ -52,7 +52,10 @@ test_map_put_and_get(const MunitParameter params[], void= *user_data_or_fixture) assert_int(*((int *)map_get(map, "n1")), =3D=3D, n1); assert_int(*((int *)map_get(map, "n2")), =3D=3D, n2); =20 + map_put(map, "n1", (void *)&n2); + arena_free(&arena); + assert_int(*((int *)map_get(map, "n1")), =3D=3D, n2); =20 return MUNIT_OK; }