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 heron.birch.relay.mailchannels.net (heron.birch.relay.mailchannels.net [23.83.209.82]) by mail-a.sr.ht (Postfix) with ESMTPS id 9FF1020195 for <~johnnyrichard/olang-devel@lists.sr.ht>; Tue, 27 Feb 2024 18:45:08 +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 43821544002 for <~johnnyrichard/olang-devel@lists.sr.ht>; Tue, 27 Feb 2024 18:45:05 +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 671AA543E8D for <~johnnyrichard/olang-devel@lists.sr.ht>; Tue, 27 Feb 2024 18:45:04 +0000 (UTC) ARC-Seal: i=1; s=arc-2022; d=mailchannels.net; t=1709059504; a=rsa-sha256; cv=none; b=Ox8PPPzctHqa2LSxSZmliOianJs8twknU8LkTjSUZS8zxj2qzso6edr1Bu//kwhB3cnt6x O8JpfbU1I9lWgWWoLeHn04nnjbefwB/Z8WVvp7+KD7WwroYQdw2xDPuVKjIrwP8n1G6rPR sjbn1O8SQ2fuey+geQWl9gojL4uPtd8PsWyy7Q7YoPJfTgt6023MCcsK5lHP4Vbw5SiydX yQnY0TUFUVGpLk+3WGesLUawgYZB34LMdGLFsjTDnGApvEqaGtrxy6mDCdjdkonXbnpUsG qCWBSIfNuV/1Dbs20+yotGbhJPOq0e8SieaWz350j85hT4263puN86T8ckvjyg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=mailchannels.net; s=arc-2022; t=1709059504; 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=T/ohkgJknM4V53mVfpcDuLbUe0GgnCGoaO26iMYt2xI=; b=VIRhOk4kbwSduHOUIIGPKTZ26EGnyhY1UoZsz4zoY01nDBPkuWuf4u96tdfo2DHYXEe/5T D0tqt4+o/+Os4iM+o9FRNtala7/YAzMRQO+bLxlTsokuhelhZSkwJ2tG7a6xOHBlgrG02F oSL50vtR0ww3N9Wo2aLwHba3A1CINtATQrwh9OXtF8Uq7uM9Z379VOqwOiJQU2ELd00hGZ /kFpgCrRc/OsvVjRMA3lk4c1KBfEHVzvXB1izy+gw5LUHFHavyFV7W2yJztxlZZuNX19Yg GiFjWZb8wcA4Ye4JPCsMOKMYIJQxX2osnv2zo/imtHGlw601zzu5kvzzrZ5xZw== 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-Skirt-Abortive: 099a2e9b177b6333_1709059504974_3038896790 X-MC-Loop-Signature: 1709059504973:3182838959 X-MC-Ingress-Time: 1709059504973 Received: from fr-int-smtpout5.hostinger.io ([UNAVAILABLE]. [89.116.146.168]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384) by 100.124.220.191 (trex/6.9.2); Tue, 27 Feb 2024 18:45:04 +0000 Mime-Version: 1.0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=maniero.me; s=hostingermail1; t=1709059502; 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=T/ohkgJknM4V53mVfpcDuLbUe0GgnCGoaO26iMYt2xI=; b=aI8+RxczZGdb+tasJOlsc0leTnFDEghUD2qXaguSAnHujjo2BfSD7xLlx2SgxZOiOEw5T2 3iOZ7tdU+wbdXJ3r09hZf/yPiINgpmqZLoQ1HrPAgf7Fcz7bzYESrtd7hrLlPjror1n0RJ Z+nHO9Apo4w8cE93M5EZx9eA+EMK+ktQeE8zXFKLZvEHmseKnuFCYbkOyDrOWebvVc4kGc YAWkDXr+Nt0kG+j0bGWoP4BSe8f7232uVx0BkXXpbQWNx7WB1w+S5NuRU3Qz4pkAyrV8Eg Gv9SlNSMI6rO8JMW/xgkZcsCxo05HuSY/BFbVtZqIKJE9Nwzf8Uin/QS2b54pA== Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=UTF-8 Date: Tue, 27 Feb 2024 15:44:56 -0300 Message-Id: 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-Analysis: v=2.4 cv=S+LfwpsP c=1 sm=1 tr=0 ts=65de2dae a=5+VMC1FZ3J4mVPAKpPmAqg==:117 a=5+VMC1FZ3J4mVPAKpPmAqg==:17 a=IkcTkHD0fZMA:10 a=MKtGQD3n3ToA:10 a=1oJP67jkp3AA:10 a=BXDaF_L80NYA:10 a=hiCM8kp1hnV805XiqbEA:9 a=QEXdDO2ut3YA:10 X-CM-Envelope: MS4xfFQxPMBybMlTtgOMABBI2bCMfxPmqIHssOVDYkL0Stby28WbZ3qyuMY/POJLXxjQ5eV6aJPQ05CGN3qZjaUfeHw0PILNISu09daG2dJ1muYdC1vkZY7q cfvaQR1LIBKXNXrwMRWKvXBO3UNVqTyJrixuC5fG5fS1US/1NDmsY0Ku1Kd3tNrIAuXggH4BNI8nvmCyHbXFZl9Z0S8T2EAbZy3ai1snxdF3tufnQG2uKdYa AmwFsix4J9OAaxR21Ic9+g== X-AuthUser: carlos@maniero.me X-TUID: xTDjkehA3HKS Fixing the suggestions based on Johnny's comments: - on map_test I was asserting after freeing the memory - on map.c there was a bug where I was valdating that the entry was NULL not the entry->key which was leading to always having an empty first entry (not a SEGFAULT). - It does not makes sense to have strdup on arena. - Instead I just kept the convention to have a single _. If you think we are good to go, please send a v2. So it will trigger the pipeline. --->8--- diff --git a/src/map.c b/src/map.c index 532ba3b..6665e18 100644 --- a/src/map.c +++ b/src/map.c @@ -32,7 +32,10 @@ static void map_init(map_t *map); =20 static char * -__strdup(const char *s, arena_t *arena); +_strdup(const char *s, arena_t *arena); + +static uint32_t +map_get_index(map_t *map, uint32_t hash); =20 map_t * map_new(arena_t *arena) @@ -78,24 +81,26 @@ 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_get_index(map, hash); =20 - while (entry !=3D NULL) { + if (entry->key =3D=3D NULL) { + *entry =3D (map_entry_t){ .key =3D _strdup(key, map->arena), .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 _strdup(key, map->are= na), .hash =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 +109,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_get_index(map, hash); while (entry !=3D NULL) { if (entry->hash =3D=3D hash && strcmp(entry->key, key) =3D=3D 0) { return entry->value; @@ -114,8 +119,15 @@ map_get(map_t *map, char *key) return NULL; } =20 +static uint32_t +map_get_index(map_t *map, uint32_t hash) +{ + uint32_t capacity_mask =3D map->capacity - 1; + return hash & capacity_mask; +} + static char * -__strdup(const char *s, arena_t *arena) +_strdup(const char *s, arena_t *arena) { size_t slen =3D strlen(s); char *result =3D arena_alloc(arena, slen + 1); diff --git a/tests/unit/map_test.c b/tests/unit/map_test.c index 3eb9acd..449bca6 100644 --- a/tests/unit/map_test.c +++ b/tests/unit/map_test.c @@ -52,6 +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); + + assert_int(*((int *)map_get(map, "n1")), =3D=3D, n2); + arena_free(&arena); =20 return MUNIT_OK;