stamp

Documentation

Overview

Package stamp contains a utility for maintaining certain ordering invariants when queuing (time-)stamped values.

Index

• func Compare(a, b Stamp) int
• type Coalescing
• type MinMap
  • 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
  • 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 Stamped

Functions

func Compare

func Compare(a, b Stamp) int

Compare returns -1, 0, or 1 if a is less than, equal to, or greater than b. This function is nil-safe; a nil Stamp is less than any non-nil Stamp.

Types

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

func NewMinMap() *MinMap

NewMinMap constructs an empty MinMap.

func (*MinMap) Delete

func (m *MinMap) Delete(key any)

Delete removes the mapping for the specified key, if one is present.

func (*MinMap) Get

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

Get returns the previously set Stamp for the key, or nil if no mapping is present.

func (*MinMap) Len

func (m *MinMap) Len() int

Len returns the number of elements within the map.

func (*MinMap) Min

func (m *MinMap) Min() Stamp

Min returns the minimum Stamp in the map, or nil if the map is empty.

func (*MinMap) Put

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

Put adds or updates an entry in the map. This method returns the minimum Stamp within the map and a boolean flag to indicate if the call to Put changed the minimum value.

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 (*Queue) Consistent

func (s *Queue) Consistent() Stamp

Consistent returns a Stamp which is less than the stamps of all enqueued values or markers. This value will be nil if none of Dequeue, Mark, or setConsistent have been called.

func (*Queue) Dequeue

func (s *Queue) Dequeue() Stamped

Dequeue returns the next Stamped value, or nil if the Queue is empty. Draining a value will advance the consistent point to the greatest marker that is strictly less than the Stamp of the value returned. That is, the consistent Stamp will be in the half-open range of [ nil, Dequeue().Stamp() ).

func (*Queue) Enqueue

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

Enqueue adds a Stamped value to the end of the queue. If the tail value in the Queue implements Coalescing, the Queue will attempt to merge the tail and next values.

func (*Queue) Mark

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

Mark adds a potential future consistent point to the Queue. This method will update the consistent point if the new marker is greater than the current consistent point and less than the stamp of the head of the queue or if the queue is empty.

func (*Queue) Markers

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

Markers appends all markers passed to Mark that are greater than the current consistent point. The modified slice is returned.

func (*Queue) Peek

func (s *Queue) Peek() Stamped

Peek returns the value at the head of the queue, without modifying it.

func (*Queue) PeekMarker

func (s *Queue) PeekMarker() Stamp

PeekMarker returns the head of the markers queue, without modifying it.

func (*Queue) Values

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

Values appends all Stamped values in the Queue. The modified slice is returned.

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.