13a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/************************************************************************** 23a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 33a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Copyright 2009 VMware, Inc. 43a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * All Rights Reserved. 53a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 63a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Permission is hereby granted, free of charge, to any person obtaining a 73a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * copy of this software and associated documentation files (the 83a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * "Software"), to deal in the Software without restriction, including 93a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * without limitation the rights to use, copy, modify, merge, publish, 103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * distribute, sub license, and/or sell copies of the Software, and to 113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * permit persons to whom the Software is furnished to do so, subject to 123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * the following conditions: 133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * The above copyright notice and this permission notice (including the 153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * next paragraph) shall be included in all copies or substantial portions 163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * of the Software. 173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. 213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR 223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org **************************************************************************/ 273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * @file 303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Generic bitmask implementation. 313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * @author Jose Fonseca <jfonseca@vmware.com> 333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#include "pipe/p_compiler.h" 373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#include "util/u_debug.h" 383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#include "util/u_memory.h" 403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#include "util/u_bitmask.h" 413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgtypedef uint32_t util_bitmask_word; 443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define UTIL_BITMASK_INITIAL_WORDS 16 473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define UTIL_BITMASK_BITS_PER_BYTE 8 483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define UTIL_BITMASK_BITS_PER_WORD (sizeof(util_bitmask_word) * UTIL_BITMASK_BITS_PER_BYTE) 493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct util_bitmask 523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org util_bitmask_word *words; 543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org /** Number of bits we can currently hold */ 563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned size; 573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org /** Number of consecutive bits set at the start of the bitmask */ 593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned filled; 603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org}; 613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct util_bitmask * 643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgutil_bitmask_create(void) 653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct util_bitmask *bm; 673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bm = MALLOC_STRUCT(util_bitmask); 693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(!bm) 703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return NULL; 713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bm->words = (util_bitmask_word *)CALLOC(UTIL_BITMASK_INITIAL_WORDS, sizeof(util_bitmask_word)); 733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(!bm->words) { 743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org FREE(bm); 753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return NULL; 763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bm->size = UTIL_BITMASK_INITIAL_WORDS * UTIL_BITMASK_BITS_PER_WORD; 793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bm->filled = 0; 803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return bm; 823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 853a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Resize the bitmask if necessary 873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic INLINE boolean 893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgutil_bitmask_resize(struct util_bitmask *bm, 903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned minimum_index) 913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned minimum_size = minimum_index + 1; 933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned new_size; 943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org util_bitmask_word *new_words; 953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org /* Check integer overflow */ 973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(!minimum_size) 983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return FALSE; 993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 100760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org if(bm->size >= minimum_size) 1013a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return TRUE; 1023a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1033a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(bm->size % UTIL_BITMASK_BITS_PER_WORD == 0); 1043a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org new_size = bm->size; 105760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org while(new_size < minimum_size) { 1063a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org new_size *= 2; 1073a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org /* Check integer overflow */ 1083a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(new_size < bm->size) 1093a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return FALSE; 1103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 1113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(new_size); 1123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(new_size % UTIL_BITMASK_BITS_PER_WORD == 0); 1133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org new_words = (util_bitmask_word *)REALLOC((void *)bm->words, 1153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bm->size / UTIL_BITMASK_BITS_PER_BYTE, 1163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org new_size / UTIL_BITMASK_BITS_PER_BYTE); 1173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(!new_words) 1183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return FALSE; 1193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org memset(new_words + bm->size/UTIL_BITMASK_BITS_PER_WORD, 1213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 0, 1223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (new_size - bm->size)/UTIL_BITMASK_BITS_PER_BYTE); 1233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bm->size = new_size; 1253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bm->words = new_words; 1263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return TRUE; 1283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 1323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Lazily update the filled. 1333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 1343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic INLINE void 1353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgutil_bitmask_filled_set(struct util_bitmask *bm, 1363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned index) 1373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(bm->filled <= bm->size); 139760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org assert(index < bm->size); 1403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(index == bm->filled) { 1423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++bm->filled; 1433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(bm->filled <= bm->size); 1443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 1453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic INLINE void 1483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgutil_bitmask_filled_unset(struct util_bitmask *bm, 1493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned index) 1503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(bm->filled <= bm->size); 152760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org assert(index < bm->size); 1533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(index < bm->filled) 1553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bm->filled = index; 1563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgunsigned 1603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgutil_bitmask_add(struct util_bitmask *bm) 1613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned word; 1633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned bit; 1643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org util_bitmask_word mask; 1653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(bm); 1673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org /* linear search for an empty index */ 1693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org word = bm->filled / UTIL_BITMASK_BITS_PER_WORD; 1703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bit = bm->filled % UTIL_BITMASK_BITS_PER_WORD; 1713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org mask = 1 << bit; 1723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while(word < bm->size / UTIL_BITMASK_BITS_PER_WORD) { 1733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while(bit < UTIL_BITMASK_BITS_PER_WORD) { 1743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(!(bm->words[word] & mask)) 1753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org goto found; 1763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++bm->filled; 1773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++bit; 1783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org mask <<= 1; 1793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 1803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++word; 1813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bit = 0; 1823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org mask = 1; 1833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 1843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgfound: 185760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 1863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org /* grow the bitmask if necessary */ 1873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(!util_bitmask_resize(bm, bm->filled)) 1883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return UTIL_BITMASK_INVALID_INDEX; 1893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(!(bm->words[word] & mask)); 1913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bm->words[word] |= mask; 1923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return bm->filled++; 1943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgunsigned 1983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgutil_bitmask_set(struct util_bitmask *bm, 1993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned index) 2003a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 201760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org unsigned word; 202760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org unsigned bit; 203760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org util_bitmask_word mask; 2043a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2053a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(bm); 2063a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2073a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org /* grow the bitmask if necessary */ 2083a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(!util_bitmask_resize(bm, index)) 2093a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return UTIL_BITMASK_INVALID_INDEX; 2103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 211760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org word = index / UTIL_BITMASK_BITS_PER_WORD; 212760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org bit = index % UTIL_BITMASK_BITS_PER_WORD; 213760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org mask = 1 << bit; 214760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 2153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bm->words[word] |= mask; 2163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org util_bitmask_filled_set(bm, index); 2183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return index; 2203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgvoid 2243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgutil_bitmask_clear(struct util_bitmask *bm, 2253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned index) 2263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 227760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org unsigned word; 228760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org unsigned bit; 229760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org util_bitmask_word mask; 2303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(bm); 2323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(index >= bm->size) 2343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return; 2353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 236760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org word = index / UTIL_BITMASK_BITS_PER_WORD; 237760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org bit = index % UTIL_BITMASK_BITS_PER_WORD; 238760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org mask = 1 << bit; 239760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org 2403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bm->words[word] &= ~mask; 2413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org util_bitmask_filled_unset(bm, index); 2433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgboolean 2473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgutil_bitmask_get(struct util_bitmask *bm, 2483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned index) 2493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned word = index / UTIL_BITMASK_BITS_PER_WORD; 2513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned bit = index % UTIL_BITMASK_BITS_PER_WORD; 2523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org util_bitmask_word mask = 1 << bit; 2533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(bm); 2553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(index < bm->filled) { 2573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(bm->words[word] & mask); 2583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return TRUE; 2593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 261760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org if(index >= bm->size) 2623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return FALSE; 2633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(bm->words[word] & mask) { 2653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org util_bitmask_filled_set(bm, index); 2663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return TRUE; 2673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org else 2693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return FALSE; 2703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgunsigned 2743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgutil_bitmask_get_next_index(struct util_bitmask *bm, 2753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned index) 2763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned word = index / UTIL_BITMASK_BITS_PER_WORD; 2783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned bit = index % UTIL_BITMASK_BITS_PER_WORD; 2793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org util_bitmask_word mask = 1 << bit; 2803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(index < bm->filled) { 2823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(bm->words[word] & mask); 2833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return index; 2843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2853a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(index >= bm->size) { 2873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return UTIL_BITMASK_INVALID_INDEX; 2883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org /* Do a linear search */ 2913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while(word < bm->size / UTIL_BITMASK_BITS_PER_WORD) { 2923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while(bit < UTIL_BITMASK_BITS_PER_WORD) { 2933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(bm->words[word] & mask) { 2943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if(index == bm->filled) { 2953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++bm->filled; 2963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(bm->filled <= bm->size); 2973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return index; 2993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 3003a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++index; 3013a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++bit; 3023a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org mask <<= 1; 3033a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 3043a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++word; 3053a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bit = 0; 3063a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org mask = 1; 3073a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 3083a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3093a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return UTIL_BITMASK_INVALID_INDEX; 3103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgunsigned 3143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgutil_bitmask_get_first_index(struct util_bitmask *bm) 3153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 3163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return util_bitmask_get_next_index(bm, 0); 3173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgvoid 3213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgutil_bitmask_destroy(struct util_bitmask *bm) 3223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 3233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(bm); 3243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org FREE(bm->words); 3263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org FREE(bm); 3273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 329