queue.go

     1  // Copyright 2021 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  package fuzz
     6  
     7  // queue holds a growable sequence of inputs for fuzzing and minimization.
     8  //
     9  // For now, this is a simple ring buffer
    10  // (https://en.wikipedia.org/wiki/Circular_buffer).
    11  //
    12  // TODO(golang.org/issue/46224): use a priotization algorithm based on input
    13  // size, previous duration, coverage, and any other metrics that seem useful.
    14  type queue struct {
    15  	// elems holds a ring buffer.
    16  	// The queue is empty when begin = end.
    17  	// The queue is full (until grow is called) when end = begin + N - 1 (mod N)
    18  	// where N = cap(elems).
    19  	elems     []any
    20  	head, len int
    21  }
    22  
    23  func (q *queue) cap() int {
    24  	return len(q.elems)
    25  }
    26  
    27  func (q *queue) grow() {
    28  	oldCap := q.cap()
    29  	newCap := oldCap * 2
    30  	if newCap == 0 {
    31  		newCap = 8
    32  	}
    33  	newElems := make([]any, newCap)
    34  	oldLen := q.len
    35  	for i := 0; i < oldLen; i++ {
    36  		newElems[i] = q.elems[(q.head+i)%oldCap]
    37  	}
    38  	q.elems = newElems
    39  	q.head = 0
    40  }
    41  
    42  func (q *queue) enqueue(e any) {
    43  	if q.len+1 > q.cap() {
    44  		q.grow()
    45  	}
    46  	i := (q.head + q.len) % q.cap()
    47  	q.elems[i] = e
    48  	q.len++
    49  }
    50  
    51  func (q *queue) dequeue() (any, bool) {
    52  	if q.len == 0 {
    53  		return nil, false
    54  	}
    55  	e := q.elems[q.head]
    56  	q.elems[q.head] = nil
    57  	q.head = (q.head + 1) % q.cap()
    58  	q.len--
    59  	return e, true
    60  }
    61  
    62  func (q *queue) peek() (any, bool) {
    63  	if q.len == 0 {
    64  		return nil, false
    65  	}
    66  	return q.elems[q.head], true
    67  }
    68  
    69  func (q *queue) clear() {
    70  	*q = queue{}
    71  }
    72
View as plain text