/*

Copyright (c) 2008 - 2026, Ilan Schnell; All Rights Reserved

bitarray is published under the PSF license.

This file is the C part of the bitarray package.

All functionality of the bitarray object is implemented here.

Author: Ilan Schnell

*/

#define PY_SSIZE_T_CLEAN

#include "Python.h"

#include "pythoncapi_compat.h"

#include "bitarray.h"

/* size used when reading / writing blocks from files (in bytes) */

#define BLOCKSIZE 65536

/* translation table - setup during module initialization */

static char reverse_trans[256];

static PyTypeObject Bitarray_Type;

#define bitarray_Check(obj) PyObject_TypeCheck((obj), &Bitarray_Type)

static size_t

new_allocation(size_t size, size_t allocated, size_t newsize)

{

assert(allocated >= size);

assert(newsize > 0);

if (allocated >= newsize) {

/* current buffer is large enough to host the requested size */

if (newsize >= allocated / 2)

return allocated; /* minor downsize - keep current allocation */

return newsize; /* major downsize - shrink to exact size */

}

else {

/* need to grow buffer */

size_t new_alloc = newsize;

/* overallocate when previous size isn't zero and when growth

is moderate */

if (size != 0 && newsize / 2 <= allocated) {

/* overallocate proportional to the bitarray size and

add padding to make the allocated size multiple of 4 */

new_alloc += (newsize >> 4) + ((newsize < 8) ? 3 : 7);

new_alloc &= ~(size_t) 3;

}

return new_alloc;

}

}

static int

resize(bitarrayobject *self, Py_ssize_t nbits)

{

const size_t size = Py_SIZE(self);

const size_t allocated = self->allocated;

const size_t newsize = BYTES((size_t) nbits);

size_t new_allocated;

char *item;

if (self->ob_exports > 0) {

PyErr_SetString(PyExc_BufferError,

"cannot resize bitarray that is exporting buffers");

return -1;

}

if (self->buffer) {

PyErr_SetString(PyExc_BufferError, "cannot resize imported buffer");

return -1;

}

if (nbits < 0) {

PyErr_Format(PyExc_OverflowError, "bitarray resize %zd", nbits);

return -1;

}

#ifndef NDEBUG

assert(self->readonly == 0);

assert(allocated >= size && size == BYTES((size_t) self->nbits));

if (self->ob_item == NULL)

assert(size == 0 && allocated == 0);

assert(self->readonly == 0);

#endif

/* bypass everything when buffer size hasn't changed */

if (newsize == size)

goto done;

if (newsize == 0) {

PyMem_Free(self->ob_item);

self->ob_item = NULL;

Py_SET_SIZE(self, 0);

self->allocated = 0;

goto done;

}

new_allocated = new_allocation(size, allocated, newsize);

if (new_allocated == allocated) {

/* bypass reallocation */

Py_SET_SIZE(self, newsize);

goto done;

}

assert(new_allocated >= newsize);

item = PyMem_Realloc(self->ob_item, new_allocated);

if (item == NULL) {

PyErr_NoMemory();

return -1;

}

self->ob_item = item;

Py_SET_SIZE(self, newsize);

self->allocated = new_allocated;

done:

self->nbits = nbits;

return 0;

}

/* create new bitarray object without initialization of buffer */

static bitarrayobject *

newbitarrayobject(PyTypeObject *type, Py_ssize_t nbits, int endian)

{

const size_t nbytes = BYTES((size_t) nbits);

bitarrayobject *obj;

assert(nbits >= 0);

obj = (bitarrayobject *) type->tp_alloc(type, 0);

if (obj == NULL)

return NULL;

if (nbytes == 0) {

obj->ob_item = NULL;

}

else {

/* allocate exact size */

obj->ob_item = (char *) PyMem_Malloc(nbytes);

if (obj->ob_item == NULL) {

PyObject_Del(obj);

PyErr_NoMemory();

return NULL;

}

}

Py_SET_SIZE(obj, nbytes);

obj->allocated = nbytes; /* no overallocation */

obj->nbits = nbits;

obj->endian = endian;

obj->ob_exports = 0;

obj->weakreflist = NULL;

obj->buffer = NULL;

obj->readonly = 0;

return obj;

}

/* return new copy of bitarray object self */

static bitarrayobject *

bitarray_cp(bitarrayobject *self)

