Fuzz tester for B+ Tree with operation tracking and reference comparison
| 31 | |
| 32 | |
| 33 | class BPlusTreeFuzzTester: |
| 34 | """Fuzz tester for B+ Tree with operation tracking and reference comparison""" |
| 35 | |
| 36 | def __init__(self, capacity: int = 16, seed: int = None, prepopulate: int = 0): |
| 37 | self.capacity = capacity |
| 38 | self.seed = seed or random.randint(1, 1000000) |
| 39 | self.prepopulate = prepopulate |
| 40 | random.seed(self.seed) |
| 41 | |
| 42 | # Initialize data structures |
| 43 | self.btree = BPlusTreeMap(capacity=capacity) |
| 44 | self.reference = OrderedDict() |
| 45 | |
| 46 | # Pre-populate if requested |
| 47 | if prepopulate > 0: |
| 48 | self._prepopulate_tree(prepopulate) |
| 49 | |
| 50 | # Operation tracking for debugging |
| 51 | self.operations: List[Tuple[str, Any, Any]] = [] |
| 52 | self.operation_count = 0 |
| 53 | |
| 54 | # Statistics |
| 55 | self.stats = { |
| 56 | "insert": 0, |
| 57 | "delete": 0, |
| 58 | "update": 0, |
| 59 | "get": 0, |
| 60 | "batch_delete": 0, |
| 61 | "compact": 0, |
| 62 | "errors": 0, |
| 63 | "prepopulate": prepopulate, |
| 64 | } |
| 65 | |
| 66 | def log_operation( |
| 67 | self, op_type: str, key: Any = None, value: Any = None, extra: Any = None |
| 68 | ): |
| 69 | """Log an operation for replay in case of errors""" |
| 70 | self.operations.append((op_type, key, value, extra)) |
| 71 | self.operation_count += 1 |
| 72 | self.stats[op_type] = self.stats.get(op_type, 0) + 1 |
| 73 | |
| 74 | def _prepopulate_tree(self, count: int) -> None: |
| 75 | """Pre-populate the tree with a specified number of elements to create complex structure""" |
| 76 | print(f"Pre-populating tree with {count} elements...") |
| 77 | |
| 78 | # Use a different random state for prepopulation to ensure variety |
| 79 | prepop_state = random.getstate() |
| 80 | random.seed(self.seed + 12345) # Offset seed for prepopulation |
| 81 | |
| 82 | try: |
| 83 | # Insert keys in a pattern that creates a well-distributed tree |
| 84 | keys_to_insert = set() |
| 85 | |
| 86 | # Generate unique keys |
| 87 | while len(keys_to_insert) < count: |
| 88 | # Use a mix of patterns to ensure good tree structure |
| 89 | if len(keys_to_insert) < count // 2: |
| 90 | # First half: sequential with gaps |
no outgoing calls