1package truncindex // import "github.com/docker/docker/pkg/truncindex"
2
3import (
4	"math/rand"
5	"testing"
6	"time"
7
8	"github.com/docker/docker/pkg/stringid"
9)
10
11// Test the behavior of TruncIndex, an index for querying IDs from a non-conflicting prefix.
12func TestTruncIndex(t *testing.T) {
13	var ids []string
14	index := NewTruncIndex(ids)
15	// Get on an empty index
16	if _, err := index.Get("foobar"); err == nil {
17		t.Fatal("Get on an empty index should return an error")
18	}
19
20	// Spaces should be illegal in an id
21	if err := index.Add("I have a space"); err == nil {
22		t.Fatalf("Adding an id with ' ' should return an error")
23	}
24
25	id := "99b36c2c326ccc11e726eee6ee78a0baf166ef96"
26	// Add an id
27	if err := index.Add(id); err != nil {
28		t.Fatal(err)
29	}
30
31	// Add an empty id (should fail)
32	if err := index.Add(""); err == nil {
33		t.Fatalf("Adding an empty id should return an error")
34	}
35
36	// Get a non-existing id
37	assertIndexGet(t, index, "abracadabra", "", true)
38	// Get an empty id
39	assertIndexGet(t, index, "", "", true)
40	// Get the exact id
41	assertIndexGet(t, index, id, id, false)
42	// The first letter should match
43	assertIndexGet(t, index, id[:1], id, false)
44	// The first half should match
45	assertIndexGet(t, index, id[:len(id)/2], id, false)
46	// The second half should NOT match
47	assertIndexGet(t, index, id[len(id)/2:], "", true)
48
49	id2 := id[:6] + "blabla"
50	// Add an id
51	if err := index.Add(id2); err != nil {
52		t.Fatal(err)
53	}
54	// Both exact IDs should work
55	assertIndexGet(t, index, id, id, false)
56	assertIndexGet(t, index, id2, id2, false)
57
58	// 6 characters or less should conflict
59	assertIndexGet(t, index, id[:6], "", true)
60	assertIndexGet(t, index, id[:4], "", true)
61	assertIndexGet(t, index, id[:1], "", true)
62
63	// An ambiguous id prefix should return an error
64	if _, err := index.Get(id[:4]); err == nil {
65		t.Fatal("An ambiguous id prefix should return an error")
66	}
67
68	// 7 characters should NOT conflict
69	assertIndexGet(t, index, id[:7], id, false)
70	assertIndexGet(t, index, id2[:7], id2, false)
71
72	// Deleting a non-existing id should return an error
73	if err := index.Delete("non-existing"); err == nil {
74		t.Fatalf("Deleting a non-existing id should return an error")
75	}
76
77	// Deleting an empty id should return an error
78	if err := index.Delete(""); err == nil {
79		t.Fatal("Deleting an empty id should return an error")
80	}
81
82	// Deleting id2 should remove conflicts
83	if err := index.Delete(id2); err != nil {
84		t.Fatal(err)
85	}
86	// id2 should no longer work
87	assertIndexGet(t, index, id2, "", true)
88	assertIndexGet(t, index, id2[:7], "", true)
89	assertIndexGet(t, index, id2[:11], "", true)
90
91	// conflicts between id and id2 should be gone
92	assertIndexGet(t, index, id[:6], id, false)
93	assertIndexGet(t, index, id[:4], id, false)
94	assertIndexGet(t, index, id[:1], id, false)
95
96	// non-conflicting substrings should still not conflict
97	assertIndexGet(t, index, id[:7], id, false)
98	assertIndexGet(t, index, id[:15], id, false)
99	assertIndexGet(t, index, id, id, false)
100
101	assertIndexIterate(t)
102	assertIndexIterateDoNotPanic(t)
103}
104
105func assertIndexIterate(t *testing.T) {
106	ids := []string{
107		"19b36c2c326ccc11e726eee6ee78a0baf166ef96",
108		"28b36c2c326ccc11e726eee6ee78a0baf166ef96",
109		"37b36c2c326ccc11e726eee6ee78a0baf166ef96",
110		"46b36c2c326ccc11e726eee6ee78a0baf166ef96",
111	}
112
113	index := NewTruncIndex(ids)
114
115	index.Iterate(func(targetId string) {
116		for _, id := range ids {
117			if targetId == id {
118				return
119			}
120		}
121
122		t.Fatalf("An unknown ID '%s'", targetId)
123	})
124}
125
126func assertIndexIterateDoNotPanic(t *testing.T) {
127	ids := []string{
128		"19b36c2c326ccc11e726eee6ee78a0baf166ef96",
129		"28b36c2c326ccc11e726eee6ee78a0baf166ef96",
130	}
131
132	index := NewTruncIndex(ids)
133	iterationStarted := make(chan bool, 1)
134
135	go func() {
136		<-iterationStarted
137		index.Delete("19b36c2c326ccc11e726eee6ee78a0baf166ef96")
138	}()
139
140	index.Iterate(func(targetId string) {
141		if targetId == "19b36c2c326ccc11e726eee6ee78a0baf166ef96" {
142			iterationStarted <- true
143			time.Sleep(100 * time.Millisecond)
144		}
145	})
146}
147
148func assertIndexGet(t *testing.T, index *TruncIndex, input, expectedResult string, expectError bool) {
149	if result, err := index.Get(input); err != nil && !expectError {
150		t.Fatalf("Unexpected error getting '%s': %s", input, err)
151	} else if err == nil && expectError {
152		t.Fatalf("Getting '%s' should return an error, not '%s'", input, result)
153	} else if result != expectedResult {
154		t.Fatalf("Getting '%s' returned '%s' instead of '%s'", input, result, expectedResult)
155	}
156}
157
158func BenchmarkTruncIndexAdd100(b *testing.B) {
159	var testSet []string
160	for i := 0; i < 100; i++ {
161		testSet = append(testSet, stringid.GenerateNonCryptoID())
162	}
163	b.ResetTimer()
164	for i := 0; i < b.N; i++ {
165		index := NewTruncIndex([]string{})
166		for _, id := range testSet {
167			if err := index.Add(id); err != nil {
168				b.Fatal(err)
169			}
170		}
171	}
172}
173
174func BenchmarkTruncIndexAdd250(b *testing.B) {
175	var testSet []string
176	for i := 0; i < 250; i++ {
177		testSet = append(testSet, stringid.GenerateNonCryptoID())
178	}
179	b.ResetTimer()
180	for i := 0; i < b.N; i++ {
181		index := NewTruncIndex([]string{})
182		for _, id := range testSet {
183			if err := index.Add(id); err != nil {
184				b.Fatal(err)
185			}
186		}
187	}
188}
189
190func BenchmarkTruncIndexAdd500(b *testing.B) {
191	var testSet []string
192	for i := 0; i < 500; i++ {
193		testSet = append(testSet, stringid.GenerateNonCryptoID())
194	}
195	b.ResetTimer()
196	for i := 0; i < b.N; i++ {
197		index := NewTruncIndex([]string{})
198		for _, id := range testSet {
199			if err := index.Add(id); err != nil {
200				b.Fatal(err)
201			}
202		}
203	}
204}
205
206func BenchmarkTruncIndexGet100(b *testing.B) {
207	var testSet []string
208	var testKeys []string
209	for i := 0; i < 100; i++ {
210		testSet = append(testSet, stringid.GenerateNonCryptoID())
211	}
212	index := NewTruncIndex([]string{})
213	for _, id := range testSet {
214		if err := index.Add(id); err != nil {
215			b.Fatal(err)
216		}
217		l := rand.Intn(12) + 12
218		testKeys = append(testKeys, id[:l])
219	}
220	b.ResetTimer()
221	for i := 0; i < b.N; i++ {
222		for _, id := range testKeys {
223			if res, err := index.Get(id); err != nil {
224				b.Fatal(res, err)
225			}
226		}
227	}
228}
229
230func BenchmarkTruncIndexGet250(b *testing.B) {
231	var testSet []string
232	var testKeys []string
233	for i := 0; i < 250; i++ {
234		testSet = append(testSet, stringid.GenerateNonCryptoID())
235	}
236	index := NewTruncIndex([]string{})
237	for _, id := range testSet {
238		if err := index.Add(id); err != nil {
239			b.Fatal(err)
240		}
241		l := rand.Intn(12) + 12
242		testKeys = append(testKeys, id[:l])
243	}
244	b.ResetTimer()
245	for i := 0; i < b.N; i++ {
246		for _, id := range testKeys {
247			if res, err := index.Get(id); err != nil {
248				b.Fatal(res, err)
249			}
250		}
251	}
252}
253
254func BenchmarkTruncIndexGet500(b *testing.B) {
255	var testSet []string
256	var testKeys []string
257	for i := 0; i < 500; i++ {
258		testSet = append(testSet, stringid.GenerateNonCryptoID())
259	}
260	index := NewTruncIndex([]string{})
261	for _, id := range testSet {
262		if err := index.Add(id); err != nil {
263			b.Fatal(err)
264		}
265		l := rand.Intn(12) + 12
266		testKeys = append(testKeys, id[:l])
267	}
268	b.ResetTimer()
269	for i := 0; i < b.N; i++ {
270		for _, id := range testKeys {
271			if res, err := index.Get(id); err != nil {
272				b.Fatal(res, err)
273			}
274		}
275	}
276}
277
278func BenchmarkTruncIndexDelete100(b *testing.B) {
279	var testSet []string
280	for i := 0; i < 100; i++ {
281		testSet = append(testSet, stringid.GenerateNonCryptoID())
282	}
283	b.ResetTimer()
284	for i := 0; i < b.N; i++ {
285		b.StopTimer()
286		index := NewTruncIndex([]string{})
287		for _, id := range testSet {
288			if err := index.Add(id); err != nil {
289				b.Fatal(err)
290			}
291		}
292		b.StartTimer()
293		for _, id := range testSet {
294			if err := index.Delete(id); err != nil {
295				b.Fatal(err)
296			}
297		}
298	}
299}
300
301func BenchmarkTruncIndexDelete250(b *testing.B) {
302	var testSet []string
303	for i := 0; i < 250; i++ {
304		testSet = append(testSet, stringid.GenerateNonCryptoID())
305	}
306	b.ResetTimer()
307	for i := 0; i < b.N; i++ {
308		b.StopTimer()
309		index := NewTruncIndex([]string{})
310		for _, id := range testSet {
311			if err := index.Add(id); err != nil {
312				b.Fatal(err)
313			}
314		}
315		b.StartTimer()
316		for _, id := range testSet {
317			if err := index.Delete(id); err != nil {
318				b.Fatal(err)
319			}
320		}
321	}
322}
323
324func BenchmarkTruncIndexDelete500(b *testing.B) {
325	var testSet []string
326	for i := 0; i < 500; i++ {
327		testSet = append(testSet, stringid.GenerateNonCryptoID())
328	}
329	b.ResetTimer()
330	for i := 0; i < b.N; i++ {
331		b.StopTimer()
332		index := NewTruncIndex([]string{})
333		for _, id := range testSet {
334			if err := index.Add(id); err != nil {
335				b.Fatal(err)
336			}
337		}
338		b.StartTimer()
339		for _, id := range testSet {
340			if err := index.Delete(id); err != nil {
341				b.Fatal(err)
342			}
343		}
344	}
345}
346
347func BenchmarkTruncIndexNew100(b *testing.B) {
348	var testSet []string
349	for i := 0; i < 100; i++ {
350		testSet = append(testSet, stringid.GenerateNonCryptoID())
351	}
352	b.ResetTimer()
353	for i := 0; i < b.N; i++ {
354		NewTruncIndex(testSet)
355	}
356}
357
358func BenchmarkTruncIndexNew250(b *testing.B) {
359	var testSet []string
360	for i := 0; i < 250; i++ {
361		testSet = append(testSet, stringid.GenerateNonCryptoID())
362	}
363	b.ResetTimer()
364	for i := 0; i < b.N; i++ {
365		NewTruncIndex(testSet)
366	}
367}
368
369func BenchmarkTruncIndexNew500(b *testing.B) {
370	var testSet []string
371	for i := 0; i < 500; i++ {
372		testSet = append(testSet, stringid.GenerateNonCryptoID())
373	}
374	b.ResetTimer()
375	for i := 0; i < b.N; i++ {
376		NewTruncIndex(testSet)
377	}
378}
379
380func BenchmarkTruncIndexAddGet100(b *testing.B) {
381	var testSet []string
382	var testKeys []string
383	for i := 0; i < 500; i++ {
384		id := stringid.GenerateNonCryptoID()
385		testSet = append(testSet, id)
386		l := rand.Intn(12) + 12
387		testKeys = append(testKeys, id[:l])
388	}
389	b.ResetTimer()
390	for i := 0; i < b.N; i++ {
391		index := NewTruncIndex([]string{})
392		for _, id := range testSet {
393			if err := index.Add(id); err != nil {
394				b.Fatal(err)
395			}
396		}
397		for _, id := range testKeys {
398			if res, err := index.Get(id); err != nil {
399				b.Fatal(res, err)
400			}
401		}
402	}
403}
404
405func BenchmarkTruncIndexAddGet250(b *testing.B) {
406	var testSet []string
407	var testKeys []string
408	for i := 0; i < 500; i++ {
409		id := stringid.GenerateNonCryptoID()
410		testSet = append(testSet, id)
411		l := rand.Intn(12) + 12
412		testKeys = append(testKeys, id[:l])
413	}
414	b.ResetTimer()
415	for i := 0; i < b.N; i++ {
416		index := NewTruncIndex([]string{})
417		for _, id := range testSet {
418			if err := index.Add(id); err != nil {
419				b.Fatal(err)
420			}
421		}
422		for _, id := range testKeys {
423			if res, err := index.Get(id); err != nil {
424				b.Fatal(res, err)
425			}
426		}
427	}
428}
429
430func BenchmarkTruncIndexAddGet500(b *testing.B) {
431	var testSet []string
432	var testKeys []string
433	for i := 0; i < 500; i++ {
434		id := stringid.GenerateNonCryptoID()
435		testSet = append(testSet, id)
436		l := rand.Intn(12) + 12
437		testKeys = append(testKeys, id[:l])
438	}
439	b.ResetTimer()
440	for i := 0; i < b.N; i++ {
441		index := NewTruncIndex([]string{})
442		for _, id := range testSet {
443			if err := index.Add(id); err != nil {
444				b.Fatal(err)
445			}
446		}
447		for _, id := range testKeys {
448			if res, err := index.Get(id); err != nil {
449				b.Fatal(res, err)
450			}
451		}
452	}
453}
454