root/libutil/idset.c

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. idset_open
  2. idset_empty
  3. idset_add
  4. idset_contains
  5. idset_first
  6. idset_next
  7. idset_count
  8. idset_close

/*
 * Copyright (c) 2005, 2006, 2007 Tama Communications Corporation
 *
 * This file is part of GNU GLOBAL.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program 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 General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <stdlib.h>
#ifdef HAVE_LIMITS_H
#include <limits.h>
#endif
#include "checkalloc.h"
#include "die.h"
#include "idset.h"

#ifndef CHAR_BIT
#define CHAR_BIT 8
#endif
#undef LONG_BIT
#define LONG_BIT        (sizeof(long) * CHAR_BIT)       /* maybe 32 or 64 */

/*
 * idset->min is initialized to END_OF_ID.
 * (You may use idset->max instead of idset->min.)
 */
#define IS_EMPTY(idset)  ((idset)->min == END_OF_ID ? 1 : 0)

/*
Idset: usage and memory status

                                idset->set
                                []

idset = idset_open(21)          000000000000000000000___________
                                 v
idset_add(idset, 1)             010000000000000000000___________
                                  v
idset_add(idset, 2)             011000000000000000000___________
                                                    v
idset_add(idset, 20)            011000000000000000001___________

idset_contains(idset, 2) == true
idset_contains(idset, 3) == false

idset_close(idset)              []

Idset's index always start from 0 according to the custom of C language.
I you want to treat 1-20 then you must invoke idset_open() with a argument 21.

        idset = idset_open(21);
        idset_add(idset, 0);            => OK
        idset_add(idset, 1);            => OK
                ...
        idset_add(idset, 20);           => OK
        idset_add(idset, 21);           => ERROR (idset_add: id is out of range.)

The range of value is from 0 to the maximum value expressible by unsigned integer - 1.
You should define index as an unsigned integer, and use END_OF_ID like follows:

        unsigned int id;
        for (id = idset_first(set); id != END_OF_ID; id = idset_next(set))
                -- processing about an id --
 */
/*
 * bit mask table
 * Prepare all bit mask for performance.
 */
static unsigned long *bit;

/*
 * Allocate memory for new idset.
 */
IDSET *
idset_open(unsigned int size)
{
        IDSET *idset = (IDSET *)check_malloc(sizeof(IDSET));
        int i;

        if (bit == NULL) {
                bit = (unsigned long *)check_calloc(sizeof(unsigned long), LONG_BIT);
                for (i = 0; i < LONG_BIT; i++)
                        bit[i] = 1UL << i;
        }
        idset->set = (unsigned long *)check_calloc(sizeof(unsigned long), (size + LONG_BIT - 1) / LONG_BIT);
        idset->size = size;
        /*
         * Initialize all id expressions using invalid value.
         * END_OF_ID means 'no value' or 'out of range'.
         */
        idset->min = idset->max = idset->lastid = END_OF_ID;
        return idset;
}
/*
 * Return true if idset is empty.
 *
 *      i)      idset   idset structure
 *      r)              1: empty, 0: not empty
 */
int
idset_empty(IDSET *idset)
{
        return IS_EMPTY(idset);
}
/*
 * Add id to the idset.
 *
 *      i)      idset   idset structure
 *      i)      id      id number
 */
void
idset_add(IDSET *idset, unsigned int id)
{
        int empty = IS_EMPTY(idset);

        if (id >= idset->size)
                die("idset_add: id is out of range.");
        idset->set[id / LONG_BIT] |= bit[id % LONG_BIT];
        if (empty)
                idset->max = idset->min = id;
        else if (id > idset->max)
                idset->max = id;
        else if (id < idset->min)
                idset->min = id;
}
/*
 * Whether or not idset includes specified id.
 *
 *      i)      idset   idset structure
 *      i)      id      id number
 *      r)              true: contains, false: doesn't contain
 */
int
idset_contains(IDSET *idset, unsigned int id)
{
        if (IS_EMPTY(idset))
                return 0;
        if (id < idset->min || id > idset->max)
                return 0;
        return (idset->set[id / LONG_BIT] & bit[id % LONG_BIT]) != 0;
}
/*
 * Get first id.
 *
 *      i)      idset   idset structure
 *      r)              id (END_OF_ID: end of id)
 *
 */
unsigned int
idset_first(IDSET *idset)
{
        /* There is no need to check whether idset is empty
           because idset->min is initialized with END_OF_ID. */
        return idset->lastid = idset->min;
}
/*
 * Get next id.
 *
 *      i)      idset   idset structure
 *      r)              id (END_OF_ID: end of id)
 *
 */
unsigned int
idset_next(IDSET *idset)
{
        unsigned int i, limit;
        int index0, index1;

        if (IS_EMPTY(idset))
                return END_OF_ID;
        if (idset->lastid >= idset->max)
                return END_OF_ID;
        limit = idset->max / LONG_BIT + 1;
        index0 = idset->lastid / LONG_BIT;
        index1 = idset->lastid % LONG_BIT;
        for (i = ++index1; i < LONG_BIT; i++)
                if (bit[i] & idset->set[index0])
                        return idset->lastid = index0 * LONG_BIT + i;
        index0++;
        for (i = index0; i < limit && idset->set[i] == 0; i++)
                ;
        if (i >= limit)
                die("idset_next: internal error.");
        index0 = i;
        for (i = 0; i < LONG_BIT; i++)
                if (bit[i] & idset->set[index0])
                        return idset->lastid = index0 * LONG_BIT + i;
        die("idset_next: internal error.");
}
/*
 * Return the number of bits.
 *
 *      i)      idset   idset structure
 *      r)              number of bits
 */
unsigned int
idset_count(IDSET *idset)
{
        unsigned int id, count = 0;

        for (id = idset_first(idset); id != END_OF_ID; id = idset_next(idset))
                count++;
        return count;
}
/*
 * Free memory for the idset.
 */
void
idset_close(IDSET *idset)
{
        free(idset->set);
        free(idset);
}

/* [<][>][^][v][top][bottom][index][help] */