truncindex_test.go 11 KB

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