1// Copyright (c) 2017 Couchbase, Inc. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package regexp 16 17type sparseSet struct { 18 dense []uint 19 sparse []uint 20 size uint 21} 22 23func newSparseSet(size uint) *sparseSet { 24 return &sparseSet{ 25 dense: make([]uint, size), 26 sparse: make([]uint, size), 27 size: 0, 28 } 29} 30 31func (s *sparseSet) Len() int { 32 return int(s.size) 33} 34 35func (s *sparseSet) Add(ip uint) uint { 36 i := s.size 37 s.dense[i] = ip 38 s.sparse[ip] = i 39 s.size++ 40 return i 41} 42 43func (s *sparseSet) Get(i uint) uint { 44 return s.dense[i] 45} 46 47func (s *sparseSet) Contains(ip uint) bool { 48 i := s.sparse[ip] 49 return i < s.size && s.dense[i] == ip 50} 51 52func (s *sparseSet) Clear() { 53 s.size = 0 54} 55