Line data    Source code

       1             : // Copyright 2019 The LevelDB-Go and Pebble Authors. All rights reserved. Use
       2             : // of this source code is governed by a BSD-style license that can be found in
       3             : // the LICENSE file.
       4             : 
       5             : package metamorphic
       6             : 
       7             : import (
       8             :         "fmt"
       9             :         "sort"
      10             : 
      11             :         "golang.org/x/exp/rand"
      12             : )
      13             : 
      14             : // objTag identifies the type for an object: DB, Batch, Iter, or Snapshot.
      15             : type objTag uint8
      16             : 
      17             : const (
      18             :         dbTag objTag = iota + 1
      19             :         batchTag
      20             :         iterTag
      21             :         snapTag
      22             : )
      23             : 
      24             : // objID identifies a particular object. The top 4-bits store the tag
      25             : // identifying the type of object, while the bottom 28-bits store the slot used
      26             : // to index with the test.{batches,iters,snapshots} slices.
      27             : type objID uint32
      28             : 
      29           1 : func makeObjID(t objTag, slot uint32) objID {
      30           1 :         return objID((uint32(t) << 28) | slot)
      31           1 : }
      32             : 
      33           1 : func (i objID) tag() objTag {
      34           1 :         return objTag(i >> 28)
      35           1 : }
      36             : 
      37           1 : func (i objID) slot() uint32 {
      38           1 :         return uint32(i) & ((1 << 28) - 1)
      39           1 : }
      40             : 
      41           1 : func (i objID) String() string {
      42           1 :         switch i.tag() {
      43           1 :         case dbTag:
      44           1 :                 return fmt.Sprintf("db%d", i.slot())
      45           1 :         case batchTag:
      46           1 :                 return fmt.Sprintf("batch%d", i.slot())
      47           1 :         case iterTag:
      48           1 :                 return fmt.Sprintf("iter%d", i.slot())
      49           1 :         case snapTag:
      50           1 :                 return fmt.Sprintf("snap%d", i.slot())
      51             :         }
      52           0 :         return fmt.Sprintf("unknown%d", i.slot())
      53             : }
      54             : 
      55             : // objIDSlice is an unordered set of integers used when random selection of an
      56             : // element is required.
      57             : type objIDSlice []objID
      58             : 
      59           1 : func (s objIDSlice) Len() int           { return len(s) }
      60           1 : func (s objIDSlice) Less(i, j int) bool { return s[i] < s[j] }
      61           1 : func (s objIDSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
      62             : 
      63             : // Remove removes the specified integer from the set.
      64             : //
      65             : // TODO(peter): If this proves slow, we can replace this implementation with a
      66             : // map and a slice. The slice would provide for random selection of an element,
      67             : // while the map would provide quick location of an element to remove.
      68           1 : func (s *objIDSlice) remove(id objID) {
      69           1 :         n := len(*s)
      70           1 :         for j := 0; j < n; j++ {
      71           1 :                 if (*s)[j] == id {
      72           1 :                         (*s)[j], (*s)[n-1] = (*s)[n-1], (*s)[j]
      73           1 :                         (*s) = (*s)[:n-1]
      74           1 :                         break
      75             :                 }
      76             :         }
      77             : }
      78             : 
      79           1 : func (s *objIDSlice) rand(rng *rand.Rand) objID {
      80           1 :         return (*s)[rng.Intn(len(*s))]
      81           1 : }
      82             : 
      83             : // objIDSet is an unordered set of object IDs.
      84             : type objIDSet map[objID]struct{}
      85             : 
      86             : // sortedKeys returns a sorted slice of the set's keys for deterministic
      87             : // iteration.
      88           1 : func (s objIDSet) sorted() []objID {
      89           1 :         keys := make(objIDSlice, 0, len(s))
      90           1 :         for id := range s {
      91           1 :                 keys = append(keys, id)
      92           1 :         }
      93           1 :         sort.Sort(keys)
      94           1 :         return keys
      95             : }
      96             : 
      97             : // firstError returns the first non-nil error of err0 and err1, or nil if both
      98             : // are nil.
      99           1 : func firstError(err0, err1 error) error {
     100           1 :         if err0 != nil {
     101           0 :                 return err0
     102           0 :         }
     103           1 :         return err1
     104             : }