array.h

Go to the documentation of this file.

// Copyright (C) 2011 CNRS - Ecole Polytechnique - INRIA.
//
// This file is part of TIFA.
//
// TIFA 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.
//
// TIFA 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 Street, Fifth Floor, Boston, MA  02110-1301 USA.

#if !defined(_TIFA_ARRAY_H_)

#define _TIFA_ARRAY_H_

#include "tifa_config.h"

#include <inttypes.h>
#include <stdbool.h>
#include <gmp.h>

#include "bitstring_t.h"

#ifdef __cplusplus
extern "C" {
#endif

#define ELONGATION 16

#define NOT_IN_ARRAY UINT32_MAX

#define ARRAY_IS_FULL(ARRAY_PTR) ((ARRAY_PTR)->length == (ARRAY_PTR)->alloced)

/*
 *-----------------------------------------------------------------------------
 *              byte_array_t and associated functions
 *-----------------------------------------------------------------------------
 */

struct struct_byte_array_t {
    uint32_t alloced;
    uint32_t length;
    unsigned char* data;
};

typedef struct struct_byte_array_t byte_array_t;

byte_array_t* alloc_byte_array(uint32_t length);

void free_byte_array(byte_array_t* array);

#define reset_byte_array(ARRAY) do {(ARRAY)->length = 0;} while (0)

void resize_byte_array(byte_array_t* const array, uint32_t alloced);

void append_byte_to_array(byte_array_t* array, const unsigned char to_append);

void append_byte_array(byte_array_t* const array,
                       const byte_array_t* const to_append);

void swap_byte_array(byte_array_t* const a, byte_array_t* const b);

void print_byte_array(const byte_array_t* const array);

void ins_sort_byte_array(byte_array_t* const array);

void qsort_byte_array(byte_array_t* const array);

uint32_t index_in_byte_array(unsigned char to_find,
                             const byte_array_t* const array);

inline static bool
is_in_byte_array(unsigned char to_find, const byte_array_t* const array) {
    return (NOT_IN_ARRAY != index_in_byte_array(to_find, array));
}

uint32_t index_in_sorted_byte_array(unsigned char to_find,
                                    const byte_array_t* const sorted_array,
                                    uint32_t min_index, uint32_t max_index);

inline static bool
is_in_sorted_byte_array(unsigned char to_find,
                        const byte_array_t* const array) {
    return (NOT_IN_ARRAY != index_in_sorted_byte_array(
                                to_find,
                                array,
                                0,
                                array->length - 1
                            )
            );
}

/*
 *-----------------------------------------------------------------------------
 *              uint32_array_t and associated functions
 *-----------------------------------------------------------------------------
 */

struct struct_uint32_array_t {
    uint32_t alloced;
    uint32_t length;
    uint32_t* data;
};

typedef struct struct_uint32_array_t uint32_array_t;

uint32_array_t* alloc_uint32_array(uint32_t length);

void free_uint32_array(uint32_array_t* array);

#define reset_uint32_array(ARRAY) do {(ARRAY)->length = 0;} while (0)

void resize_uint32_array(uint32_array_t* const array, uint32_t alloced);

void append_uint32_to_array(uint32_array_t* array, const uint32_t to_append);

void append_uint32_array(uint32_array_t* const array,
                         const uint32_array_t* const to_append);

void swap_uint32_array(uint32_array_t* const a, uint32_array_t* const b);

void print_uint32_array(const uint32_array_t* const array);

void ins_sort_uint32_array(uint32_array_t* const array);

void qsort_uint32_array(uint32_array_t* const array);

uint32_t index_in_uint32_array(uint32_t to_find,
                               const uint32_array_t* const array);

inline static bool
is_in_uint32_array(uint32_t to_find, const uint32_array_t* const array) {
    return (NOT_IN_ARRAY != index_in_uint32_array(to_find, array));
}

uint32_t index_in_sorted_uint32_array(uint32_t to_find,
                                      const uint32_array_t* const sorted_array,
                                      uint32_t min_index, uint32_t max_index);

inline static bool
is_in_sorted_uint32_array(uint32_t to_find, const uint32_array_t* const array) {
    return (NOT_IN_ARRAY != index_in_sorted_uint32_array(
                                to_find,
                                array,
                                0,
                                array->length - 1
                            )
            );
}

/*
 *-----------------------------------------------------------------------------
 *              int32_array_t and associated functions
 *-----------------------------------------------------------------------------
 */

struct struct_int32_array_t {
    uint32_t alloced;
    uint32_t length;
    int32_t* data;
};

typedef struct struct_int32_array_t int32_array_t;

int32_array_t* alloc_int32_array(uint32_t length);

void free_int32_array(int32_array_t* array);

#define reset_int32_array(ARRAY) do {(ARRAY)->length = 0;} while (0)

void resize_int32_array(int32_array_t* const array, uint32_t alloced);

void append_int32_to_array(int32_array_t* array, const int32_t to_append);

void append_int32_array(int32_array_t* const array,
                        const int32_array_t* const to_append);

void swap_int32_array(int32_array_t* const a, int32_array_t* const b);

void print_int32_array(const int32_array_t* const array);

uint32_t index_in_int32_array(int32_t to_find,
                              const int32_array_t* const array);

inline static bool
is_in_int32_array(int32_t to_find, const int32_array_t* const array) {
    return (NOT_IN_ARRAY != index_in_int32_array(to_find, array));
}

uint32_t index_in_sorted_int32_array(int32_t to_find,
                                     const int32_array_t* const sorted_array,
                                     uint32_t min_index, uint32_t max_index);

inline static bool
is_in_sorted_int32_array(int32_t to_find, const int32_array_t* const array) {
    return (NOT_IN_ARRAY != index_in_sorted_int32_array(
                                to_find,
                                array,
                                0,
                                array->length - 1
                            )
            );
}

/*
 *-----------------------------------------------------------------------------
 *                  mpz_array_t and associated functions
 *-----------------------------------------------------------------------------
 */

struct struct_mpz_array_t {
    uint32_t alloced;
    uint32_t length;
    mpz_t* data;
};
typedef struct struct_mpz_array_t mpz_array_t;

mpz_array_t* alloc_mpz_array(uint32_t length);

void free_mpz_array(mpz_array_t* array);

#define reset_mpz_array(ARRAY) do {(ARRAY)->length = 0;} while (0)

void resize_mpz_array(mpz_array_t* const array, uint32_t alloced);

void swap_mpz_array(mpz_array_t* const a, mpz_array_t* const b);

void append_mpz_to_array(mpz_array_t* array, const mpz_t to_append);

void append_mpz_array(mpz_array_t* const array,
                      const mpz_array_t* const to_append);

void print_mpz_array(const mpz_array_t* const array);

uint32_t index_in_mpz_array(const mpz_t to_find,
                            const mpz_array_t* const array);
uint32_t index_in_sorted_mpz_array(const mpz_t to_find,
                                   const mpz_array_t* const sorted_array,
                                   uint32_t min_index, uint32_t max_index);

inline static bool
is_in_mpz_array(const mpz_t to_find, const mpz_array_t* const array) {
    return (NOT_IN_ARRAY != index_in_mpz_array(to_find, array));
}

void ins_sort_mpz_array(mpz_array_t* const array);

void qsort_mpz_array(mpz_array_t* const array);

inline static bool
is_in_sorted_mpz_array(const mpz_t to_find, const mpz_array_t* const array) {
    return (NOT_IN_ARRAY != index_in_sorted_mpz_array(
                                to_find,
                                array,
                                0,
                                array->length - 1
                            )
           );
}

/*
 *-----------------------------------------------------------------------------
 *                  binary_array_t and associated functions
 *-----------------------------------------------------------------------------
 */

struct struct_binary_array_t {
   uint32_t alloced;
   uint32_t length;
   TIFA_BITSTRING_T* data;
};
typedef struct struct_binary_array_t binary_array_t;

binary_array_t* alloc_binary_array(uint32_t length);

void free_binary_array(binary_array_t* array);

#define reset_binary_array(ARRAY) do {(ARRAY)->length = 0;} while (0)

void resize_binary_array(binary_array_t* const array, uint32_t alloced);

void append_bit_to_array(binary_array_t* array, const unsigned int to_append);

void print_binary_array(const binary_array_t* const array);

inline static uint8_t
get_array_bit(uint32_t index, const binary_array_t* const array) {
#if BITSTRING_T_SIZE_IS_POW_OF_TWO
    uint32_t offset = index & (BITSTRING_T_BITSIZE - 1);
    index >>= POW_TWO_BITSTRING_T_SIZE;
#else
    uint32_t offset = index % BITSTRING_T_BITSIZE;
    index /= BITSTRING_T_BITSIZE;
#endif
    offset = BITSTRING_T_BITSIZE - 1 - offset;
    if (0 == ((((TIFA_BITSTRING_T)1)<<offset) & array->data[index])) {
        return 0;
    } else {
        return 1;
    }
}

inline static void
set_array_bit_to_one(uint32_t index, binary_array_t* const array) {
#if BITSTRING_T_SIZE_IS_POW_OF_TWO
    uint32_t offset = index & (BITSTRING_T_BITSIZE - 1);
    index >>= POW_TWO_BITSTRING_T_SIZE;
#else
    uint32_t offset = index % BITSTRING_T_BITSIZE;
    index /= BITSTRING_T_BITSIZE;
#endif
    offset = BITSTRING_T_BITSIZE - 1 - offset;
    array->data[index] |= (((TIFA_BITSTRING_T)1)<<offset);
}

inline static void
set_array_bit_to_zero(uint32_t index, binary_array_t* const array) {
#if BITSTRING_T_SIZE_IS_POW_OF_TWO
    uint32_t offset = index & (BITSTRING_T_BITSIZE - 1);
    index >>= POW_TWO_BITSTRING_T_SIZE;
#else
    uint32_t offset = index % BITSTRING_T_BITSIZE;
    index /= BITSTRING_T_BITSIZE;
#endif
    offset = BITSTRING_T_BITSIZE - 1 - offset;
    array->data[index] &= !(((TIFA_BITSTRING_T)1)<<offset);
}

inline static void
flip_array_bit(uint32_t index, binary_array_t* const array) {
#if BITSTRING_T_SIZE_IS_POW_OF_TWO
    uint32_t offset = index & (BITSTRING_T_BITSIZE - 1);
    index >>= POW_TWO_BITSTRING_T_SIZE;
#else
    uint32_t offset = index % BITSTRING_T_BITSIZE;
    index /= BITSTRING_T_BITSIZE;
#endif
    offset = BITSTRING_T_BITSIZE - 1 - offset;
    array->data[index] ^= (((TIFA_BITSTRING_T)1)<<offset);
}

#ifdef __cplusplus
}
#endif

#endif

---