tiny.wayland.ids

1const std = @import("std");23pub const display_id: u32 = 1;4pub const first_dynamic_id: u32 = 2;5pub const first_server_id: u32 = 0xff000000;6pub const maximum_client_id_count: usize = first_server_id - first_dynamic_id;7pub const default_client_id_count: usize = 256;89pub const Limits = struct {10    client_id_count: usize = default_client_id_count,11};1213pub const CapacityError = error{14    ClientIdStorageTooLarge,15    CapacityOverflow,16};1718pub const Capacity = struct {19    client_id_count: usize,20    state_bytes: usize,21    reusable_id_bytes: usize,22    total_requested_bytes: usize,2324    pub fn derive(limits: Limits) CapacityError!Capacity {25        if (limits.client_id_count > maximum_client_id_count) {26            return error.ClientIdStorageTooLarge;27        }28        const state_bytes = std.math.mul(29            usize,30            limits.client_id_count,31            @sizeOf(State),32        ) catch return error.CapacityOverflow;33        const reusable_id_bytes = std.math.mul(34            usize,35            limits.client_id_count,36            @sizeOf(u32),37        ) catch return error.CapacityOverflow;38        const total_requested_bytes = std.math.add(39            usize,40            state_bytes,41            reusable_id_bytes,42        ) catch return error.CapacityOverflow;43        return .{44            .client_id_count = limits.client_id_count,45            .state_bytes = state_bytes,46            .reusable_id_bytes = reusable_id_bytes,47            .total_requested_bytes = total_requested_bytes,48        };49    }50};5152pub const StorageError = error{ClientIdCapacityExceeded};5354pub const LifecycleError = error{55    InvalidObjectId,56    UnknownObject,57    ObjectAlreadyRetired,58    ObjectStillLive,59    DeleteAlreadyAcknowledged,60};6162pub const Error = StorageError || LifecycleError;6364pub const Status = struct {65    client_id_capacity_rejection_count: u64 = 0,66};6768pub const default_capacity = Capacity.derive(.{}) catch unreachable;6970const State = enum {71    live,72    awaiting_delete,73    reusable,74};7576pub const Pool = struct {77    session_allocator: std.mem.Allocator,78    states: []State,79    reusable: []u32,80    state_count: usize = 0,81    reusable_count: usize = 0,82    capacity_rejection_count: u64 = 0,8384    pub fn init(85        session_allocator: std.mem.Allocator,86        capacity: Capacity,87    ) std.mem.Allocator.Error!Pool {88        const states = try session_allocator.alloc(State, capacity.client_id_count);89        errdefer if (states.len != 0) session_allocator.free(states);90        return .{91            .session_allocator = session_allocator,92            .states = states,93            .reusable = try session_allocator.alloc(u32, capacity.client_id_count),94        };95    }9697    pub fn deinit(self: *Pool) void {98        self.assertValid();99        if (self.reusable.len != 0) self.session_allocator.free(self.reusable);100        if (self.states.len != 0) self.session_allocator.free(self.states);101        self.* = undefined;102    }103104    pub fn allocate(self: *Pool) StorageError!u32 {105        self.assertValid();106        if (self.reusable_count != 0) {107            self.reusable_count -= 1;108            const id = self.reusable[self.reusable_count];109            self.states[index(id)] = .live;110            return id;111        }112113        if (self.state_count == self.states.len) {114            self.capacity_rejection_count +|= 1;115            return error.ClientIdCapacityExceeded;116        }117        const id = first_dynamic_id + @as(u32, @intCast(self.state_count));118        self.states[self.state_count] = .live;119        self.state_count += 1;120        return id;121    }122123    pub fn abandon(self: *Pool, id: u32) LifecycleError!void {124        const at = try self.knownIndex(id);125        switch (self.states[at]) {126            .live => {127                std.debug.assert(self.reusable_count < self.reusable.len);128                self.states[at] = .reusable;129                self.reusable[self.reusable_count] = id;130                self.reusable_count += 1;131            },132            .awaiting_delete => return error.ObjectAlreadyRetired,133            .reusable => return error.DeleteAlreadyAcknowledged,134        }135    }136137    pub fn retire(self: *Pool, id: u32) LifecycleError!void {138        const at = try self.knownIndex(id);139        switch (self.states[at]) {140            .live => self.states[at] = .awaiting_delete,141            .awaiting_delete => return error.ObjectAlreadyRetired,142            .reusable => return error.DeleteAlreadyAcknowledged,143        }144    }145146    pub fn acknowledgeDelete(self: *Pool, id: u32) LifecycleError!void {147        const at = try self.knownIndex(id);148        switch (self.states[at]) {149            .live => return error.ObjectStillLive,150            .awaiting_delete => {151                std.debug.assert(self.reusable_count < self.reusable.len);152                self.reusable[self.reusable_count] = id;153                self.reusable_count += 1;154                self.states[at] = .reusable;155            },156            .reusable => return error.DeleteAlreadyAcknowledged,157        }158    }159160    pub fn isLive(self: *const Pool, id: u32) bool {161        const at = self.knownIndex(id) catch return false;162        return self.states[at] == .live;163    }164165    pub fn status(self: *const Pool) Status {166        self.assertValid();167        return .{168            .client_id_capacity_rejection_count = self.capacity_rejection_count,169        };170    }171172    fn knownIndex(self: *const Pool, id: u32) LifecycleError!usize {173        self.assertValid();174        if (id < first_dynamic_id or id >= first_server_id) return error.InvalidObjectId;175        const at = index(id);176        if (at >= self.state_count) return error.UnknownObject;177        return at;178    }179180    fn assertValid(self: *const Pool) void {181        std.debug.assert(self.states.len == self.reusable.len);182        std.debug.assert(self.states.len <= maximum_client_id_count);183        std.debug.assert(self.state_count <= self.states.len);184        std.debug.assert(self.reusable_count <= self.state_count);185    }186};187188fn index(id: u32) usize {189    return @intCast(id - first_dynamic_id);190}191192test "client ID capacity derives two exact storage regions" {193    try std.testing.expectEqual(@as(usize, 256), default_capacity.client_id_count);194    const capacity = try Capacity.derive(.{ .client_id_count = 3 });195    try std.testing.expectEqual(@as(usize, 3), capacity.client_id_count);196    try std.testing.expectEqual(3 * @sizeOf(State), capacity.state_bytes);197    try std.testing.expectEqual(3 * @sizeOf(u32), capacity.reusable_id_bytes);198    try std.testing.expectEqual(199        capacity.state_bytes + capacity.reusable_id_bytes,200        capacity.total_requested_bytes,201    );202    try std.testing.expectError(203        error.ClientIdStorageTooLarge,204        Capacity.derive(.{ .client_id_count = maximum_client_id_count + 1 }),205    );206}207208test "client ID storage is acquired before use" {209    const capacity = try Capacity.derive(.{ .client_id_count = 3 });210    for (0..2) |fail_index| {211        var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{212            .fail_index = fail_index,213        });214        try std.testing.expectError(error.OutOfMemory, Pool.init(failing.allocator(), capacity));215    }216    var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{217        .fail_index = 2,218    });219    var pool = try Pool.init(failing.allocator(), capacity);220    defer pool.deinit();221    try std.testing.expectEqual(@as(usize, 2), failing.allocations);222}223224test "object IDs become reusable only after delete_id acknowledgement" {225    var pool = try Pool.init(std.testing.allocator, default_capacity);226    defer pool.deinit();227228    try std.testing.expectEqual(@as(u32, 2), try pool.allocate());229    try std.testing.expectEqual(@as(u32, 3), try pool.allocate());230    try pool.retire(2);231    try std.testing.expectEqual(@as(u32, 4), try pool.allocate());232    try pool.acknowledgeDelete(2);233    try std.testing.expectEqual(@as(u32, 2), try pool.allocate());234}235236test "delete_id lifecycle rejects invalid transitions" {237    var pool = try Pool.init(std.testing.allocator, default_capacity);238    defer pool.deinit();239240    const id = try pool.allocate();241    try std.testing.expectError(error.ObjectStillLive, pool.acknowledgeDelete(id));242    try pool.retire(id);243    try std.testing.expectError(error.ObjectAlreadyRetired, pool.retire(id));244    try pool.acknowledgeDelete(id);245    try std.testing.expectError(error.DeleteAlreadyAcknowledged, pool.acknowledgeDelete(id));246}247248test "unsent object IDs can be abandoned without server acknowledgement" {249    var pool = try Pool.init(std.testing.allocator, default_capacity);250    defer pool.deinit();251252    const id = try pool.allocate();253    try pool.abandon(id);254    try std.testing.expectEqual(id, try pool.allocate());255    try pool.abandon(id);256    try std.testing.expectError(error.DeleteAlreadyAcknowledged, pool.abandon(id));257}258259test "client ID max plus one preserves storage and saturates status" {260    const capacity = try Capacity.derive(.{ .client_id_count = 2 });261    var pool = try Pool.init(std.testing.allocator, capacity);262    defer pool.deinit();263    const states = pool.states.ptr;264    const reusable = pool.reusable.ptr;265266    try std.testing.expectEqual(@as(u32, 2), try pool.allocate());267    try std.testing.expectEqual(@as(u32, 3), try pool.allocate());268    try std.testing.expectError(error.ClientIdCapacityExceeded, pool.allocate());269    try std.testing.expectEqual(states, pool.states.ptr);270    try std.testing.expectEqual(reusable, pool.reusable.ptr);271    try std.testing.expectEqual(272        @as(u64, 1),273        pool.status().client_id_capacity_rejection_count,274    );275276    pool.capacity_rejection_count = std.math.maxInt(u64);277    try std.testing.expectError(error.ClientIdCapacityExceeded, pool.allocate());278    try std.testing.expectEqual(279        std.math.maxInt(u64),280        pool.status().client_id_capacity_rejection_count,281    );282}283284test "every allocated ID has infallible rollback capacity" {285    const capacity = try Capacity.derive(.{ .client_id_count = 65 });286    var pool = try Pool.init(std.testing.allocator, capacity);287    defer pool.deinit();288289    var allocated: [65]u32 = undefined;290    for (&allocated) |*id| id.* = try pool.allocate();291    for (allocated) |id| try pool.abandon(id);292    for (0..allocated.len) |_| _ = try pool.allocate();293}

1pub const ids = @import("ids.zig");