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 1 : func makeObjID(t objTag, slot uint32) objID {
43 1 : return objID((uint32(t) << 28) | slot)
44 1 : }
45 :
46 1 : func (i objID) tag() objTag {
47 1 : return objTag(i >> 28)
48 1 : }
49 :
50 1 : func (i objID) slot() uint32 {
51 1 : return uint32(i) & ((1 << 28) - 1)
52 1 : }
53 :
54 1 : func (i objID) String() string {
55 1 : return fmt.Sprintf("%s%d", objTagPrefix[i.tag()], i.slot())
56 1 : }
57 :
58 1 : func parseObjID(str string) (objID, error) {
59 1 : // To provide backward compatibility, treat "db" as "db1". Note that unlike
60 1 : // the others, db slots are 1-indexed.
61 1 : if str == "db" {
62 1 : str = "db1"
63 1 : }
64 1 : for tag := objTag(1); tag < numObjTags; tag++ {
65 1 : if strings.HasPrefix(str, objTagPrefix[tag]) {
66 1 : id, err := strconv.ParseInt(str[len(objTagPrefix[tag]):], 10, 32)
67 1 : if err != nil {
68 0 : return 0, err
69 0 : }
70 1 : 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 1 : func firstError(err0, err1 error) error {
121 1 : if err0 != nil {
122 0 : return err0
123 0 : }
124 1 : return err1
125 : }
|