Hello guys.
Say I have generic table defined by myself (https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/content/ntddk/nf-ntddk-rtlinitializegenerictable) no matter this is AVL nor Splay.
Now, if my “content” of leaves in this tree contains some ULONGs or other simple POD style values I guess this is not a problem, but lets assume I have some strings in it. Is there any option to work on pointers to allocated memory instead of copying data every time I need to get some content?
I assume if I woudl return pointer to originally allocated memory (by allocate function I provided) it will be not thread safe right? Because I will never know if in another thread such content could be deleted… so i would need to have some ref counters to use otriginal memory OR I cna copy data all the time (but doing it under lock looks bit performance invasive). What is good way of handling this issue in general? how you address such issue?
Another question, more to confirm, if AVL tree needs rebalancing I guess under the hood there are no reallocations, but reassinging pointers “beloning” to tree right? I mean that AVL contains some structures and only those are “repinned” and memory allocated for content do not change?
Thank you.
You may work with pointers as elements (so the allocation routine would be called to allocate space for these pointers). Of course, you must ensure the pointers point to valid memory. As far as I read the documentation however, you need to synchronize access to the generic table since it is not thread-safe by its nature (e.g. an exclusive lock should be held when performing an insert operation).
Another question, more to confirm, if AVL tree needs rebalancing I guess under the hood there are no reallocations, but reassinging pointers “beloning” to tree right? I mean that AVL contains some structures and only those are “repinned” and memory allocated for content do not change?
I think rebalancing (in both AVL and splay tree cases) should not lead to any memory (de)allocations since tree rotations just work with pointers to left/right child and parent nodes.
Martin thank you for answer.
I’d say direct usage of pointers depends on case. If however my data is connected to process my guess I cannot use it, because in another thread I may receive termination callback in which I would remove such data and if in another thread Im accessing this data (e.g ecuase I needed to check something there) there is no safe way to do it.
Actually it doesn’t need to be connected to process itself. I think in any scenario when you have multiple readers and multiple writers such scenario may happen.
I’d say direct usage of pointers depends on case. If however my data is connected to process my guess I cannot use it, because in another thread I may receive termination callback in which I would remove such data and if in another thread Im accessing this data (e.g ecuase I needed to check something there) there is no safe way to do it.
I think that reference counting is probably the best option then, provided you can avoid circular references between objects. It is not so hard to implement and solves quite a lot of troubles for you.