diff options
Diffstat (limited to 'vendor/codeberg.org/gruf/go-structr/timeline.go')
| -rw-r--r-- | vendor/codeberg.org/gruf/go-structr/timeline.go | 1008 |
1 files changed, 1008 insertions, 0 deletions
diff --git a/vendor/codeberg.org/gruf/go-structr/timeline.go b/vendor/codeberg.org/gruf/go-structr/timeline.go new file mode 100644 index 000000000..7a9c17f70 --- /dev/null +++ b/vendor/codeberg.org/gruf/go-structr/timeline.go @@ -0,0 +1,1008 @@ +package structr + +import ( + "cmp" + "reflect" + "slices" + "sync" + "unsafe" +) + +// Direction defines a direction +// to iterate entries in a Timeline. +type Direction bool + +const ( + // Asc = ascending, i.e. bottom-up. + Asc = Direction(true) + + // Desc = descending, i.e. top-down. + Desc = Direction(false) +) + +// TimelineConfig defines config vars for initializing a Timeline{}. +type TimelineConfig[StructType any, PK cmp.Ordered] struct { + + // Copy provides a means of copying + // timelined values, to ensure returned values + // do not share memory with those in timeline. + Copy func(StructType) StructType + + // Invalidate is called when timelined + // values are invalidated, either as passed + // to Insert(), or by calls to Invalidate(). + Invalidate func(StructType) + + // PKey defines the generic parameter StructType's + // field to use as the primary key for this cache. + // It must be ordered so that the timeline can + // maintain correct sorting of inserted values. + // + // Field selection logic follows the same path as + // with IndexConfig{}.Fields. Noting that in this + // case only a single field is permitted, though + // it may be nested, and as described above the + // type must conform to cmp.Ordered. + PKey string + + // Indices defines indices to create + // in the Timeline for the receiving + // generic struct type parameter. + Indices []IndexConfig +} + +// Timeline provides an ordered-list like cache of structures, +// with automated indexing and invalidation by any initialization +// defined combination of fields. The list order is maintained +// according to the configured struct primary key. +type Timeline[StructType any, PK cmp.Ordered] struct { + + // hook functions. + invalid func(StructType) + copy func(StructType) StructType + + // main underlying + // timeline list. + // + // where: + // - head = top = largest + // - tail = btm = smallest + list list + + // contains struct field information of + // the field used as the primary key for + // this timeline. it can also be found + // under indices[0] + pkey pkey_field + + // indices used in storing passed struct + // types by user defined sets of fields. + indices []Index + + // protective mutex, guards: + // - Timeline{}.* + // - Index{}.data + mutex sync.Mutex +} + +// Init initializes the timeline with given configuration +// including struct fields to index, and necessary fns. +func (t *Timeline[T, PK]) Init(config TimelineConfig[T, PK]) { + rt := reflect.TypeOf((*T)(nil)).Elem() + + if len(config.Indices) == 0 { + panic("no indices provided") + } + + if config.Copy == nil { + panic("copy function must be provided") + } + + // Safely copy over + // provided config. + t.mutex.Lock() + defer t.mutex.Unlock() + + // The first index is created from PKey. + t.indices = make([]Index, len(config.Indices)+1) + t.indices[0].ptr = unsafe.Pointer(t) + t.indices[0].init(rt, IndexConfig{ + Fields: config.PKey, + AllowZero: true, + Multiple: true, + }, 0) + if len(t.indices[0].fields) > 1 { + panic("primary key must contain only 1 field") + } + for i, cfg := range config.Indices { + t.indices[i+1].ptr = unsafe.Pointer(t) + t.indices[i+1].init(rt, cfg, 0) + } + + // Before extracting + // first index for pkey. + field := t.indices[0].fields[0] + t.pkey = pkey_field{ + rtype: field.rtype, + offsets: field.offsets, + likeptr: field.likeptr, + } + + // Copy over remaining. + t.copy = config.Copy + t.invalid = config.Invalidate +} + +// Index selects index with given name from timeline, else panics. +func (t *Timeline[T, PK]) Index(name string) *Index { + for i, idx := range t.indices { + if idx.name == name { + return &(t.indices[i]) + } + } + panic("unknown index: " + name) +} + +// Select allows you to retrieve a slice of values, in order, from the timeline. +// This slice is defined by the minimum and maximum primary key parameters, up to +// a given length in size. The direction in which you select will determine which +// of the min / max primary key values is used as the *cursor* to begin the start +// of the selection, and which is used as the *boundary* to mark the end, if set. +// In either case, the length parameter is always optional. +// +// dir = Asc : cursors up from 'max' (required), with boundary 'min' (optional). +// dir = Desc : cursors down from 'min' (required), with boundary 'max' (optional). +func (t *Timeline[T, PK]) Select(min, max *PK, length *int, dir Direction) (values []T) { + + // Acquire lock. + t.mutex.Lock() + + // Check init'd. + if t.copy == nil { + t.mutex.Unlock() + panic("not initialized") + } + + switch dir { + case Asc: + // Verify args. + if min == nil { + t.mutex.Unlock() + panic("min must be provided when selecting asc") + } + + // Select determined values ASCENDING. + values = t.select_asc(*min, max, length) + + case Desc: + // Verify args. + if max == nil { + t.mutex.Unlock() + panic("max must be provided when selecting asc") + } + + // Select determined values DESCENDING. + values = t.select_desc(min, *max, length) + } + + // Done with lock. + t.mutex.Unlock() + + return values +} + +// Insert will insert the given values into the timeline, +// calling any set invalidate hook on each inserted value. +func (t *Timeline[T, PK]) Insert(values ...T) { + + // Acquire lock. + t.mutex.Lock() + + // Check init'd. + if t.copy == nil { + t.mutex.Unlock() + panic("not initialized") + } + + // Allocate a slice of our value wrapping struct type. + with_keys := make([]value_with_pk[T, PK], len(values)) + if len(with_keys) != len(values) { + panic("BCE") + } + + // Range the provided values. + for i, value := range values { + + // Create our own copy + // of value to work with. + value = t.copy(value) + + // Take ptr to the value copy. + vptr := unsafe.Pointer(&value) + + // Extract primary key from vptr. + kptr := extract_pkey(vptr, t.pkey) + + var pkey PK + if kptr != nil { + // Cast as PK type. + pkey = *(*PK)(kptr) + } else { + // Use zero value pointer. + kptr = unsafe.Pointer(&pkey) + } + + // Append wrapped value to slice with + // the acquire pointers and primary key. + with_keys[i] = value_with_pk[T, PK]{ + k: pkey, + v: value, + + kptr: kptr, + vptr: vptr, + } + } + + var last *list_elem + + // BEFORE inserting the prepared slice of value copies w/ primary + // keys, sort them by their primary key, ascending. This permits + // us to re-use the 'last' timeline position as next insert cursor. + // Otherwise we would have to iterate from 'head' every single time. + slices.SortFunc(with_keys, func(a, b value_with_pk[T, PK]) int { + const k = +1 + switch { + case a.k < b.k: + return +k + case b.k < a.k: + return -k + default: + return 0 + } + }) + + // Store each value in the timeline, + // updating the last used list element + // each time so we don't have to iter + // down from head on every single store. + for _, value := range with_keys { + last = t.store_one(last, value) + } + + // Get func ptrs. + invalid := t.invalid + + // Done with lock. + t.mutex.Unlock() + + if invalid != nil { + // Pass all invalidated values + // to given user hook (if set). + for _, value := range values { + invalid(value) + } + } +} + +// Invalidate invalidates all entries stored in index under given keys. +// Note that if set, this will call the invalidate hook on each value. +func (t *Timeline[T, PK]) Invalidate(index *Index, keys ...Key) { + if index == nil { + panic("no index given") + } else if index.ptr != unsafe.Pointer(t) { + panic("invalid index for timeline") + } + + // Acquire lock. + t.mutex.Lock() + + // Preallocate expected ret slice. + values := make([]T, 0, len(keys)) + + for i := range keys { + // Delete all items under key from index, collecting + // value items and dropping them from all their indices. + index.delete(keys[i].key, func(item *indexed_item) { + + // Cast to *actual* timeline item. + t_item := to_timeline_item(item) + + if value, ok := item.data.(T); ok { + // No need to copy, as item + // being deleted from cache. + values = append(values, value) + } + + // Delete item. + t.delete(t_item) + }) + } + + // Get func ptrs. + invalid := t.invalid + + // Done with lock. + t.mutex.Unlock() + + if invalid != nil { + // Pass all invalidated values + // to given user hook (if set). + for _, value := range values { + invalid(value) + } + } +} + +// Range will range over all values in the timeline in given direction. +// dir = Asc : ranges from the bottom-up. +// dir = Desc : ranges from the top-down. +// +// Please note that the entire Timeline{} will be locked for the duration of the range +// operation, i.e. from the beginning of the first yield call until the end of the last. +func (t *Timeline[T, PK]) Range(dir Direction) func(yield func(T) bool) { + return func(yield func(T) bool) { + if t.copy == nil { + panic("not initialized") + } else if yield == nil { + panic("nil func") + } + + // Acquire lock. + t.mutex.Lock() + defer t.mutex.Unlock() + + switch dir { + case Asc: + // Iterate through linked list from bottom (i.e. tail). + for prev := t.list.tail; prev != nil; prev = prev.prev { + + // Extract item from list element. + item := (*timeline_item)(prev.data) + + // Create copy of item value. + value := t.copy(item.data.(T)) + + // Pass to given function. + if !yield(value) { + break + } + } + + case Desc: + // Iterate through linked list from top (i.e. head). + for next := t.list.head; next != nil; next = next.next { + + // Extract item from list element. + item := (*timeline_item)(next.data) + + // Create copy of item value. + value := t.copy(item.data.(T)) + + // Pass to given function. + if !yield(value) { + break + } + } + } + } +} + +// RangeKeys will iterate over all values for given keys in the given index. +// +// Please note that the entire Timeline{} will be locked for the duration of the range +// operation, i.e. from the beginning of the first yield call until the end of the last. +func (t *Timeline[T, PK]) RangeKeys(index *Index, keys ...Key) func(yield func(T) bool) { + return func(yield func(T) bool) { + if t.copy == nil { + panic("not initialized") + } else if index == nil { + panic("no index given") + } else if index.ptr != unsafe.Pointer(t) { + panic("invalid index for timeline") + } else if yield == nil { + panic("nil func") + } + + // Acquire lock. + t.mutex.Lock() + defer t.mutex.Unlock() + + for _, key := range keys { + var done bool + + // Iterate over values in index under key. + index.get(key.key, func(i *indexed_item) { + + // Cast to timeline_item type. + item := to_timeline_item(i) + + // Create copy of item value. + value := t.copy(item.data.(T)) + + // Pass val to yield function. + done = done || !yield(value) + }) + + if done { + break + } + } + } +} + +// Trim will remove entries from the timeline in given +// direction, ensuring timeline is no larger than 'max'. +// If 'max' >= t.Len(), this function is a no-op. +// dir = Asc : trims from the bottom-up. +// dir = Desc : trims from the top-down. +func (t *Timeline[T, PK]) Trim(max int, dir Direction) { + // Acquire lock. + t.mutex.Lock() + + // Calculate number to drop. + diff := t.list.len - int(max) + if diff <= 0 { + + // Trim not needed. + t.mutex.Unlock() + return + } + + switch dir { + case Asc: + // Iterate over 'diff' items + // from bottom of timeline list. + for range diff { + + // Get bottom list elem. + bottom := t.list.tail + if bottom == nil { + + // reached + // end. + break + } + + // Drop bottom-most item from timeline. + item := (*timeline_item)(bottom.data) + t.delete(item) + } + + case Desc: + // Iterate over 'diff' items + // from top of timeline list. + for range diff { + + // Get top list elem. + top := t.list.head + if top == nil { + + // reached + // end. + break + } + + // Drop top-most item from timeline. + item := (*timeline_item)(top.data) + t.delete(item) + } + } + + // Compact index data stores. + for _, idx := range t.indices { + (&idx).data.Compact() + } + + // Done with lock. + t.mutex.Unlock() +} + +// Clear empties the timeline by calling .TrimBottom(0, Down). +func (t *Timeline[T, PK]) Clear() { t.Trim(0, Desc) } + +// Len returns the current length of cache. +func (t *Timeline[T, PK]) Len() int { + t.mutex.Lock() + l := t.list.len + t.mutex.Unlock() + return l +} + +// Debug returns debug stats about cache. +func (t *Timeline[T, PK]) Debug() map[string]any { + m := make(map[string]any, 2) + t.mutex.Lock() + m["list"] = t.list.len + indices := make(map[string]any, len(t.indices)) + m["indices"] = indices + for _, idx := range t.indices { + var n uint64 + for _, l := range idx.data.m { + n += uint64(l.len) + } + indices[idx.name] = n + } + t.mutex.Unlock() + return m +} + +func (t *Timeline[T, PK]) select_asc(min PK, max *PK, length *int) (values []T) { + // Iterate through linked list + // from bottom (i.e. tail), asc. + prev := t.list.tail + + // Iterate from 'prev' up, skipping all + // entries with pkey below cursor 'min'. + for ; prev != nil; prev = prev.prev { + item := (*timeline_item)(prev.data) + pkey := *(*PK)(item.pk) + + // Check below min. + if pkey < min { + continue + } + + // Reached + // cursor. + break + } + + if prev == nil { + // No values + // remaining. + return + } + + // Optimized switch case to handle + // each set of argument combinations + // separately, in order to minimize + // number of checks during loops. + switch { + + case length != nil && max != nil: + // Deref arguments. + length := *length + max := *max + + // Optimistic preallocate slice. + values = make([]T, 0, length) + + // Both a length and maximum were given, + // select from cursor until either reached. + for ; prev != nil; prev = prev.prev { + item := (*timeline_item)(prev.data) + pkey := *(*PK)(item.pk) + + // Check above max. + if pkey >= max { + break + } + + // Append value copy. + value := item.data.(T) + value = t.copy(value) + values = append(values, value) + + // Check if length reached. + if len(values) >= length { + break + } + } + + case length != nil: + // Deref length. + length := *length + + // Optimistic preallocate slice. + values = make([]T, 0, length) + + // Only a length was given, select + // from cursor until length reached. + for ; prev != nil; prev = prev.prev { + item := (*timeline_item)(prev.data) + + // Append value copy. + value := item.data.(T) + value = t.copy(value) + values = append(values, value) + + // Check if length reached. + if len(values) >= length { + break + } + } + + case max != nil: + // Deref min. + max := *max + + // Only a maximum was given, select + // from cursor until max is reached. + for ; prev != nil; prev = prev.prev { + item := (*timeline_item)(prev.data) + pkey := *(*PK)(item.pk) + + // Check above max. + if pkey >= max { + break + } + + // Append value copy. + value := item.data.(T) + value = t.copy(value) + values = append(values, value) + } + + default: + // No maximum or length were given, + // ALL from cursor need selecting. + for ; prev != nil; prev = prev.prev { + item := (*timeline_item)(prev.data) + + // Append value copy. + value := item.data.(T) + value = t.copy(value) + values = append(values, value) + } + } + + return +} + +func (t *Timeline[T, PK]) select_desc(min *PK, max PK, length *int) (values []T) { + // Iterate through linked list + // from top (i.e. head), desc. + next := t.list.head + + // Iterate from 'next' down, skipping + // all entries with pkey above cursor 'max'. + for ; next != nil; next = next.next { + item := (*timeline_item)(next.data) + pkey := *(*PK)(item.pk) + + // Check above max. + if pkey > max { + continue + } + + // Reached + // cursor. + break + } + + if next == nil { + // No values + // remaining. + return + } + + // Optimized switch case to handle + // each set of argument combinations + // separately, in order to minimize + // number of checks during loops. + switch { + + case length != nil && min != nil: + // Deref arguments. + length := *length + min := *min + + // Optimistic preallocate slice. + values = make([]T, 0, length) + + // Both a length and minimum were given, + // select from cursor until either reached. + for ; next != nil; next = next.next { + item := (*timeline_item)(next.data) + pkey := *(*PK)(item.pk) + + // Check below min. + if pkey <= min { + break + } + + // Append value copy. + value := item.data.(T) + value = t.copy(value) + values = append(values, value) + + // Check if length reached. + if len(values) >= length { + break + } + } + + case length != nil: + // Deref length. + length := *length + + // Optimistic preallocate slice. + values = make([]T, 0, length) + + // Only a length was given, select + // from cursor until length reached. + for ; next != nil; next = next.next { + item := (*timeline_item)(next.data) + + // Append value copy. + value := item.data.(T) + value = t.copy(value) + values = append(values, value) + + // Check if length reached. + if len(values) >= length { + break + } + } + + case min != nil: + // Deref min. + min := *min + + // Only a minimum was given, select + // from cursor until minimum reached. + for ; next != nil; next = next.next { + item := (*timeline_item)(next.data) + pkey := *(*PK)(item.pk) + + // Check below min. + if pkey <= min { + break + } + + // Append value copy. + value := item.data.(T) + value = t.copy(value) + values = append(values, value) + } + + default: + // No minimum or length were given, + // ALL from cursor need selecting. + for ; next != nil; next = next.next { + item := (*timeline_item)(next.data) + + // Append value copy. + value := item.data.(T) + value = t.copy(value) + values = append(values, value) + } + } + + return +} + +// value_with_pk wraps an incoming value type, with +// its extracted primary key, and pointers to both. +// this encompasses all arguments related to a value +// required by store_one(), simplifying some logic. +// +// with all the primary keys extracted, it also +// makes it much easier to sort input before insert. +type value_with_pk[T any, PK comparable] struct { + k PK // primary key value + v T // value copy + + kptr unsafe.Pointer // primary key ptr + vptr unsafe.Pointer // value copy ptr +} + +func (t *Timeline[T, PK]) store_one(last *list_elem, value value_with_pk[T, PK]) *list_elem { + // NOTE: the value passed here should + // already be a copy of the original. + + // Alloc new index item. + t_item := new_timeline_item() + if cap(t_item.indexed) < len(t.indices) { + + // Preallocate item indices slice to prevent Go auto + // allocating overlying large slices we don't need. + t_item.indexed = make([]*index_entry, 0, len(t.indices)) + } + + // Set item value data. + t_item.data = value.v + t_item.pk = value.kptr + + // Acquire key buf. + buf := new_buffer() + + // Convert to indexed_item ptr. + i_item := from_timeline_item(t_item) + + // Append already-extracted + // primary key to 0th index. + idx := (&t.indices[0]) + partptrs := []unsafe.Pointer{value.kptr} + key := idx.key(buf, partptrs) + evicted := idx.append(key, i_item) + if evicted != nil { + + // This item is no longer + // indexed, remove from list. + t.list.remove(&evicted.elem) + + // Now convert from index_item ptr + // and release it to global mem pool. + evicted := to_timeline_item(evicted) + free_timeline_item(evicted) + } + + for i := 1; i < len(t.indices); i++ { + // Get current index ptr. + idx := (&t.indices[i]) + + // Extract fields comprising index key from value. + parts := extract_fields(value.vptr, idx.fields) + + // Calculate this index key. + key := idx.key(buf, parts) + if key == "" { + continue + } + + // Append this item to index. + evicted := idx.append(key, i_item) + if evicted != nil { + + // This item is no longer + // indexed, remove from list. + t.list.remove(&evicted.elem) + + // Now convert from index_item ptr + // and release it to global mem pool. + evicted := to_timeline_item(evicted) + free_timeline_item(evicted) + } + } + + // Done with buf. + free_buffer(buf) + + if last == nil { + // No previous element was provided, this is + // first insert, we need to work from head. + + // Check for emtpy head. + if t.list.head == nil { + + // The easiest case, this will + // be the first item in list. + t.list.push_front(&t_item.elem) + return t.list.head + } + + // Extract head item and its primary key. + headItem := (*timeline_item)(t.list.head.data) + headPK := *(*PK)(headItem.pk) + if value.k >= headPK { + + // Another easier case, this also + // will be the first item in list. + t.list.push_front(&t_item.elem) + return t.list.head + } + + // Set last=head + // to work from. + last = t.list.head + } + + // Iterate through linked list + // from head to find location. + for next := last.next; // + next != nil; next = next.next { + + // Extract item and it's primary key. + nextItem := (*timeline_item)(next.data) + nextPK := *(*PK)(nextItem.pk) + + // If pkey smaller than + // cursor's, keep going. + if value.k < nextPK { + continue + } + + // New pkey is larger than cursor, + // insert into list just before it. + t.list.insert(&t_item.elem, next.prev) + return next + } + + // We reached the end of the + // list, insert at tail pos. + t.list.push_back(&t_item.elem) + return t.list.tail +} + +func (t *Timeline[T, PK]) delete(i *timeline_item) { + for len(i.indexed) != 0 { + // Pop last indexed entry from list. + entry := i.indexed[len(i.indexed)-1] + i.indexed[len(i.indexed)-1] = nil + i.indexed = i.indexed[:len(i.indexed)-1] + + // Get entry's index. + index := entry.index + + // Drop this index_entry. + index.delete_entry(entry) + } + + // Drop from main list. + t.list.remove(&i.elem) + + // Free unused item. + free_timeline_item(i) +} + +type timeline_item struct { + indexed_item + + // retains fast ptr access + // to primary key value of + // above indexed_item{}.data + pk unsafe.Pointer + + // check bits always all set + // to 1. used to ensure cast + // from indexed_item to this + // type was originally a + // timeline_item to begin with. + ck uint +} + +func init() { + // ensure the embedded indexed_item struct is ALWAYS at zero offset. + // we rely on this to allow a ptr to one to be a ptr to either of them. + const off = unsafe.Offsetof(timeline_item{}.indexed_item) + if off != 0 { + panic("invalid timeline_item{}.indexed_item offset") + } +} + +// from_timeline_item converts a timeline_item ptr to indexed_item, given the above init() guarantee. +func from_timeline_item(item *timeline_item) *indexed_item { + return (*indexed_item)(unsafe.Pointer(item)) +} + +// to_timeline_item converts an indexed_item ptr to timeline_item, given the above init() guarantee. +// NOTE THIS MUST BE AN indexed_item THAT WAS INITIALLY CONVERTED WITH from_timeline_item(). +func to_timeline_item(item *indexed_item) *timeline_item { + to := (*timeline_item)(unsafe.Pointer(item)) + if to.ck != ^uint(0) { + // ensure check bits are + // set indicating it was a + // timeline_item originally. + should_not_reach(true) + } + return to +} + +var timeline_item_pool sync.Pool + +// new_timeline_item returns a new prepared timeline_item. +func new_timeline_item() *timeline_item { + v := timeline_item_pool.Get() + if v == nil { + i := new(timeline_item) + i.elem.data = unsafe.Pointer(i) + i.ck = ^uint(0) + v = i + } + item := v.(*timeline_item) + return item +} + +// free_timeline_item releases the timeline_item. +func free_timeline_item(item *timeline_item) { + if len(item.indexed) > 0 || + item.elem.next != nil || + item.elem.prev != nil { + should_not_reach(false) + return + } + item.data = nil + item.pk = nil + timeline_item_pool.Put(item) +} |