{

bitarrayobject *res;

res = newbitarrayobject(Py_TYPE(self), self->nbits, self->endian);

if (res == NULL)

return NULL;

if (Py_SIZE(self))

memcpy(res->ob_item, self->ob_item, (size_t) Py_SIZE(self));

return res;

}

static void

bitarray_dealloc(bitarrayobject *self)

{

if (self->weakreflist)

PyObject_ClearWeakRefs((PyObject *) self);

if (self->buffer) {

PyBuffer_Release(self->buffer);

PyMem_Free(self->buffer);

}

else if (self->ob_item) {

/* only free object's buffer - imported buffers cannot be freed */

assert(self->buffer == NULL);

PyMem_Free((void *) self->ob_item);

}

Py_TYPE(self)->tp_free((PyObject *) self);

}

/* Return 1 if buffers overlap, 0 otherwise.

'other' may be 'self'. In that case the buffers overlap unless the

bitarray is empty. Empty buffers never overlap.

*/

static int

buffers_overlap(bitarrayobject *self, bitarrayobject *other)

{

if (Py_SIZE(self) == 0 || Py_SIZE(other) == 0)

return 0;

/* is pointer ptr in buffer of bitarray a ? */

#define PIB(a, ptr) (a->ob_item <= ptr && ptr < a->ob_item + Py_SIZE(a))

return PIB(self, other->ob_item) || PIB(other, self->ob_item);

#undef PIB

}

/* reverse bits in first n characters of p */

static void

bytereverse(char *p, Py_ssize_t n)

{

assert(n >= 0);

while (n--) {

*p = reverse_trans[(unsigned char) *p];

p++;

}

}

/* The following two functions operate on first n bytes in buffer.

Within this region, they shift all bits by k positions to right,

i.e. towards higher addresses.

They operate on little-endian and big-endian bitarrays respectively.

As we shift right, we need to start with the highest address and loop

downwards such that lower bytes are still unaltered.

See also devel/shift_r8.c

*/

static void

shift_r8le(unsigned char *buff, Py_ssize_t n, int k)

{

Py_ssize_t w = 0;

#if HAVE_BUILTIN_BSWAP64 || PY_LITTLE_ENDIAN /* use shift word */

w = n / 8; /* number of words used for shifting */

n %= 8; /* number of remaining bytes */

#endif

while (n--) { /* shift in byte-range(8 * w, n) */

Py_ssize_t i = n + 8 * w;

buff[i] <<= k; /* shift byte */

if (n || w) /* add shifted next lower byte */

buff[i] |= buff[i - 1] >> (8 - k);

}

assert(w == 0 || ((uintptr_t) buff) % 4 == 0);

while (w--) { /* shift in word-range(0, w) */

uint64_t *p = ((uint64_t *) buff) + w;

#if HAVE_BUILTIN_BSWAP64 && PY_BIG_ENDIAN

*p = builtin_bswap64(*p);

*p <<= k;

*p = builtin_bswap64(*p);

#else

*p <<= k;

#endif

if (w) /* add shifted byte from next lower word */

buff[8 * w] |= buff[8 * w - 1] >> (8 - k);

}

}

static void

shift_r8be(unsigned char *buff, Py_ssize_t n, int k)

{

Py_ssize_t w = 0;

#if HAVE_BUILTIN_BSWAP64 || PY_BIG_ENDIAN /* use shift word */

w = n / 8; /* number of words used for shifting */

n %= 8; /* number of remaining bytes */

#endif

while (n--) { /* shift in byte-range(8 * w, n) */

Py_ssize_t i = n + 8 * w;

buff[i] >>= k; /* shift byte */

if (n || w) /* add shifted next lower byte */

buff[i] |= buff[i - 1] << (8 - k);

}

assert(w == 0 || ((uintptr_t) buff) % 4 == 0);

while (w--) { /* shift in word-range(0, w) */

uint64_t *p = ((uint64_t *) buff) + w;

#if HAVE_BUILTIN_BSWAP64 && PY_LITTLE_ENDIAN

*p = builtin_bswap64(*p);

*p >>= k;

*p = builtin_bswap64(*p);

#else

*p >>= k;

#endif

if (w) /* add shifted byte from next lower word */

buff[8 * w] |= buff[8 * w - 1] << (8 - k);

}

}

/* shift bits in byte-range(a, b) by k bits to right */

static void

shift_r8(bitarrayobject *self, Py_ssize_t a, Py_ssize_t b, int k)

