Skip to content

impkement probing hashtable-based array domainsΒ #10

@micromaomao

Description

@micromaomao

@copilot Can you create a pull request that targets the "landlock-arraydomain" branch (not main!!) that does the following?

I was talking to the maintainer about converting Landlock to use a flat-array based lookup of rules, rather than the current rbtrees. Here is a snippet:

maybe the optimal way to do it would be to

  1. Add a "u32 next_collision" to domain_index
  2. Sort the indices array such that each domain_index is either placed in the slot corresponding to a hash of the key, or placed in one of the empty slots if a collision happens (and updating next_collision)

And then we can either allocate the array to be the next power of 2 size, in which case hashing would be faster, or allocate it with exactly the number of indices we need and do a modulo operation (less space, but potentially slower as it has to do a division?)

I can try to implement that. Searching is easy, but construction would probably be more tricky, and would also (temproarily) require a u32[number_of_rules] (or u32 [number_of_slots] if rounding to power of 2) scratch array

Please refer to #9 for the current flat array domains impl. We still want a flat array and we don't want individual allocations for each rule, so don't use stuff like hlist.

Metadata

Metadata

Assignees

Labels

No labels
No labels

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions