Mirror of forum.nim-lang.org

10316 :: realloc and self referencing array problem

• r3c (orginal) [2023-07-03T13:58:12+02:00] view original

  When you expand an array/tree where each member has a pointer to other member, but realloc sometimes copy the old data and the pointers are gone.

  What im doing now is instead of pointers im using indexes, but its not enough flexible if you want to go up/down to parent/child trees. Other solution might be to create another struct which will hold the indices, or simply not using realloc at all and make linked list of arrays. This is pain it the a.

  Does Nim have any mechanism to overcome this?

---

• PMunch (orginal) [2023-07-03T14:01:50+02:00] view original

  The easiest would simply be to store the references in the sequence to begin with. The order would be kept by the sequence, and you're free to link to each object as you see fit. Of course this might hurt cache locality, so if that's of concern I guess you'd need to allocate chunks at a time or something.

---

• r3c (orginal) [2023-07-03T14:24:01+02:00] view original

  "allocate chunks at a time or something" Its the same thing as linked list of arrays, but from different angle :P

---

• PMunch (orginal) [2023-07-03T15:48:22+02:00] view original

  Sure, the point is that you need to keep your references pointing to something which won't move. As you've discovered realloc can move everything in your sequence, so to avoid this you can store references to your objects in your sequence instead of your actual objects. But if you want them to live close to each other in memory you need to allocate the memory for them in chunks. A list of arrays (linked or otherwise) is one way to solve this. But you could do it in other ways as well.

---

• mratsim (orginal) [2023-07-04T10:59:56+02:00] view original

  This is a common problem in graph data structures.

  Either you store a tree of references or you use an adjacency matrix.

---

• r3c (orginal) [2023-07-04T17:32:18+02:00] view original

  I was kinda hoping Nim has some pragma for this :)))

---