1 /* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include <stdint.h> 18 #include <string.h> 19 #include <atomicBitset.h> 20 #include <atomic.h> 21 22 23 24 void atomicBitsetInit(struct AtomicBitset *set, uint32_t numBits) 25 { 26 set->numBits = numBits; 27 memset(set->words, 0, (numBits + 31) / 8); 28 if (numBits & 31) //mark all high bits so that atomicBitsetFindClearAndSet() is simpler 29 set->words[numBits / 32] = ((uint32_t)((int32_t)-1LL)) << (numBits & 31); 30 } 31 32 uint32_t atomicBitsetGetNumBits(const struct AtomicBitset *set) 33 { 34 return set->numBits; 35 } 36 37 bool atomicBitsetGetBit(const struct AtomicBitset *set, uint32_t num) 38 { 39 if (num >= set->numBits) /* any value is as good as the next */ 40 return false; 41 42 return !!((set->words[num / 32]) & (1UL << (num & 31))); 43 } 44 45 void atomicBitsetClearBit(struct AtomicBitset *set, uint32_t num) 46 { 47 uint32_t idx = num / 32, mask = 1UL << (num & 31); 48 uint32_t *wordPtr = set->words + idx; 49 uint32_t old, new; 50 51 if (num >= set->numBits) 52 return; 53 54 55 do { 56 old = *wordPtr; 57 new = old &~ mask; 58 } while (!atomicCmpXchg32bits(wordPtr, old, new)); 59 } 60 61 int32_t atomicBitsetFindClearAndSet(struct AtomicBitset *set) 62 { 63 uint32_t pos, i, numWords = (set->numBits + 31) / 32; 64 uint32_t *wordPtr = set->words; 65 66 for (i = 0; i < numWords; i++, wordPtr++) { 67 uint32_t old, new; 68 69 while (1) { 70 old = *wordPtr; 71 if (!(old + 1)) /* no work for words with no clear bits */ 72 break; 73 74 pos = __builtin_ctz(~old); /* This will allocate in diff order than ARM. Since we never made any promises on order of bits returned, this is ok */ 75 new = old | (1 << pos); 76 77 if (atomicCmpXchg32bits(wordPtr, old, new)) 78 return 32 * i + pos; 79 } 80 } 81 82 return false; 83 } 84 85 86 87 88 89 90 91 92 93 94
