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             :         "strconv"
      11             :         "strings"
      12             : 
      13             :         "github.com/cockroachdb/errors"
      14             :         "golang.org/x/exp/rand"
      15             : )
      16             : 
      17             : // objTag identifies the type for an object: DB, Batch, Iter, or Snapshot.
      18             : type objTag uint8
      19             : 
      20             : const (
      21             :         dbTag objTag = iota + 1
      22             :         batchTag
      23             :         iterTag
      24             :         snapTag
      25             :         externalObjTag
      26             :         numObjTags
      27             : )
      28             : 
      29             : var objTagPrefix = [numObjTags]string{
      30             :         dbTag:          "db",
      31             :         batchTag:       "batch",
      32             :         iterTag:        "iter",
      33             :         snapTag:        "snap",
      34             :         externalObjTag: "external",
      35             : }
      36             : 
      37             : // objID identifies a particular object. The top 4-bits store the tag
      38             : // identifying the type of object, while the bottom 28-bits store the slot used
      39             : // to index with the test.{batches,iters,snapshots,externalObjs} slices.
      40             : type objID uint32
      41             : 
      42           2 : func makeObjID(t objTag, slot uint32) objID {
      43           2 :         return objID((uint32(t) << 28) | slot)
      44           2 : }
      45             : 
      46           2 : func (i objID) tag() objTag {
      47           2 :         return objTag(i >> 28)
      48           2 : }
      49             : 
      50           2 : func (i objID) slot() uint32 {
      51           2 :         return uint32(i) & ((1 << 28) - 1)
      52           2 : }
      53             : 
      54           2 : func (i objID) String() string {
      55           2 :         return fmt.Sprintf("%s%d", objTagPrefix[i.tag()], i.slot())
      56           2 : }
      57             : 
      58           2 : func parseObjID(str string) (objID, error) {
      59           2 :         // To provide backward compatibility, treat "db" as "db1". Note that unlike
      60           2 :         // the others, db slots are 1-indexed.
      61           2 :         if str == "db" {
      62           1 :                 str = "db1"
      63           1 :         }
      64           2 :         for tag := objTag(1); tag < numObjTags; tag++ {
      65           2 :                 if strings.HasPrefix(str, objTagPrefix[tag]) {
      66           2 :                         id, err := strconv.ParseInt(str[len(objTagPrefix[tag]):], 10, 32)
      67           2 :                         if err != nil {
      68           0 :                                 return 0, err
      69           0 :                         }
      70           2 :                         return makeObjID(tag, uint32(id)), nil
      71             :                 }
      72             :         }
      73           1 :         return 0, errors.Newf("unknown object type: %q", str)
      74             : }
      75             : 
      76             : // objIDSlice is an unordered set of integers used when random selection of an
      77             : // element is required.
      78             : type objIDSlice []objID
      79             : 
      80           1 : func (s objIDSlice) Len() int           { return len(s) }
      81           1 : func (s objIDSlice) Less(i, j int) bool { return s[i] < s[j] }
      82           1 : func (s objIDSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
      83             : 
      84             : // Remove removes the specified integer from the set.
      85             : //
      86             : // TODO(peter): If this proves slow, we can replace this implementation with a
      87             : // map and a slice. The slice would provide for random selection of an element,
      88             : // while the map would provide quick location of an element to remove.
      89           1 : func (s *objIDSlice) remove(id objID) {
      90           1 :         n := len(*s)
      91           1 :         for j := 0; j < n; j++ {
      92           1 :                 if (*s)[j] == id {
      93           1 :                         (*s)[j], (*s)[n-1] = (*s)[n-1], (*s)[j]
      94           1 :                         (*s) = (*s)[:n-1]
      95           1 :                         break
      96             :                 }
      97             :         }
      98             : }
      99             : 
     100           1 : func (s *objIDSlice) rand(rng *rand.Rand) objID {
     101           1 :         return (*s)[rng.Intn(len(*s))]
     102           1 : }
     103             : 
     104             : // objIDSet is an unordered set of object IDs.
     105             : type objIDSet map[objID]struct{}
     106             : 
     107             : // sortedKeys returns a sorted slice of the set's keys for deterministic
     108             : // iteration.
     109           1 : func (s objIDSet) sorted() []objID {
     110           1 :         keys := make(objIDSlice, 0, len(s))
     111           1 :         for id := range s {
     112           1 :                 keys = append(keys, id)
     113           1 :         }
     114           1 :         sort.Sort(keys)
     115           1 :         return keys
     116             : }
     117             : 
     118             : // firstError returns the first non-nil error of err0 and err1, or nil if both
     119             : // are nil.
     120           2 : func firstError(err0, err1 error) error {
     121           2 :         if err0 != nil {
     122           0 :                 return err0
     123           0 :         }
     124           2 :         return err1
     125             : }