1dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch/* 2dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * Copyright (C) 2010 Apple Inc. All rights reserved. 3dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * 4dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * This library is free software; you can redistribute it and/or 5dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * modify it under the terms of the GNU Lesser General Public 6dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * License as published by the Free Software Foundation; either 7dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * version 2 of the License, or (at your option) any later version. 8dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * 9dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * This library is distributed in the hope that it will be useful, 10dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * but WITHOUT ANY WARRANTY; without even the implied warranty of 11dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * Lesser General Public License for more details. 13dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * 14dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * You should have received a copy of the GNU Lesser General Public 15dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * License along with this library; if not, write to the Free Software 16dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 17dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch * 18dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch */ 19dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch#ifndef Bitmap_h 20dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch#define Bitmap_h 21dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 22dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch#include "FixedArray.h" 23dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch#include "StdLibExtras.h" 24dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch#include <stdint.h> 252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include <string.h> 26dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 27dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochnamespace WTF { 28dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 29dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochtemplate<size_t size> 30dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochclass Bitmap { 31dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochprivate: 32dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch typedef uint32_t WordType; 33dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 34dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochpublic: 35dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch Bitmap(); 36dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 37dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch bool get(size_t) const; 38dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch void set(size_t); 392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool testAndSet(size_t); 402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block size_t nextPossiblyUnset(size_t) const; 41dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch void clear(size_t); 42dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch void clearAll(); 4381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch int64_t findRunOfZeros(size_t) const; 44dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch size_t count(size_t = 0) const; 45dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch size_t isEmpty() const; 46dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch size_t isFull() const; 47dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 48dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochprivate: 49dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch static const WordType wordSize = sizeof(WordType) * 8; 50dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch static const WordType words = (size + wordSize - 1) / wordSize; 51dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 52dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch // the literal '1' is of type signed int. We want to use an unsigned 53dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch // version of the correct size when doing the calculations because if 54dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch // WordType is larger than int, '1 << 31' will first be sign extended 55dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch // and then casted to unsigned, meaning that set(31) when WordType is 56dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch // a 64 bit unsigned int would give 0xffff8000 57dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch static const WordType one = 1; 58dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 59dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch FixedArray<WordType, words> bits; 60dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch}; 61dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 62dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochtemplate<size_t size> 63dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochinline Bitmap<size>::Bitmap() 64dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch{ 65dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch clearAll(); 66dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch} 67dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 68dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochtemplate<size_t size> 69dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochinline bool Bitmap<size>::get(size_t n) const 70dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch{ 71dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch return !!(bits[n / wordSize] & (one << (n % wordSize))); 72dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch} 73dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 74dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochtemplate<size_t size> 75dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochinline void Bitmap<size>::set(size_t n) 76dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch{ 77dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch bits[n / wordSize] |= (one << (n % wordSize)); 78dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch} 79dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 80dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochtemplate<size_t size> 812fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockinline bool Bitmap<size>::testAndSet(size_t n) 822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block WordType mask = one << (n % wordSize); 842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block size_t index = n / wordSize; 852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool result = bits[index] & mask; 862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bits[index] |= mask; 872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return result; 882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 892fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 902fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocktemplate<size_t size> 91dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochinline void Bitmap<size>::clear(size_t n) 92dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch{ 93dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch bits[n / wordSize] &= ~(one << (n % wordSize)); 94dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch} 95dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 96dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochtemplate<size_t size> 97dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochinline void Bitmap<size>::clearAll() 98dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch{ 99dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch memset(bits.data(), 0, sizeof(bits)); 100dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch} 101dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 102dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochtemplate<size_t size> 1032fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockinline size_t Bitmap<size>::nextPossiblyUnset(size_t start) const 104dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch{ 105dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch if (!~bits[start / wordSize]) 1062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return ((start / wordSize) + 1) * wordSize; 1072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return start + 1; 108dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch} 109dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 110dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochtemplate<size_t size> 11181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochinline int64_t Bitmap<size>::findRunOfZeros(size_t runLength) const 11281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch{ 11381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch if (!runLength) 11481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch runLength = 1; 11581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 11681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch for (size_t i = 0; i <= (size - runLength) ; i++) { 11781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch bool found = true; 11881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch for (size_t j = i; j <= (i + runLength - 1) ; j++) { 11981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch if (get(j)) { 12081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch found = false; 12181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch break; 12281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 12381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 12481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch if (found) 12581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return i; 12681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 12781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return -1; 12881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch} 12981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 13081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochtemplate<size_t size> 131dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochinline size_t Bitmap<size>::count(size_t start) const 132dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch{ 133dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch size_t result = 0; 134dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch for ( ; (start % wordSize); ++start) { 135dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch if (get(start)) 136dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch ++result; 137dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch } 138dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch for (size_t i = start / wordSize; i < words; ++i) 139dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch result += WTF::bitCount(bits[i]); 140dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch return result; 141dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch} 142dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 143dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochtemplate<size_t size> 144dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochinline size_t Bitmap<size>::isEmpty() const 145dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch{ 146dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch for (size_t i = 0; i < words; ++i) 147dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch if (bits[i]) 148dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch return false; 149dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch return true; 150dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch} 151dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 152dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochtemplate<size_t size> 153dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdochinline size_t Bitmap<size>::isFull() const 154dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch{ 155dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch for (size_t i = 0; i < words; ++i) 156dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch if (~bits[i]) 157dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch return false; 158dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch return true; 159dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch} 160dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch 161dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch} 162dd8bb3de4f353a81954234999f1fea748aee2ea9Ben Murdoch#endif 163