| /* |
| * |
| * Embedded Linux library |
| * |
| * Copyright (C) 2015 Intel Corporation. All rights reserved. |
| * |
| * This library is free software; you can redistribute it and/or |
| * modify it under the terms of the GNU Lesser General Public |
| * License as published by the Free Software Foundation; either |
| * version 2.1 of the License, or (at your option) any later version. |
| * |
| * This library is distributed in the hope that it will be useful, |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| * Lesser General Public License for more details. |
| * |
| * You should have received a copy of the GNU Lesser General Public |
| * License along with this library; if not, write to the Free Software |
| * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA |
| * |
| */ |
| |
| #ifdef HAVE_CONFIG_H |
| #include <config.h> |
| #endif |
| |
| #define _GNU_SOURCE |
| #include <limits.h> |
| |
| #include "uintset.h" |
| #include "private.h" |
| |
| #define BITS_PER_LONG (sizeof(unsigned long) * 8) |
| |
| static inline int __ffz(unsigned long word) |
| { |
| return __builtin_ctzl(~word); |
| } |
| |
| static inline int __fls(unsigned long word) |
| { |
| return word ? sizeof(word) * 8 - __builtin_clzl(word) : 0; |
| } |
| |
| static inline int __ffs(unsigned long word) |
| { |
| return __builtin_ctzl(word); |
| } |
| |
| static unsigned long find_first_zero_bit(const unsigned long *addr, |
| unsigned long size) |
| { |
| unsigned long result = 0; |
| unsigned long tmp; |
| |
| while (size >= BITS_PER_LONG) { |
| tmp = *addr; |
| addr += 1; |
| |
| /* Any zero bits? */ |
| if (~tmp) |
| goto found; |
| |
| result += BITS_PER_LONG; |
| size -= BITS_PER_LONG; |
| } |
| |
| if (!size) |
| return result; |
| |
| /* |
| * If we are here, then we have a partial last word. Unused bits |
| * are always zero, so no ffz sanity checking is needed |
| */ |
| tmp = *addr; |
| |
| found: |
| return result + __ffz(tmp); |
| } |
| |
| static unsigned long find_first_bit(const unsigned long *addr, |
| unsigned long size) |
| { |
| unsigned long result = 0; |
| unsigned long tmp; |
| |
| while (size >= BITS_PER_LONG) { |
| tmp = *addr; |
| addr += 1; |
| |
| if (tmp) |
| goto found; |
| |
| result += BITS_PER_LONG; |
| size -= BITS_PER_LONG; |
| } |
| |
| if (!size) |
| return result; |
| |
| tmp = *addr; |
| if (!tmp) |
| return result + size; |
| |
| found: |
| return result + __ffs(tmp); |
| } |
| |
| static unsigned long find_last_bit(const unsigned long *addr, unsigned int size) |
| { |
| unsigned long words; |
| unsigned long tmp; |
| long i; |
| |
| /* Bits out of bounds are always zero, start at last word */ |
| words = (size + BITS_PER_LONG - 1) / BITS_PER_LONG; |
| |
| for (i = words - 1; i >= 0; i -= 1) { |
| tmp = addr[i]; |
| |
| if (!tmp) |
| continue; |
| |
| return i * BITS_PER_LONG + __fls(tmp) - 1; |
| } |
| |
| /* Not found */ |
| return size; |
| } |
| |
| struct l_uintset { |
| unsigned long *bits; |
| uint16_t size; |
| uint32_t min; |
| uint32_t max; |
| }; |
| |
| /** |
| * l_uintset_new_from_range: |
| * @min: The minimum value of the set of numbers contained in the set |
| * @max: The maximum value of the set of numbers contained |
| * |
| * Creates a new empty collection of unsigned integers. The size of the set |
| * is limited to roughly 2^16 entries. @min and @max give the minimum and |
| * maximum elements of the set. |
| * |
| * Returns: A newly allocated l_uintset object, and NULL otherwise. |
| **/ |
| LIB_EXPORT struct l_uintset *l_uintset_new_from_range(uint32_t min, |
| uint32_t max) |
| { |
| struct l_uintset *ret; |
| unsigned int size = max - min + 1; |
| |
| if (size > USHRT_MAX) |
| return NULL; |
| |
| ret = l_new(struct l_uintset, 1); |
| ret->bits = l_new(unsigned long, |
| (size + BITS_PER_LONG - 1) / BITS_PER_LONG); |
| ret->size = size; |
| ret->min = min; |
| ret->max = max; |
| |
| return ret; |
| } |
| |
| /** |
| * l_uintset_new: |
| * @size: The maximum size of the set |
| * |
| * Creates a new empty collection of unsigned integers. The size of the set |
| * is limited to roughly 2^16 entries. The set is created with minimum value |
| * of 1 and maximum value equal to size. |
| * |
| * Returns: A newly allocated l_uintset object, and NULL otherwise. |
| **/ |
| LIB_EXPORT struct l_uintset *l_uintset_new(unsigned int size) |
| { |
| return l_uintset_new_from_range(1, size); |
| } |
| |
| /** |
| * l_uintset_free: |
| * @set: The set to destroy |
| * |
| * De-allocated the set object. |
| **/ |
| LIB_EXPORT void l_uintset_free(struct l_uintset *set) |
| { |
| if (unlikely(!set)) |
| return; |
| |
| l_free(set->bits); |
| l_free(set); |
| } |
| |
| /** |
| * l_uintset_take: |
| * @set: The set of numbers |
| * @number: The number to remove from the set |
| * |
| * Removes the @number from the @set. No checking is performed whether the |
| * number is actually contained in the set. However, basic bounds checking |
| * is performed to make sure the number taken can actually exist in the set. |
| * |
| * Returns: true if the number was removed, and false otherwise. |
| **/ |
| LIB_EXPORT bool l_uintset_take(struct l_uintset *set, uint32_t number) |
| { |
| uint32_t offset = (number - set->min) / BITS_PER_LONG; |
| |
| if (unlikely(!set)) |
| return false; |
| |
| number -= set->min; |
| |
| if (number > set->size) |
| return false; |
| |
| number %= BITS_PER_LONG; |
| |
| set->bits[offset] &= ~(1UL << number); |
| |
| return true; |
| } |
| |
| /** |
| * l_uintset_put: |
| * @set: The set of numbers |
| * @number: The number to add to the set |
| * |
| * Adds the @number to the @set. No checking is performed whether the |
| * number is already contained in the set. However, basic bounds checking |
| * is performed to make sure the number being added can actually exist in |
| * the set. |
| * |
| * Returns: true if the number was added, and false otherwise. |
| **/ |
| LIB_EXPORT bool l_uintset_put(struct l_uintset *set, uint32_t number) |
| { |
| uint32_t bit = number - set->min; |
| uint32_t offset; |
| |
| if (unlikely(!set)) |
| return false; |
| |
| if (bit >= set->size) |
| return false; |
| |
| offset = bit / BITS_PER_LONG; |
| set->bits[offset] |= 1UL << (bit % BITS_PER_LONG); |
| |
| return true; |
| } |
| |
| /** |
| * l_uintset_contains: |
| * @set: The set of numbers |
| * @number: The number to search for |
| * |
| * Returns: true if the number is in the set, and false otherwise. |
| **/ |
| LIB_EXPORT bool l_uintset_contains(struct l_uintset *set, uint32_t number) |
| { |
| uint32_t bit = number - set->min; |
| uint32_t offset; |
| |
| if (unlikely(!set)) |
| return false; |
| |
| if (bit >= set->size) |
| return false; |
| |
| offset = bit / BITS_PER_LONG; |
| if (set->bits[offset] & (1UL << (bit % BITS_PER_LONG))) |
| return true; |
| |
| return false; |
| } |
| |
| /** |
| * l_uintset_get_min: |
| * @set: The set of numbers |
| * |
| * Returns: the minimum possible value of the set. If @set is NULL returns |
| * UINT_MAX. |
| **/ |
| LIB_EXPORT uint32_t l_uintset_get_min(struct l_uintset *set) |
| { |
| if (unlikely(!set)) |
| return UINT_MAX; |
| |
| return set->min; |
| } |
| |
| /** |
| * l_uintset_get_max: |
| * @set: The set of numbers |
| * |
| * Returns: the maximum possible value of the set. If @set is NULL returns |
| * UINT_MAX. |
| **/ |
| LIB_EXPORT uint32_t l_uintset_get_max(struct l_uintset *set) |
| { |
| if (unlikely(!set)) |
| return UINT_MAX; |
| |
| return set->max; |
| } |
| |
| /** |
| * l_uintset_find_unused_min: |
| * @set: The set of numbers |
| * |
| * Returns: The minimum number that is not preset in the set. If the set of |
| * numbers is fully populated, returns l_uintset_get_max(set) + 1. If @set is |
| * NULL returns UINT_MAX. |
| **/ |
| LIB_EXPORT uint32_t l_uintset_find_unused_min(struct l_uintset *set) |
| { |
| unsigned int bit; |
| |
| if (unlikely(!set)) |
| return UINT_MAX; |
| |
| bit = find_first_zero_bit(set->bits, set->size); |
| |
| if (bit >= set->size) |
| return set->max + 1; |
| |
| return bit + set->min; |
| } |
| |
| /** |
| * l_uintset_find_max: |
| * @set: The set of numbers |
| * |
| * Returns: The maximum number preset in the set. If the set of numbers is |
| * empty returns l_uintset_get_max(set) + 1. If @set is NULL returns UINT_MAX. |
| **/ |
| LIB_EXPORT uint32_t l_uintset_find_max(struct l_uintset *set) |
| { |
| unsigned int bit; |
| |
| if (unlikely(!set)) |
| return UINT_MAX; |
| |
| bit = find_last_bit(set->bits, set->size); |
| |
| if (bit >= set->size) |
| return set->max + 1; |
| |
| return bit + set->min; |
| } |
| |
| /** |
| * l_uintset_find_min: |
| * @set: The set of numbers |
| * |
| * Returns: The minimum number preset in the set. If the set of numbers is |
| * empty returns l_uintset_get_max(set) + 1. If @set is NULL returns UINT_MAX. |
| **/ |
| LIB_EXPORT uint32_t l_uintset_find_min(struct l_uintset *set) |
| { |
| unsigned int bit; |
| |
| if (unlikely(!set)) |
| return UINT_MAX; |
| |
| bit = find_first_bit(set->bits, set->size); |
| |
| if (bit >= set->size) |
| return set->max + 1; |
| |
| return bit + set->min; |
| } |