{

unsigned char *buff = (unsigned char *) self->ob_item + a;

Py_ssize_t n = b - a; /* number of bytes to be shifted */

Py_ssize_t s = 0; /* distance to next aligned pointer */

assert(0 <= k && k < 8);

assert(0 <= a && a <= Py_SIZE(self));

assert(0 <= b && b <= Py_SIZE(self));

assert(self->readonly == 0);

if (k == 0 || n <= 0)

return;

if (n >= 8) {

s = to_aligned((void *) buff);

buff += s; /* align pointer for casting to (uint64_t *) */

n -= s;

}

if (IS_LE(self)) { /* little endian */

shift_r8le(buff, n, k);

if (s) {

buff[0] |= buff[-1] >> (8 - k);

shift_r8le(buff - s, s, k);

}

}

else { /* big endian */

shift_r8be(buff, n, k);

if (s) {

buff[0] |= buff[-1] << (8 - k);

shift_r8be(buff - s, s, k);

}

}

}

/* Copy n bits from other (starting at b) onto self (starting at a).

Please see devel/copy_n.py for more details.

Notes:

- self and other may have opposite bit-endianness

- other may equal self - copy a section of self onto itself

- when other and self are distinct objects, their buffers

may not overlap

*/

static void

copy_n(bitarrayobject *self, Py_ssize_t a,

bitarrayobject *other, Py_ssize_t b, Py_ssize_t n)

{

Py_ssize_t p3 = b / 8, i;

int sa = a % 8, sb = -(b % 8);

char t3 = 0; /* silence uninitialized warning on some compilers */

assert(0 <= n && n <= self->nbits && n <= other->nbits);

assert(0 <= a && a <= self->nbits - n);

assert(0 <= b && b <= other->nbits - n);

assert(self == other || !buffers_overlap(self, other));

assert(self->readonly == 0);

if (n == 0 || (self == other && a == b))

return;

if (sa + sb < 0) {

t3 = other->ob_item[p3++];

sb += 8;

}

if (n > sb) {

const Py_ssize_t p1 = a / 8, p2 = (a + n - 1) / 8, m = BYTES(n - sb);

const char *table = ones_table[IS_BE(self)];

char *cp1 = self->ob_item + p1, m1 = table[sa];

char *cp2 = self->ob_item + p2, m2 = table[(a + n) % 8];

char t1 = *cp1, t2 = *cp2;

assert(p1 + m <= Py_SIZE(self) && p3 + m <= Py_SIZE(other));

memmove(cp1, other->ob_item + p3, (size_t) m);

if (self->endian != other->endian)

bytereverse(cp1, m);

shift_r8(self, p1, p2 + 1, sa + sb);

if (m1)

*cp1 = (*cp1 & ~m1) | (t1 & m1); /* restore bits at p1 */

if (m2)

*cp2 = (*cp2 & m2) | (t2 & ~m2); /* restore bits at p2 */

}

for (i = 0; i < sb && i < n; i++) /* copy first sb bits */

setbit(self, i + a, t3 & BITMASK(other, i + b));

}

/* starting at start, delete n bits from self */

static int

delete_n(bitarrayobject *self, Py_ssize_t start, Py_ssize_t n)

{

const Py_ssize_t nbits = self->nbits;

assert(0 <= start && start <= nbits);

assert(0 <= n && n <= nbits - start);

/* start == nbits implies n == 0 */

assert(start != nbits || n == 0);

copy_n(self, start, self, start + n, nbits - start - n);

return resize(self, nbits - n);

}

/* starting at start, insert n (uninitialized) bits into self */

static int

insert_n(bitarrayobject *self, Py_ssize_t start, Py_ssize_t n)

{

const Py_ssize_t nbits = self->nbits;

assert(0 <= start && start <= nbits);

assert(n >= 0);

if (resize(self, nbits + n) < 0)

return -1;

copy_n(self, start + n, self, start, nbits - start);

return 0;

}

/* repeat self m times (negative m is treated as 0) */

static int

repeat(bitarrayobject *self, Py_ssize_t m)

