1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
/*
* Copyright (C) 2024, Thomas Wolf <twolf@apache.org> and others
*
* This program and the accompanying materials are made available under the
* terms of the Eclipse Distribution License v. 1.0 which is available at
* https://www.eclipse.org/org/documents/edl-v10.php.
*
* SPDX-License-Identifier: BSD-3-Clause
*/
package org.eclipse.jgit.internal.signing.ssh;
import java.util.TreeMap;
import org.eclipse.jgit.internal.transport.sshd.SshdText;
/**
* Encapsulates the storage for revoked certificate serial numbers.
*/
class SerialRangeSet {
/**
* A range of certificate serial numbers [from..to], i.e., with both range
* limits included.
*/
private interface SerialRange {
long from();
long to();
}
private static record Singleton(long from) implements SerialRange {
@Override
public long to() {
return from;
}
}
private static record Range(long from, long to) implements SerialRange {
public Range(long from, long to) {
if (Long.compareUnsigned(from, to) > 0) {
throw new IllegalArgumentException(
SshdText.get().signKrlEmptyRange);
}
this.from = from;
this.to = to;
}
}
// We use the same data structure as OpenSSH; basically a TreeSet of mutable
// SerialRanges. To get "mutability", the set is implemented as a TreeMap
// with the same elements as keys and values.
//
// get(x) will return null if none of the serial numbers in the range x is
// in the set, and some range (partially) overlapping with x otherwise.
//
// containsKey(x) will return true if there is any (partially) overlapping
// range in the TreeMap.
private final TreeMap<SerialRange, SerialRange> ranges = new TreeMap<>(
SerialRangeSet::compare);
private static int compare(SerialRange a, SerialRange b) {
// Return == if they overlap
if (Long.compareUnsigned(a.to(), b.from()) >= 0
&& Long.compareUnsigned(a.from(), b.to()) <= 0) {
return 0;
}
return Long.compareUnsigned(a.from(), b.from());
}
void add(long serial) {
add(ranges, new Singleton(serial));
}
void add(long from, long to) {
add(ranges, new Range(from, to));
}
boolean contains(long serial) {
return ranges.containsKey(new Singleton(serial));
}
int size() {
return ranges.size();
}
boolean isEmpty() {
return ranges.isEmpty();
}
private static void add(TreeMap<SerialRange, SerialRange> ranges,
SerialRange newRange) {
for (;;) {
SerialRange existing = ranges.get(newRange);
if (existing == null) {
break;
}
if (Long.compareUnsigned(existing.from(), newRange.from()) <= 0
&& Long.compareUnsigned(existing.to(),
newRange.to()) >= 0) {
// newRange completely contained in existing
return;
}
ranges.remove(existing);
long newFrom = newRange.from();
if (Long.compareUnsigned(existing.from(), newFrom) < 0) {
newFrom = existing.from();
}
long newTo = newRange.to();
if (Long.compareUnsigned(existing.to(), newTo) > 0) {
newTo = existing.to();
}
newRange = new Range(newFrom, newTo);
}
// No overlapping range exists: check for coalescing with the
// previous/next range
SerialRange prev = ranges.floorKey(newRange);
if (prev != null && newRange.from() - prev.to() == 1) {
ranges.remove(prev);
newRange = new Range(prev.from(), newRange.to());
}
SerialRange next = ranges.ceilingKey(newRange);
if (next != null && next.from() - newRange.to() == 1) {
ranges.remove(next);
newRange = new Range(newRange.from(), next.to());
}
ranges.put(newRange, newRange);
}
}
|
