src/idmap.c

   1 /*
   2  *
   3  *  oFono - Open Source Telephony
   4  *
   5  *  Copyright (C) 2008-2011  Intel Corporation. All rights reserved.
   6  *  Copyright (C) 2004  Red Hat, Inc. All Rights Reserved.
   7  *
   8  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License version 2 as
  10  *  published by the Free Software Foundation.
  11  *
  12  *  This program is distributed in the hope that it will be useful,
  13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  *  GNU General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU General Public License
  18  *  along with this program; if not, write to the Free Software
  19  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20  *
  21  */
  22
  23 #ifdef HAVE_CONFIG_H
  24 #include <config.h>
  25 #endif
  26
  27 #define _GNU_SOURCE
  28 #include <string.h>
  29
  30 #include <glib.h>
  31
  32 #include "idmap.h"
  33
  34 #define BITS_PER_LONG (sizeof(unsigned long) * 8)
  35
  36 struct idmap {
  37         unsigned long *bits;
  38         unsigned int size;
  39         unsigned int min;
  40         unsigned int max;
  41 };
  42
  43 static inline int ffz(unsigned long word)
  44 {
  45         return __builtin_ctzl(~word);
  46 }
  47
  48 /*
  49  * Stolen from linux kernel lib/find_next_bit.c
  50  */
  51 static unsigned int find_next_zero_bit(const unsigned long *addr,
  52                                         unsigned int size,
  53                                         unsigned int offset)
  54 {
  55         const unsigned long *p = addr + offset / BITS_PER_LONG;
  56         unsigned int result = offset & ~(BITS_PER_LONG-1);
  57         unsigned long tmp;
  58
  59         if (offset >= size)
  60                 return size;
  61
  62         size -= result;
  63         offset %= BITS_PER_LONG;
  64
  65         if (offset) {
  66                 tmp = *(p++);
  67                 tmp |= ~0UL >> (BITS_PER_LONG - offset);
  68
  69                 if (size < BITS_PER_LONG)
  70                         goto found_first;
  71
  72                 if (~tmp)
  73                         goto found_middle;
  74
  75                 size -= BITS_PER_LONG;
  76                 result += BITS_PER_LONG;
  77         }
  78
  79         while (size & ~(BITS_PER_LONG-1)) {
  80                 if (~(tmp = *(p++)))
  81                         goto found_middle;
  82
  83                 size -= BITS_PER_LONG;
  84                 result += BITS_PER_LONG;
  85         }
  86
  87         if (!size)
  88                 return result;
  89
  90         tmp = *p;
  91
  92 found_first:
  93         tmp |= ~0UL << size;
  94
  95         if (tmp == ~0UL)        /* Are any bits zero? */
  96                 return result + size;   /* Nope. */
  97
  98 found_middle:
  99         return result + ffz(tmp);
 100 }
 101
 102 struct idmap *idmap_new_from_range(unsigned int min, unsigned int max)
 103 {
 104         struct idmap *ret = g_new0(struct idmap, 1);
 105         unsigned int size = max - min + 1;
 106
 107         ret->bits = g_new0(unsigned long,
 108                                 (size + BITS_PER_LONG - 1) / BITS_PER_LONG);
 109         ret->size = size;
 110         ret->min = min;
 111         ret->max = max;
 112
 113         return ret;
 114 }
 115
 116 struct idmap *idmap_new(unsigned int size)
 117 {
 118         return idmap_new_from_range(1, size);
 119 }
 120
 121 void idmap_free(struct idmap *idmap)
 122 {
 123         g_free(idmap->bits);
 124         g_free(idmap);
 125 }
 126
 127 void idmap_put(struct idmap *idmap, unsigned int id)
 128 {
 129         unsigned int offset = (id - idmap->min) / BITS_PER_LONG;
 130
 131         id -= idmap->min;
 132
 133         if (id > idmap->size)
 134                 return;
 135
 136         id %= BITS_PER_LONG;
 137
 138         idmap->bits[offset] &= ~(1 << id);
 139 }
 140
 141 unsigned int idmap_alloc(struct idmap *idmap)
 142 {
 143         unsigned int bit;
 144         unsigned int offset;
 145
 146         bit = find_next_zero_bit(idmap->bits, idmap->size, 0);
 147
 148         if (bit >= idmap->size)
 149                 return idmap->max + 1;
 150
 151         offset = bit / BITS_PER_LONG;
 152         idmap->bits[offset] |= 1 << (bit % BITS_PER_LONG);
 153
 154         return bit + idmap->min;
 155 }
 156
 157 void idmap_take(struct idmap *idmap, unsigned int id)
 158 {
 159         unsigned int bit = id - idmap->min;
 160         unsigned int offset;
 161
 162         if (bit >= idmap->size)
 163                 return;
 164
 165         offset = bit / BITS_PER_LONG;
 166         idmap->bits[offset] |= 1 << (bit % BITS_PER_LONG);
 167 }
 168
 169 /*
 170  * Allocate the next bit skipping the ids up to and including last.  If there
 171  * is no free ids until the max id is encountered, the counter is wrapped back
 172  * to min and the search starts again.
 173  */
 174 unsigned int idmap_alloc_next(struct idmap *idmap, unsigned int last)
 175 {
 176         unsigned int bit;
 177         unsigned int offset;
 178
 179         if (last < idmap->min || last > idmap->max)
 180                 return idmap->max + 1;
 181
 182         bit = find_next_zero_bit(idmap->bits, idmap->size,
 183                                         last - idmap->min + 1);
 184
 185         if (bit >= idmap->size)
 186                 return idmap_alloc(idmap);
 187
 188         offset = bit / BITS_PER_LONG;
 189         idmap->bits[offset] |= 1 << (bit % BITS_PER_LONG);
 190
 191         return bit + idmap->min;
 192 }
 193
 194 unsigned int idmap_get_min(struct idmap *idmap)
 195 {
 196         return idmap->min;
 197 }
 198
 199 unsigned int idmap_get_max(struct idmap *idmap)
 200 {
 201         return idmap->max;
 202 }