{

Py_ssize_t q, k = self->nbits;

assert(self->readonly == 0);

if (k == 0 || m == 1) /* nothing to do */

return 0;

if (m <= 0) /* clear */

return resize(self, 0);

assert(m > 1 && k > 0);

if (k >= PY_SSIZE_T_MAX / m) {

PyErr_Format(PyExc_OverflowError,

"cannot repeat bitarray (of size %zd) %zd times", k, m);

return -1;

}

q = k * m; /* number of resulting bits */

if (resize(self, q) < 0)

return -1;

/* k: number of bits which have been copied so far */

while (k <= q / 2) { /* double copies */

copy_n(self, k, self, 0, k);

k *= 2;

}

assert(q / 2 < k && k <= q);

copy_n(self, k, self, 0, q - k); /* copy remaining bits */

return 0;

}

/* invert self[i] in-place */

static int

invert_index(bitarrayobject *self, Py_ssize_t i)

{

assert(self->readonly == 0);

if (i < 0)

i += self->nbits;

if (i < 0 || i >= self->nbits) {

PyErr_SetString(PyExc_IndexError, "index out of range");

return -1;

}

self->ob_item[i / 8] ^= BITMASK(self, i);

return 0;

}

/* invert bits self[a:b] in-place */

static void

invert_span(bitarrayobject *self, Py_ssize_t a, Py_ssize_t b)

{

const Py_ssize_t n = b - a; /* number of bits to invert */

Py_ssize_t i;

assert(0 <= a && a <= self->nbits);

assert(0 <= b && b <= self->nbits);

assert(self->readonly == 0);

if (n >= 64) {

const Py_ssize_t wa = (a + 63) / 64; /* word-range(wa, wb) */

const Py_ssize_t wb = b / 64;

uint64_t *wbuff = WBUFF(self);

invert_span(self, a, 64 * wa);

for (i = wa; i < wb; i++)

wbuff[i] = ~wbuff[i];

invert_span(self, 64 * wb, b);

}

else if (n >= 8) {

const Py_ssize_t ca = BYTES(a); /* char-range(ca, cb) */

const Py_ssize_t cb = b / 8;

char *buff = self->ob_item;

invert_span(self, a, 8 * ca);

for (i = ca; i < cb; i++)

buff[i] = ~buff[i];

invert_span(self, 8 * cb, b);

}

else { /* (bit-) range(a, b) */

for (i = a; i < b; i++)

self->ob_item[i / 8] ^= BITMASK(self, i);

}

}

/* invert bits self[start:stop:step] in-place */

static void

invert_range(bitarrayobject *self,

Py_ssize_t start, Py_ssize_t stop, Py_ssize_t step)

{

assert(self->readonly == 0);

adjust_slice(self->nbits, &start, &stop, &step);

if (step == 1) {

invert_span(self, start, stop);

}

else {

const char *table = bitmask_table[IS_BE(self)];

char *buff = self->ob_item;

Py_ssize_t i;

for (i = start; i < stop; i += step)

buff[i >> 3] ^= table[i & 7];

}

}

/* set bits self[a:b] to vi */

static void

set_span(bitarrayobject *self, Py_ssize_t a, Py_ssize_t b, int vi)

{

assert(0 <= a && a <= self->nbits);

assert(0 <= b && b <= self->nbits);

assert(self->readonly == 0);

if (b >= a + 8) {

const Py_ssize_t ca = BYTES(a); /* char-range(ca, cb) */

const Py_ssize_t cb = b / 8;

assert(a + 8 > 8 * ca && 8 * cb + 8 > b);

set_span(self, a, 8 * ca, vi);

memset(self->ob_item + ca, vi ? 0xff : 0x00, (size_t) (cb - ca));

set_span(self, 8 * cb, b, vi);

}

else { /* (bit-) range(a, b) */

while (a < b)

setbit(self, a++, vi);

}

}

/* set bits self[start:stop:step] to vi */

static void

set_range(bitarrayobject *self,

Py_ssize_t start, Py_ssize_t stop, Py_ssize_t step, int vi)

{

assert(self->readonly == 0);

adjust_slice(self->nbits, &start, &stop, &step);

if (step == 1) {

set_span(self, start, stop, vi);

}

else {

const char *table = bitmask_table[IS_BE(self)];

char *buff = self->ob_item;

Py_ssize_t i;

if (vi) {

for (i = start; i < stop; i += step)

buff[i >> 3] |= table[i & 7];

}

else {

for (i = start; i < stop; i += step)

buff[i >> 3] &= ~table[i & 7];

}

}

}

/* Return number of 1 bits in self[a:b]; cannot fail. */

static Py_ssize_t

