diff options
Diffstat (limited to 'vendor/github.com/mattermost/rsc/regexp/regmerge/sparse.go')
-rw-r--r-- | vendor/github.com/mattermost/rsc/regexp/regmerge/sparse.go | 80 |
1 files changed, 80 insertions, 0 deletions
diff --git a/vendor/github.com/mattermost/rsc/regexp/regmerge/sparse.go b/vendor/github.com/mattermost/rsc/regexp/regmerge/sparse.go new file mode 100644 index 000000000..461027080 --- /dev/null +++ b/vendor/github.com/mattermost/rsc/regexp/regmerge/sparse.go @@ -0,0 +1,80 @@ +// Copyright 2011 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Copied from code.google.com/p/codesearch/sparse/set.go, +// tweaked for better inlinability. + +package main + +// For comparison: running cindex over the Linux 2.6 kernel with this +// implementation of trigram sets takes 11 seconds. If I change it to +// a bitmap (which must be cleared between files) it takes 25 seconds. + +// A Set is a sparse set of uint32 values. +// http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html +type Set struct { + dense []uint32 + sparse []uint32 +} + +// NewSet returns a new Set with a given maximum size. +// The set can contain numbers in [0, max-1]. +func NewSet(max uint32) *Set { + return &Set{ + sparse: make([]uint32, max), + } +} + +// Init initializes a Set to have a given maximum size. +// The set can contain numbers in [0, max-1]. +func (s *Set) Init(max uint32) { + s.sparse = make([]uint32, max) +} + +// Reset clears (empties) the set. +func (s *Set) Reset() { + s.dense = s.dense[:0] +} + +// Add adds x to the set if it is not already there. +// +// TODO: The ugly additional variables v and n make the +// function inlinable. When the 6g inliner gets better +// they will not be necessary. +func (s *Set) Add(x uint32, v uint32, n int) { + v = s.sparse[x] + if v < uint32(len(s.dense)) && s.dense[v] == x { + return + } + n = len(s.dense) + s.sparse[x] = uint32(n) + s.dense = append(s.dense, x) +} + +func (s *Set) MustAdd(x uint32) { + s.sparse[x] = uint32(len(s.dense)) + s.dense = append(s.dense, x) +} + +// Has reports whether x is in the set. +// +// TODO: The ugly additional variables v makes +// function inlinable. When the 6g inliner gets better +// it will not be necessary. +func (s *Set) Has(x uint32, v uint32) bool { + v = s.sparse[x] + return v < uint32(len(s.dense)) && s.dense[v] == x +} + +// Dense returns the values in the set. +// The values are listed in the order in which they +// were inserted. +func (s *Set) Dense() []uint32 { + return s.dense +} + +// Len returns the number of values in the set. +func (s *Set) Len() int { + return len(s.dense) +} |