Is it possible to enforce a dependency between fields of a "config struct"?

Help
,
1

Hi, so basically I have finished my own implementation of a LinkedListUnmanaged, I’ve thoroughly tested that data structure, and it’s good. Now for my current question, I want to build my data structures with the same pattern as the std. Meaning you have the unmanaged version and on top of it you have the managed version, and custom behavior ect.

So right now this is what I have :

pub fn LinkedList(comptime T: type) type {
    return struct {
        const Self = @This();
        list: LinkedListUnmanaged(T),
        allocator: std.mem.Allocator,

        freelist: ?LinkedListUnmanaged(T),
        eql: ?fn (a: T, b: T) bool,
        config: LinkedListConfig,

        pub const LinkedListConfig = struct {
            use_buffer: ?bool,
            buffer_size: ?usize,
            load_factor: ?f32,
            eql: ?fn (a: T, b: T) bool,
        };

        pub fn create(allocator: std.mem.Allocator, config: LinkedListConfig) !*Self {
            var list = try allocator.create(Self);
            list.list = LinkedListUnmanaged(T).create(allocator);
            list.allocator = allocator;
            list.config = config;
        }
    };
}

pub fn LinkedListUnmanaged(comptime T: type) type {
    return struct {
        const Self = @This();
        const Data = T;
        maybe_head: ?*Node,
        maybe_tail: ?*Node,
        size: usize,
       /// rest of the implementation .....
}

What I would like to know is : is there a way in Zig to enforce at compile time, that if one field is assigned than the other must be too ? I’m not quite sure how to achieve or expressed what I want exactly, but basically I’d like to pass the LinkedListConfig struct to configure the LinkedList behavior for certain functionalities, but I’m not sure if I’m doing this in an idiomatic way ?

2

It seems easier to implement the unmanaged list first (to convert you linked list to unmanaged: remove the allocator field and add an allocator argument to all the functions that use it).
The managed version have as member the unmanaged list and the allocator. The allocator is set from an init function. All other functions does not have an allocator argument and pass their arguments to the unmanaged version function plus the allocator field.

No, there is no method to ensure it, except if you add these fields in a separate struct.

For example, instead of:

field1: ?T1,
field2: ?T2,

you can be sure that both are initialized with:

const S = struct{
    field1: T1,
    field2: T2,
};
fields: ?S,
1 Like
3

Yes that was my intention, I already have the complete unmanaged implementation and now I’m building on top of it the manage implementation. But if I understand you are suggesting that I put every fields that needs to be initialized together in a struct for the LinkedListConfig struct ?

4

I am not getting what are you trying to do with the other members (beside list and allocator).
And if these are required, why they are required for LinkedList and not for LinkedListUnmanaged.

1 Like
5

So basically the config options for the linked list that I would like would be to configure the use of a freelist as a buffer. So when you remove a value, you don’t destroy the node instead it’s store in the freelist and same thing when you want to insert instead of allocating for a node you simply reuse the free ones in the freelist, what I want to configure is the load factor meaning how many nodes should be kept free in regard to the size of the list and the minimum amount of node to allocate upfront at the initialization. Idk if that make sense bu this is the intended use case.

The reason the LinkedListUnmanaged doesn’t need that is because it only implement the behavior and doesn’t concern itself with memory management for example the LinkedListUnmanaged has :

        pub fn insertAt(list: *Self, child: *Node, index: usize) void {
            if (index == 0 or list.size == 0) return (list.insertFront(child));
            if (index >= list.size) return (list.insertBack(child));
            if (list.maybe_head) |head| {
                const parent = head.getNthChild(index - 1);
                parent.insertChild(child);
                list.size += 1;
            }
        }

        pub fn removeAt(list: *Self, index: usize) ?*Node {
            if (index == 0) return (list.removeFront());
            if (index >= list.size) return (list.removeBack());
            const temp = list.maybe_head orelse return (null);
            const parent = temp.getNthChild(index - 1);
            const child = parent.removeChild();
            list.size -= 1;
            return (child);
        }

Since the “buffer config” is simply an additional list to manage the free node it doesn’t need to be part of the Unmanaged version if that makes sense.

6

This can be achieved by an allocator.

1 Like
7

that’s actually a better solution, thanks for the suggestions :slight_smile:

8

Possibly related: Reduce large allocation mmap calls: free list allocator

1 Like
9

Thanks for the suggestion. I really like to see other’s code to get a better understanding of the idioms, Your implementation is great, although I’ll probably try to implement my own, it’s a great starting point thanks.

1 Like