count_span(bitarrayobject *self, Py_ssize_t a, Py_ssize_t b)

{

const Py_ssize_t n = b - a;

Py_ssize_t cnt = 0;

assert(0 <= a && a <= self->nbits);

assert(0 <= b && b <= self->nbits);

if (n >= 64) {

Py_ssize_t p = BYTES(a), w; /* first full byte */

p += to_aligned((void *) (self->ob_item + p)); /* align pointer */

w = (b / 8 - p) / 8; /* number of (full) words to count */

assert(8 * p - a < 64 && b - (8 * (p + 8 * w)) < 64 && w >= 0);

cnt += count_span(self, a, 8 * p);

cnt += popcnt_words((uint64_t *) (self->ob_item + p), w);

cnt += count_span(self, 8 * (p + 8 * w), b);

}

else if (n >= 8) {

const Py_ssize_t ca = BYTES(a); /* char-range(ca, cb) */

const Py_ssize_t cb = b / 8, m = cb - ca;

assert(8 * ca - a < 8 && b - 8 * cb < 8 && 0 <= m && m < 8);

cnt += count_span(self, a, 8 * ca);

if (m) { /* starting at ca count in m bytes */

uint64_t tmp = 0;

/* copy bytes we want to count into tmp word */

memcpy((char *) &tmp, self->ob_item + ca, (size_t) m);

cnt += popcnt_64(tmp);

}

cnt += count_span(self, 8 * cb, b);

}

else { /* (bit-) range(a, b) */

while (a < b)

cnt += getbit(self, a++);

}

return cnt;

}

/* return number of bits 'vi' in self[start:stop:step] */

static Py_ssize_t

count_range(bitarrayobject *self,

Py_ssize_t start, Py_ssize_t stop, Py_ssize_t step, int vi)

{

Py_ssize_t slicelength, cnt = 0;

slicelength = adjust_slice(self->nbits, &start, &stop, &step);

if (step == 1) {

cnt = count_span(self, start, stop);

}

else {

Py_ssize_t i;

for (i = start; i < stop; i += step)

cnt += getbit(self, i);

}

return vi ? cnt : slicelength - cnt;

}

/* return first (or rightmost in case right=1) occurrence

of vi in self[a:b], -1 when not found */

static Py_ssize_t

find_bit(bitarrayobject *self, int vi, Py_ssize_t a, Py_ssize_t b, int right);

static Py_ssize_t

find_bit_words(bitarrayobject *self, int vi,

Py_ssize_t a, Py_ssize_t b, int right)

{

const Py_ssize_t wa = (a + 63) / 64; /* word-range(wa, wb) */

const Py_ssize_t wb = b / 64;

const uint64_t *wbuff = WBUFF(self);

const uint64_t w = vi ? 0 : ~0;

Py_ssize_t res, i;

if (right) {

if ((res = find_bit(self, vi, 64 * wb, b, 1)) >= 0)

return res;

for (i = wb - 1; i >= wa; i--) { /* skip uint64 words */

if (w ^ wbuff[i])

return find_bit(self, vi, 64 * i, 64 * i + 64, 1);

}

return find_bit(self, vi, a, 64 * wa, 1);

}

else {

if ((res = find_bit(self, vi, a, 64 * wa, 0)) >= 0)

return res;

for (i = wa; i < wb; i++) { /* skip uint64 words */

if (w ^ wbuff[i])

return find_bit(self, vi, 64 * i, 64 * i + 64, 0);

}

return find_bit(self, vi, 64 * wb, b, 0);

}

}

static Py_ssize_t

find_bit_bytes(bitarrayobject *self, int vi,

Py_ssize_t a, Py_ssize_t b, int right)

{

const Py_ssize_t ca = BYTES(a); /* char-range(ca, cb) */

const Py_ssize_t cb = b / 8;

const char *buff = self->ob_item;

const char c = vi ? 0 : ~0;

Py_ssize_t res, i;

if (right) {

if ((res = find_bit(self, vi, 8 * cb, b, 1)) >= 0)

return res;

for (i = cb - 1; i >= ca; i--) { /* skip bytes */

if (c ^ buff[i])

return find_bit(self, vi, 8 * i, 8 * i + 8, 1);

}

return find_bit(self, vi, a, 8 * ca, 1);

}

else {

if ((res = find_bit(self, vi, a, 8 * ca, 0)) >= 0)

return res;

for (i = ca; i < cb; i++) { /* skip bytes */

if (c ^ buff[i])

return find_bit(self, vi, 8 * i, 8 * i + 8, 0);

}

return find_bit(self, vi, 8 * cb, b, 0);

}

}

