search

ziglang / zig

General-purpose programming language and toolchain for maintaining robust, optimal, and reusable software.
https://ziglang.org
MIT License
35.07k stars 2.56k forks source link

Add a PriorityQueueUnmanaged type to the standard library #21432

Open saltzm opened 2 months ago

saltzm commented 2 months ago

Several Zig data structures in the standard library have "unmanaged" types that require the user to pass an allocator to any function that may allocate. Examples include ArrayListUnmanaged and HashMapUnmanaged. There is however no such type for PriorityQueue.

I'm currently in need of a PriorityQueueUnmanaged, and I made one myself from the existing PriorityQueue code. I'd be happy to contribute it to the standard library if the contribution would be welcome.

The main questions I'd have for an acceptable implementation would be:

  1. Whether the original PriorityQueue type should be implemented in terms of the new PriorityQueueUnmanaged type. ArrayList seems to have separate implementations rather than having the managed version rely on the unmanaged version and I'm not sure why without reading it more closely. My inclination would be to implement PriorityQueue in terms of PriorityQueueUnmanaged but I'm curious whether others see drawbacks to this approach that I'm not seeing.
  2. Whether there should only be a PriorityQueueUnmanaged type, or whether the base type should be PriorityQueueAlignedUnmanaged similar to ArrayList. I have not done it with AlignedUnmanaged locally but given the backing data is just stored in a slice, I think an AlignedUnmanaged type would make sense.
andrewrk commented 2 months ago

Since this is a lesser used API, I think it's OK to be a little more experimental and aggressive with breakage. My suggestion is to modify the existing one to become unmanaged, and drop the "unmanaged" from the name, same as how is currently done for MultiArrayList.

Rexicon226 commented 2 months ago

I agree with Andrew. Should PriorityDequeue also undergo the same change?

andrewrk commented 2 months ago

Sure

andrewrk commented 2 months ago

2. whether the base type should be PriorityQueueAlignedUnmanaged similar to ArrayList. I have not done it with AlignedUnmanaged locally but given the backing data is just stored in a slice, I think an AlignedUnmanaged type would make sense.

Let's start with only having the default-aligned version. I think we can get away with that, and it's nicer to avoid it if possible.