Mercurial > repos > tabletprog

comparison modules/sets.tp @ 81:a905e13db753

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
author Mike Pavone <pavone@retrodev.com>
date Wed, 18 Jul 2012 08:59:08 -0700
parents cbc92ee13f35
children a2d2d8e09291
comparison
equal deleted inserted replaced
80:cbc92ee13f35 81:a905e13db753
1 #{ 1 #{
2 hash <- { 2 hash <- {
3 empty <- #{ 3 empty <- #{
4 empty? <- { true } 4 empty? <- { true }
5 } 5 }
6 size <- 0
7 hashdiffs <- #[0]
6 #{ 8 #{
7 buckets <- #[empty empty empty empty] 9 buckets <- #[empty empty empty empty]
8 contains? <- :object { 10 contains? <- :object {
9 hv <- object hash 11 hv <- object hash
10 12
11 notdone <- true 13 notdone <- true
12 hashes <- #[hv (hv + 1) (hv - 1)] 14
15 basehash <- hv
13 i <- 0 16 i <- 0
14 ret <- false 17 ret <- false
15 while: { if: notdone { i < 3 } } do: { 18 while: { if: notdone { i < (hashdiffs length) } } do: {
16 hv <- hashes get: i 19 hv <- basehash + (hashdiffs get: i)
17 trunc <- hv % (buckets length) 20 trunc <- hv % (buckets length)
18 if: trunc < 0 { trunc <- 0 - trunc } 21 if: trunc < 0 { trunc <- 0 - trunc }
19 bucketval <- (buckets get: trunc) 22 bucketval <- (buckets get: trunc)
20 if: (bucketval empty?) { 23 if: (bucketval empty?) {
21 notdone <- false 24 notdone <- false
39 v <- hv 42 v <- hv
40 eq <- :other { v = other } 43 eq <- :other { v = other }
41 } 44 }
42 } 45 }
43 notdone <- true 46 notdone <- true
44 hashes <- #[hv (hv + 1) (hv - 1)] 47 basehash <- hv
45 i <- 0 48 i <- 0
46 while: { if: notdone { i < 3 } } do: { 49 while: { if: notdone { i < (hashdiffs length) } } do: {
47 hv <- hashes get: i 50 hv <- basehash + (hashdiffs get: i)
48 trunc <- hv % (buckets length) 51 trunc <- hv % (buckets length)
49 if: trunc < 0 { trunc <- 0 - trunc } 52 if: trunc < 0 { trunc <- 0 - trunc }
50 bucketval <- (buckets get: trunc) 53 bucketval <- (buckets get: trunc)
51 if: (bucketval empty?) { 54 if: (bucketval empty?) {
55 size <- size + 1
52 buckets set: trunc (makeBucket: hv) 56 buckets set: trunc (makeBucket: hv)
53 notdone <- false 57 notdone <- false
54 } else: { 58 } else: {
55 if: (bucketval eq: hv) { 59 if: (bucketval eq: hv) {
56 notdone <- false 60 notdone <- false
57 } 61 }
58 } 62 }
59 i <- i + 1 63 i <- i + 1
60 } 64 }
61 if: notdone { 65 if: notdone {
62 newsize <- (buckets length) * 3 66 newsize <- (buckets length) * 3 + 1
67 lastdiff <- hashdiffs get: ((hashdiffs length) - 1)
68 if: lastdiff <= 0 {
69 hashdiffs append: ((0 - lastdiff) + 1)
70 } else: {
71 hashdiffs append: (0 - lastdiff)
72 }
63 newbucks <- #[] 73 newbucks <- #[]
64 while: { (newbucks length) < newsize } do: { 74 while: { (newbucks length) < newsize } do: {
65 newbucks append: empty 75 newbucks append: empty
66 } 76 }
67 oldbucks <- buckets 77 oldbucks <- buckets