src/bitmask.c

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

#include "qpid/dispatch/bitmask.h"

#include "qpid/dispatch/alloc.h"

#include <assert.h>
#include <stdint.h>

#define QD_BITMASK_LONGS 2
#define QD_BITMASK_BITS  (QD_BITMASK_LONGS * 64)

struct qd_bitmask_t {
    uint64_t array[QD_BITMASK_LONGS];
    int      first_set;
    int      cardinality;
};

ALLOC_DECLARE(qd_bitmask_t);
ALLOC_DEFINE(qd_bitmask_t);

#define MASK_INDEX(num)  (num / 64)
#define MASK_ONEHOT(num) (((uint64_t) 1) << (num % 64))
#define FIRST_NONE    -1
#define FIRST_UNKNOWN -2


int qd_bitmask_width()
{
    return QD_BITMASK_BITS;
}


qd_bitmask_t *qd_bitmask(int initial)
{
    qd_bitmask_t *b = new_qd_bitmask_t();
    if (initial)
        qd_bitmask_set_all(b);
    else
        qd_bitmask_clear_all(b);
    return b;
}


void qd_bitmask_free(qd_bitmask_t *b)
{
    if (!b) return;
    free_qd_bitmask_t(b);
}


void qd_bitmask_set_all(qd_bitmask_t *b)
{
    for (int i = 0; i < QD_BITMASK_LONGS; i++)
        b->array[i] = 0xFFFFFFFFFFFFFFFF;
    b->first_set   = 0;
    b->cardinality = QD_BITMASK_BITS;
}


void qd_bitmask_clear_all(qd_bitmask_t *b)
{
    for (int i = 0; i < QD_BITMASK_LONGS; i++)
        b->array[i] = 0;
    b->first_set   = FIRST_NONE;
    b->cardinality = 0;
}


int qd_bitmask_set_bit(qd_bitmask_t *b, int bitnum)
{
    int old_value = 1;
    assert(bitnum < QD_BITMASK_BITS);
    if ((b->array[MASK_INDEX(bitnum)] & MASK_ONEHOT(bitnum)) == 0) {
        old_value = 0;
        b->cardinality++;
    }

    b->array[MASK_INDEX(bitnum)] |= MASK_ONEHOT(bitnum);
    if (b->first_set > bitnum || b->first_set < 0)
        b->first_set = bitnum;

    return old_value;
}


int qd_bitmask_clear_bit(qd_bitmask_t *b, int bitnum)
{
    int old_value = 0;
    assert(bitnum < QD_BITMASK_BITS);
    if (b->array[MASK_INDEX(bitnum)] & MASK_ONEHOT(bitnum)) {
        old_value = 1;
        b->cardinality--;
    }

    b->array[MASK_INDEX(bitnum)] &= ~(MASK_ONEHOT(bitnum));
    if (b->first_set == bitnum)
        b->first_set = FIRST_UNKNOWN;

    return old_value;
}


int qd_bitmask_value(qd_bitmask_t *b, int bitnum)
{
    return (b->array[MASK_INDEX(bitnum)] & MASK_ONEHOT(bitnum)) ? 1 : 0;
}


int qd_bitmask_first_set(qd_bitmask_t *b, int *bitnum)
{
    //
    // If the passed in qd_bitmask_t *b pointer is null, we want to avoid a crash by returning immediately.
    //
    if (!b)
        return 0;

    if (b->first_set == FIRST_UNKNOWN) {
        b->first_set = FIRST_NONE;
        for (int i = 0; i < QD_BITMASK_LONGS; i++)
            if (b->array[i]) {
                for (int j = 0; j < 64; j++)
                    if ((((uint64_t) 1) << j) & b->array[i]) {
                        b->first_set = i * 64 + j;
                        break;
                    }
                break;
            }
    }

    if (b->first_set == FIRST_NONE)
        return 0;
    *bitnum = b->first_set;
    return 1;
}


int qd_bitmask_cardinality(const qd_bitmask_t *b)
{
    return b->cardinality;
}


bool qd_bitmask_valid_bit_value(int bitnum)
{
    return (bitnum >= 0 && bitnum < QD_BITMASK_BITS);
}


int _qdbm_start(qd_bitmask_t *b)
{
    int v;
    if (qd_bitmask_first_set(b, &v))
        return v;
    return -1;
}


void _qdbm_next(qd_bitmask_t *b, int *v)
{
    if (*v == QD_BITMASK_BITS - 1) {
        *v = -1;
        return;
    }

    int      idx  = MASK_INDEX(*v);
    uint64_t bits = MASK_ONEHOT(*v);
    int      next = *v;

    while (1) {
        next++;
        if (bits & 0x8000000000000000LL) {
            if (++idx == QD_BITMASK_LONGS) {
                *v = -1;
                return;
            }
            bits = 1;
        } else
            bits = bits << 1;

        if (b->array[idx] & bits) {
            *v = next;
            return;
        }
    }
}