# Recursive data structures with stdlib hash maps

**URL:** <https://fortran-lang.discourse.group/t/recursive-data-structures-with-stdlib-hash-maps/4501>\
**Category:** stdlib\
**Created:** [October 10, 2022, 9:25pm UTC](https://fortran-lang.discourse.group/t/recursive-data-structures-with-stdlib-hash-maps/4501 "2022-10-10T21:25:02Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![awvwgk](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/awvwgk/32/154_2.png) [@awvwgk](https://fortran-lang.discourse.group/u/awvwgk)\
**Post date:** [October 10, 2022, 9:25pm UTC](https://fortran-lang.discourse.group/t/recursive-data-structures-with-stdlib-hash-maps/4501/1 "2022-10-10T21:25:02Z")

</div>

I’m trying to understand whether it is possible / feasible to define recursive data structures using stdlib’s hash maps. For the most basic functionality, I would need a way to store maps and arrays, where the latter can be implemented as associative array using a map, as values.

However, the `copy_other` routine uses a sourced allocation, which means any data structure stored in a stdlib hash map will be copied in and later copied out this way:

> <https://github.com/fortran-lang/stdlib/blob/f8e29c6/src/stdlib_hashmap_wrappers.f90#L128-L137>

For a recursive data structure this can be quite an issue, depending on the represented data, for example I found deep copy of a 2 MB JSON to be possible however quite expensive ([TOML Fortran 0.3.0 - #3 by awvwgk](https://fortran-lang.discourse.group/t/toml-fortran-0-3-0/4108/3)).

I wonder whether there is a better way to create recursive data structures based on what we have available in stdlib.

---

<div class="post-metadata">

**Author:** ![everythingfunctional](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/everythingfunctional/32/176_2.png) [@everythingfunctional](https://fortran-lang.discourse.group/u/everythingfunctional)\
**Post date:** [October 11, 2022, 12:37am UTC](https://fortran-lang.discourse.group/t/recursive-data-structures-with-stdlib-hash-maps/4501/2 "2022-10-11T00:37:12Z")

</div>

My solution to this problem in [rojff](https://gitlab.com/everythingfunctional/rojff) was to use `move_alloc`. In that way you can build up quite large recursive data structures without any copying. It gets really monotonous and tricky to get right if you do it all in one procedure, but there’s an example of it in the test suite. Check out the `move_construct_with(out)_errors`[test/construction\_method\_test.f90 · main · Brad Richardson / rojff · GitLab](https://gitlab.com/everythingfunctional/rojff/-/blob/main/test/construction_method_test.f90)

---

<div class="post-metadata">

**Author:** ![awvwgk](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/awvwgk/32/154_2.png) [@awvwgk](https://fortran-lang.discourse.group/u/awvwgk)\
**Post date:** [October 11, 2022, 4:15am UTC](https://fortran-lang.discourse.group/t/recursive-data-structures-with-stdlib-hash-maps/4501/3 "2022-10-11T04:15:54Z")

</div>

But this requires that we change how stdlib hash maps work, _i.e._ recursive data structures are currently not possible there.

---

<div class="post-metadata">

**Author:** ![everythingfunctional](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/everythingfunctional/32/176_2.png) [@everythingfunctional](https://fortran-lang.discourse.group/u/everythingfunctional)\
**Post date:** [October 11, 2022, 2:16pm UTC](https://fortran-lang.discourse.group/t/recursive-data-structures-with-stdlib-hash-maps/4501/4 "2022-10-11T14:16:12Z")

</div>

I took a quick look, and I actually don’t see how one puts data into or fetches it from the stdlib hash map. I did see one type with a `class(*)` component, which would let you have recursive data structures (unless you mean the constructed data structure would have circular references, in which case I don’t think that’s possible).

Is there a tutorial, or user-guide for the stdlib hash map somewhere?

---

<div class="post-metadata">

**Author:** ![gnikit](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/gnikit/32/1213_2.png) [@gnikit](https://fortran-lang.discourse.group/u/gnikit)\
**Post date:** [October 11, 2022, 3:45pm UTC](https://fortran-lang.discourse.group/t/recursive-data-structures-with-stdlib-hash-maps/4501/5 "2022-10-11T15:45:49Z")

</div>

I remember stumbling onto this a while back

> <https://github.com/fortran-lang/stdlib/pull/611>
>
> \<!--
> Thank you for contributing to stdlib.
> To help us get your pull request me…rged more quickly, please consider reviewing any of the already open pull requests.
> \--\>
> 
> Now that hash functions have been added to the standard library, it is time to add hash maps. Currently this PR only includes the documentation, \`doc/specs/stdlib\_hash\_maps.md\`, giving the proposed API. The proposed API has three module files: \`stdlib\_key\_data\_wrapper.f90\`, which provides wrappers for the key and data components of the entries and some of the hash function; \`stdlib\_chaining\_hash\_map.f90\`, which implements a chaining hash map with linked lists; and \`stdlib\_open\_hash\_maps.f90\`, which implements a linear addressing open hashing map. After the (modified) API has been approved by two people I will add the required module files.

---

<div class="post-metadata">

**Author:** ![jeremie.vandenplas](https://avatars.discourse-cdn.com/v4/letter/j/76d3ee/32.png) [@jeremie.vandenplas](https://fortran-lang.discourse.group/u/jeremie.vandenplas)\
**Post date:** [October 12, 2022, 8:33am UTC](https://fortran-lang.discourse.group/t/recursive-data-structures-with-stdlib-hash-maps/4501/6 "2022-10-12T08:33:58Z")

</div>

> [@everythingfunctional](#):
>
> Is there a tutorial, or user-guide for the stdlib hash map somewhere?

Not per se. There is only the [description of the API](https://stdlib.fortran-lang.org/page/specs/stdlib_hashmaps.html).

> [@awvwgk](#):
>
> But this requires that we change how stdlib hash maps work, _i.e._ recursive data structures are currently not possible there.

I used the stdlib hashmaps a few times and I was happy with its API and performances (in comparison to other fpmized hashmap projects). However, as it is still experimental, the API can still be changed and improved

---

<div class="post-metadata">

**Author:** ![gronki](https://avatars.discourse-cdn.com/v4/letter/g/a88e4f/32.png) [@gronki](https://fortran-lang.discourse.group/u/gronki)\
**Post date:** [October 9, 2023, 5:05pm UTC](https://fortran-lang.discourse.group/t/recursive-data-structures-with-stdlib-hash-maps/4501/7 "2023-10-09T17:05:41Z")

</div>

Off-topic, but I read the code of `rojff`. Very clean and nice. I like how you approached the error handling here. Definetely learned something 🙂