static Py_ssize_t

find_bit(bitarrayobject *self, int vi, Py_ssize_t a, Py_ssize_t b, int right)

{

const Py_ssize_t n = b - a;

Py_ssize_t i;

assert(0 <= a && a <= self->nbits);

assert(0 <= b && b <= self->nbits);

assert(vi == 0 || vi == 1);

if (n <= 0)

return -1;

/* When the search range is greater than 64 bits, we skip uint64 words.

Note that we cannot check for n >= 64 here as the function could then

go into an infinite recursive loop when a word is found. */

if (n > 64)

return find_bit_words(self, vi, a, b, right);

/* For the same reason as above, we cannot check for n >= 8 here. */

if (n > 8)

return find_bit_bytes(self, vi, a, b, right);

/* finally, search for the desired bit by stepping one-by-one */

for (i = right ? b - 1 : a; a <= i && i < b; i += right ? -1 : 1)

if (getbit(self, i) == vi)

return i;

return -1;

}

/* Return first/rightmost occurrence of sub-bitarray (in self), such that

sub is contained within self[start:stop], or -1 when sub is not found. */

static Py_ssize_t

find_sub(bitarrayobject *self, bitarrayobject *sub,

Py_ssize_t start, Py_ssize_t stop, int right)

{

const Py_ssize_t sbits = sub->nbits;

const Py_ssize_t step = right ? -1 : 1;

Py_ssize_t i, k;

stop -= sbits - 1;

i = right ? stop - 1 : start;

while (start <= i && i < stop) {

for (k = 0; k < sbits; k++)

if (getbit(self, i + k) != getbit(sub, k))

goto next;

return i;

next:

i += step;

}

return -1;

}

/* return the number of non-overlapping occurrences of sub-bitarray within

self[start:stop] */

static Py_ssize_t

count_sub(bitarrayobject *self, bitarrayobject *sub,

Py_ssize_t start, Py_ssize_t stop)

{

const Py_ssize_t sbits = sub->nbits;

Py_ssize_t pos, cnt = 0;

assert(0 <= start && start <= self->nbits);

assert(0 <= stop && stop <= self->nbits);

if (sbits == 0)

return (start <= stop) ? stop - start + 1 : 0;

while ((pos = find_sub(self, sub, start, stop, 0)) >= 0) {

start = pos + sbits;

cnt++;

}

return cnt;

}

/* set item i in self to given value */

static int

set_item(bitarrayobject *self, Py_ssize_t i, PyObject *value)

{

int vi;

if (!conv_pybit(value, &vi))

return -1;

setbit(self, i, vi);

return 0;

}

static int

extend_bitarray(bitarrayobject *self, bitarrayobject *other)

{

/* We have to store the sizes before we resize, and since

other may be self, we also need to store other->nbits. */

const Py_ssize_t self_nbits = self->nbits;

const Py_ssize_t other_nbits = other->nbits;

if (resize(self, self_nbits + other_nbits) < 0)

return -1;

copy_n(self, self_nbits, other, 0, other_nbits);

return 0;

}

static int

extend_iter(bitarrayobject *self, PyObject *iter)

{

const Py_ssize_t nbits = self->nbits;

PyObject *item;

assert(PyIter_Check(iter));

while ((item = PyIter_Next(iter))) {

if (resize(self, self->nbits + 1) < 0 ||

set_item(self, self->nbits - 1, item) < 0)

{

Py_DECREF(item);

/* ignore resize() return value as we fail anyhow */

resize(self, nbits);

return -1;

}

Py_DECREF(item);

}

if (PyErr_Occurred())

return -1;

return 0;

}

static int

extend_sequence(bitarrayobject *self, PyObject *sequence)

{

const Py_ssize_t nbits = self->nbits;

Py_ssize_t n, i;

if ((n = PySequence_Size(sequence)) < 0)

return -1;

if (resize(self, nbits + n) < 0)

return -1;

for (i = 0; i < n; i++) {

PyObject *item = PySequence_GetItem(sequence, i);

if (item == NULL || set_item(self, nbits + i, item) < 0) {

Py_XDECREF(item);

resize(self, nbits);

return -1;

}

Py_DECREF(item);

}

return 0;

}

