stamp

type Coalescing ¶

type Coalescing interface {
	Stamped

	// Coalesce may be implemented to allow the tail node in the queue
	// to be coalesced with some proposed value to be added to the end
	// of the queue. Implementations should modify the callee as
	// appropriate to append the next tail value. This method can return
	// an alternate, non-nil value to still be added to the queue. If
	// this method returns nil, then the tail value will be considered
	// to have been fully coalesced and no new value will be added to
	// the queue.
	Coalesce(tail Stamped) (remainder Stamped)
}

Coalescing is an optional interface that may be implemented by Stamped values.

type MinMap ¶

type MinMap struct {
	// contains filtered or unexported fields
}

A MinMap provides a mapping of keys to Stamp values, while also tracking the minimum value.

A MinMap is not internally synchronized. A MinMap should not be copied once created.

func NewMinMap() *MinMap

func (m *MinMap) Delete(key any)

func (m *MinMap) Get(key any) (Stamp, bool)

func (m *MinMap) Len() int

func (m *MinMap) Min() Stamp

func (m *MinMap) Put(key any, stamp Stamp) (minStamp Stamp, minChanged bool)

type Queue ¶

type Queue struct {
	// contains filtered or unexported fields
}

Queue maintains ordered Stamped values.

Draining values from the queue advances a "consistent point", derived from the stamps of the dequeued values and a queue of candidate, "marker" stamps. The lowest-valued marker becomes the consistent point when there are no more stamped values in the queue whose stamps are less than the marker.

Queue is not internally synchronized. The zero value is ready to use. A Queue should not be copied once created.

At present, this implementation assumes that it is being driven from a serial source of data that provides monotonic stamps. It would be possible to extend the behavior to allow for out-of-order insertion, albeit with increased algorithmic complexity, provided that the stamp of the enqueued value is still greater than the consistent point.

The following Stamp-ordering invariants are maintained:

1. values[0] <= values[1] ... <= values[n] (softly monotonic)
2. markers[0] < markers[1] ... < markers[n] (strictly monotonic)
3. consistent < values[0]
4. consistent < markers[0]
5. consistent > previousConsistent.

func (s *Queue) Consistent() Stamp

func (s *Queue) Dequeue() Stamped

func (s *Queue) Enqueue(next Stamped) error

func (s *Queue) Mark(marker Stamp) error

func (s *Queue) Markers(buf []Stamp) []Stamp

func (s *Queue) Peek() Stamped

func (s *Queue) PeekMarker() Stamp

func (s *Queue) Values(buf []Stamped) []Stamped

type Stamp ¶

type Stamp interface {
	// Less returns true if the callee should be sorted before the other
	// Stamp.
	Less(other Stamp) bool
}

A Stamp is a comparable value (possibly a time, or an offset within a log file). Stamp implementations will be marshaled using the json package.

type Stamped ¶

type Stamped interface {
	// Stamp returns the Stamp associated with the value.
	Stamp() Stamp
}

A Stamped value has some key by which it can be ordered.