batchcursor.go

Documentation: golang.org/x/exp/trace

     1  // Copyright 2023 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Code generated by "gen.bash" from internal/trace/v2; DO NOT EDIT.
     6  
     7  //go:build go1.21
     8  
     9  package trace
    10  
    11  import (
    12  	"cmp"
    13  	"encoding/binary"
    14  	"fmt"
    15  
    16  	"golang.org/x/exp/trace/internal/event"
    17  	"golang.org/x/exp/trace/internal/event/go122"
    18  )
    19  
    20  type batchCursor struct {
    21  	m       ThreadID
    22  	lastTs  Time
    23  	idx     int       // next index into []batch
    24  	dataOff int       // next index into batch.data
    25  	ev      baseEvent // last read event
    26  }
    27  
    28  func (b *batchCursor) nextEvent(batches []batch, freq frequency) (ok bool, err error) {
    29  	// Batches should generally always have at least one event,
    30  	// but let's be defensive about that and accept empty batches.
    31  	for b.idx < len(batches) && len(batches[b.idx].data) == b.dataOff {
    32  		b.idx++
    33  		b.dataOff = 0
    34  		b.lastTs = 0
    35  	}
    36  	// Have we reached the end of the batches?
    37  	if b.idx == len(batches) {
    38  		return false, nil
    39  	}
    40  	// Initialize lastTs if it hasn't been yet.
    41  	if b.lastTs == 0 {
    42  		b.lastTs = freq.mul(batches[b.idx].time)
    43  	}
    44  	// Read an event out.
    45  	n, tsdiff, err := readTimedBaseEvent(batches[b.idx].data[b.dataOff:], &b.ev)
    46  	if err != nil {
    47  		return false, err
    48  	}
    49  	// Complete the timestamp from the cursor's last timestamp.
    50  	b.ev.time = freq.mul(tsdiff) + b.lastTs
    51  
    52  	// Move the cursor's timestamp forward.
    53  	b.lastTs = b.ev.time
    54  
    55  	// Move the cursor forward.
    56  	b.dataOff += n
    57  	return true, nil
    58  }
    59  
    60  func (b *batchCursor) compare(a *batchCursor) int {
    61  	return cmp.Compare(b.ev.time, a.ev.time)
    62  }
    63  
    64  // readTimedBaseEvent reads out the raw event data from b
    65  // into e. It does not try to interpret the arguments
    66  // but it does validate that the event is a regular
    67  // event with a timestamp (vs. a structural event).
    68  //
    69  // It requires that the event its reading be timed, which must
    70  // be the case for every event in a plain EventBatch.
    71  func readTimedBaseEvent(b []byte, e *baseEvent) (int, timestamp, error) {
    72  	// Get the event type.
    73  	typ := event.Type(b[0])
    74  	specs := go122.Specs()
    75  	if int(typ) >= len(specs) {
    76  		return 0, 0, fmt.Errorf("found invalid event type: %v", typ)
    77  	}
    78  	e.typ = typ
    79  
    80  	// Get spec.
    81  	spec := &specs[typ]
    82  	if len(spec.Args) == 0 || !spec.IsTimedEvent {
    83  		return 0, 0, fmt.Errorf("found event without a timestamp: type=%v", typ)
    84  	}
    85  	n := 1
    86  
    87  	// Read timestamp diff.
    88  	ts, nb := binary.Uvarint(b[n:])
    89  	if nb <= 0 {
    90  		return 0, 0, fmt.Errorf("found invalid uvarint for timestamp")
    91  	}
    92  	n += nb
    93  
    94  	// Read the rest of the arguments.
    95  	for i := 0; i < len(spec.Args)-1; i++ {
    96  		arg, nb := binary.Uvarint(b[n:])
    97  		if nb <= 0 {
    98  			return 0, 0, fmt.Errorf("found invalid uvarint")
    99  		}
   100  		e.args[i] = arg
   101  		n += nb
   102  	}
   103  	return n, timestamp(ts), nil
   104  }
   105  
   106  func heapInsert(heap []*batchCursor, bc *batchCursor) []*batchCursor {
   107  	// Add the cursor to the end of the heap.
   108  	heap = append(heap, bc)
   109  
   110  	// Sift the new entry up to the right place.
   111  	heapSiftUp(heap, len(heap)-1)
   112  	return heap
   113  }
   114  
   115  func heapUpdate(heap []*batchCursor, i int) {
   116  	// Try to sift up.
   117  	if heapSiftUp(heap, i) != i {
   118  		return
   119  	}
   120  	// Try to sift down, if sifting up failed.
   121  	heapSiftDown(heap, i)
   122  }
   123  
   124  func heapRemove(heap []*batchCursor, i int) []*batchCursor {
   125  	// Sift index i up to the root, ignoring actual values.
   126  	for i > 0 {
   127  		heap[(i-1)/2], heap[i] = heap[i], heap[(i-1)/2]
   128  		i = (i - 1) / 2
   129  	}
   130  	// Swap the root with the last element, then remove it.
   131  	heap[0], heap[len(heap)-1] = heap[len(heap)-1], heap[0]
   132  	heap = heap[:len(heap)-1]
   133  	// Sift the root down.
   134  	heapSiftDown(heap, 0)
   135  	return heap
   136  }
   137  
   138  func heapSiftUp(heap []*batchCursor, i int) int {
   139  	for i > 0 && heap[(i-1)/2].ev.time > heap[i].ev.time {
   140  		heap[(i-1)/2], heap[i] = heap[i], heap[(i-1)/2]
   141  		i = (i - 1) / 2
   142  	}
   143  	return i
   144  }
   145  
   146  func heapSiftDown(heap []*batchCursor, i int) int {
   147  	for {
   148  		m := min3(heap, i, 2*i+1, 2*i+2)
   149  		if m == i {
   150  			// Heap invariant already applies.
   151  			break
   152  		}
   153  		heap[i], heap[m] = heap[m], heap[i]
   154  		i = m
   155  	}
   156  	return i
   157  }
   158  
   159  func min3(b []*batchCursor, i0, i1, i2 int) int {
   160  	minIdx := i0
   161  	minT := maxTime
   162  	if i0 < len(b) {
   163  		minT = b[i0].ev.time
   164  	}
   165  	if i1 < len(b) {
   166  		if t := b[i1].ev.time; t < minT {
   167  			minT = t
   168  			minIdx = i1
   169  		}
   170  	}
   171  	if i2 < len(b) {
   172  		if t := b[i2].ev.time; t < minT {
   173  			minT = t
   174  			minIdx = i2
   175  		}
   176  	}
   177  	return minIdx
   178  }
   179
View as plain text