Index_vec.MakeIndex vector circuit with tracks indexes.
module X : sig ... endinclude S with type tag := Hardcaml.Signal.t Hardcaml.Interface.Empty.tThe vec is a small, growable array of elements. Elements may be inserted and removed from any position. Note that insertion and deletion shuffle elements up/down.
Unlike a normal data structure, it isn't supposed to hold the actual data. Instead it holds the index at which the data should reside. It should be connected to an external ram with the address connected to:
insertion_index when insertingdeletion_index when deletingaccess_index (with the address on op.slot and op.op=noop) when you want to access the data at a slot.To insert an element, set op.op = insert and *during the same cycle* write the data to the (external) memory at insertion_index. Similarly to delete an element.
In some cases it is necessary to associate some extra bits that move with the indices - this can be done using tags. Tags may be changed (though the tag_next function) so long as the circuit is not currently inserting or deleting. To modify the tag value during insertion or deletion, see insertion_tag and deletion_tag in the type Make_tagged.op below.
val indexes : t -> Hardcaml.Signal.t Base.arrayReturn an array of current indexes
val index : at:Hardcaml.Signal.t -> t -> Hardcaml.Signal.tGet the index for the given position in the vec
val tags : t -> Hardcaml.Signal.t Hardcaml.Interface.Empty.t Base.arrayReturn an array of current tags
val tag :
at:Hardcaml.Signal.t ->
t ->
Hardcaml.Signal.t Hardcaml.Interface.Empty.tGet the tag for the given position in the vec
val insertion_index : t -> Hardcaml.Signal.tIndex at which insertion will take place. It is valid _while_ the insert op is performed.
val deletion_index : t -> Hardcaml.Signal.tIndex at which deletion will take place. It is valid _while_ the delete op is performed.
val access_index : t -> Hardcaml.Signal.tIndex corresponding to op.slot.
The length is tracked during inserts and removes. To compute the length it tracks the insertion/deletion slot. Removing from an 'empty' slot does not decrease the size.
Using length is optional and probably not required unless treating the vec as a queue or stack (which can also be implemented more efficiently with a fifo like structure).
full and empty are derived combinationally from length.
val length : t -> Hardcaml.Signal.tLength of the vec
val full : t -> Hardcaml.Signal.tIs the vec full?
val empty : t -> Hardcaml.Signal.tIs the vec empty?
type op = {slot : Hardcaml.Signal.t; | (* Slot to perform operation at *) |
op : Hardcaml.Signal.t; | (* Operation type (insert, remove or nothing) *) |
}Operation performed on the vec circuit.
val create : Hardcaml.Reg_spec.t -> op -> tCreate the vec with the given size.