static int

extend_unicode01(bitarrayobject *self, PyObject *unicode)

{

const Py_ssize_t nbits = self->nbits;

const Py_ssize_t length = PyUnicode_GET_LENGTH(unicode);

Py_ssize_t i = nbits, j; /* i is the current write index in self */

if (resize(self, nbits + length) < 0)

return -1;

for (j = 0; j < length; j++) {

Py_UCS4 ch = PyUnicode_READ_CHAR(unicode, j);

switch (ch) {

case '0':

case '1':

setbit(self, i++, ch - '0');

continue;

case '_':

continue;

}

if (Py_UNICODE_ISSPACE(ch))

continue;

PyErr_Format(PyExc_ValueError, "expected '0' or '1' (or whitespace "

"or underscore), got '%c' (0x%02x)", ch, ch);

resize(self, nbits); /* no bits added on error */

return -1;

}

return resize(self, i); /* in case we ignored characters */

}

static int

extend_dispatch(bitarrayobject *self, PyObject *obj)

{

PyObject *iter;

/* dispatch on type */

if (bitarray_Check(obj)) /* bitarray */

return extend_bitarray(self, (bitarrayobject *) obj);

if (PyUnicode_Check(obj)) /* Unicode string */

return extend_unicode01(self, obj);

if (PySequence_Check(obj)) /* sequence */

return extend_sequence(self, obj);

if (PyIter_Check(obj)) /* iter */

return extend_iter(self, obj);

/* finally, try to get the iterator of the object */

if ((iter = PyObject_GetIter(obj))) {

int res = extend_iter(self, iter);

Py_DECREF(iter);

return res;

}

PyErr_Format(PyExc_TypeError,

"'%s' object is not iterable", Py_TYPE(obj)->tp_name);

return -1;

}

static PyTypeObject *

import_frozen_type(void)

{

PyTypeObject *frozen;

frozen = (PyTypeObject *) bitarray_module_attr("frozenbitarray");

if (frozen == NULL)

return NULL;

/* in case user changes bitarray.frozenbitarray */

if (!PyType_Check(frozen) || !PyType_IsSubtype(frozen, &Bitarray_Type)) {

PyErr_SetString(PyExc_TypeError,

"frozenbitarray is not a bitarray type");

Py_DECREF(frozen);

return NULL;

}

return frozen;

}

/* Set readonly member to 1 if self is an instance of frozenbitarray.

Return PyObject of self. On error, set exception and return NULL. */

static PyObject *

freeze_if_frozen(bitarrayobject *self)

{

PyTypeObject *frozen;

int is_frozen;

assert(self->ob_exports == 0 && self->buffer == NULL);

if (Py_TYPE(self) == &Bitarray_Type) /* shortcut for common case */

return (PyObject *) self;

frozen = import_frozen_type();

if (frozen == NULL)

return NULL;

is_frozen = PyObject_IsInstance((PyObject *) self,

(PyObject *) frozen);

Py_DECREF(frozen);

if (is_frozen < 0)

return NULL;

if (is_frozen) {

set_padbits(self);

self->readonly = 1;

}

return (PyObject *) self;

}

/**************************************************************************

Implementation of bitarray methods

**************************************************************************/

/*

All methods which modify the buffer need to raise an exception when the

buffer is read-only. This is necessary because the buffer may be imported

from another object which has a read-only buffer.

We decided to do this check at the top level here, by adding the

RAISE_IF_READONLY macro to all methods which modify the buffer.

We could have done it at the low level (in setbit(), etc.), however as

many of these functions have no return value we decided to do it here.

The situation is different from how resize() raises an exception when

called on an imported buffer. There, it is easy to raise the exception

in resize() itself, as there only one function which resizes the buffer,

and this function (resize()) needs to report failures anyway.

*/

/* raise when buffer is readonly */

#define RAISE_IF_READONLY(self, ret_value) \

if (((bitarrayobject *) self)->readonly) { \

PyErr_SetString(PyExc_TypeError, "cannot modify read-only memory"); \

return ret_value; \

}

static PyObject *

bitarray_all(bitarrayobject *self)

{

Py_ssize_t pos;

Py_BEGIN_CRITICAL_SECTION(self);

pos = find_bit(self, 0, 0, self->nbits, 0);

Py_END_CRITICAL_SECTION();

return PyBool_FromLong(pos == -1);

}