эффективный массив памяти в C - PullRequest
Новая
       5

эффективный массив памяти в C

3 голосов
/ 27 июля 2011

Мне нужно хранить в памяти очень длинный массив. Каждый элемент массива будет просто флагом ИСТИНА / ЛОЖЬ (0/1).Мне нужно, чтобы он был очень эффективным с точки зрения памяти, поэтому я подумал о том, чтобы реализовать его как бит с маской поверх области unsigned char.Каждый char в памяти должен дать мне как минимум 8 флагов.Я реализовал следующие функции: 

static SIZE = 8; /* 8 bits = 1 byte = 1 char */

/* creates and initializes the array for N elements */
unsigned char *new_bit_array(long n) {
    int extra = (n % SIZE) ? 1 : 0;
    size_t ms = ((n / SIZE)+extra) * sizeof(unsigned char);
    unsigned char *p = malloc(ms);
    memset(p,0xFF,ms);
    return p;
}

/* mask setter for nth bit of a char, call by function bit_array_set*/
char bit_mask_set(short nbit,short value) {    
    if (value)
        return  0xFF;
    if (nbit == 0) 
        return 0x7F;
    else if (nbit == 1)
        return 0xBF;
    else if (nbit == 2) 
        return 0xDF;
    else if (nbit == 3) 
        return 0xEF;
    else if (nbit == 4) 
        return 0xF7;
    else if (nbit == 5) 
        return 0xFB;
    else if (nbit == 6) 
        return 0xFD;
    else if (nbit == 7) 
        return 0xFE;
    return 0xFF;
}

/* mask setter for nth element of the array */
void bit_array_set(unsigned char *p,long i,int value) {
    p[i/] &= bit_mask_set(i % SIZE,value);
}

/* mask getter for nth bit of a char, call by function bit_array_get */
char bit_mask_get(short nbit) {
    if (nbit == 0) 
        return 0x80;
    else if (nbit == 1)
        return 0x40;
    else if (nbit == 2) 
        return 0x20;
    else if (nbit == 3) 
        return 0x10;
    else if (nbit == 4) 
        return 0x08;
    else if (nbit == 5) 
        return 0x04;
    else if (nbit == 6) 
        return 0x02;
    else if (nbit == 7) 
        return 0x01;
    return 0x00;
}

/* mask getter for nth element of the array */
short bit_array_get(unsigned char *p,long i) {
    return p[i/SIZE] & bit_mask_get(i % SIZE) ? 1 : 0;
}

Этот код работает нормально, но мой вопрос в том, есть ли какие-либо встроенные функции в C или в какой-либо широко используемой библиотеке (например, glib), которая бы обеспечивала те же функции?

... а также, если есть более эффективные способы реализации bit_mask_get и bit_mask_set, IF с 7 ветвями выглядят ужасно.Любые другие комментарии к этому коду также приветствуются.

Ответы [ 3 ]

8 голосов
/ 27 июля 2011

Вы можете сделать это проще: 

unsigned char flag_bitmask[MAX_FLAGS];

void setFlag( int flag) {
    flag_bitmask[flag / 8] |= (1 << (flag % 8) );
}

char isFlagSet(int flag) {
    return flag_bitmask[flag / 8] & (1 << (flag % 8) );
}

void unSetFlag(int flag) {
    flag_bitmask[flag / 8] &= ~(1 << (flag % 8) );
}

Я часто его использую, и вы можете передать массив flag_bitmask вместо того, чтобы использовать его как глобальный.

3 голосов
/ 27 июля 2011

Вы можете заменить свою SIZE константу макросом CHAR_BIT из <limits.h>, что делает то же самое.

В функции new_bit_array вы можете заменить 0xFF на (unsigned char) ~0, который не зависит от количества бит в символе.Хотя было бы проще инициализировать память нулевыми битами, возможно, используя calloc вместо malloc.

В bit_masK_get, вы можете заменить тело следующим: 

return 1 << nbit;

Затем аналогичным образом замените bit_mask_set на: 

return (!!value) << nbit;

Они размещают биты в порядке, отличном от вашего, но это не имеет значения, если они согласованы между собой.

2 голосов
/ 27 июля 2011

Вы можете использовать битовые поля в структурах.Вы можете иметь массив следующей структуры: 

struct bitflags {
    unsigned char f0:1;
    unsigned char f1:1;
    unsigned char f2:1;
    unsigned char f3:1;
    unsigned char f4:1;
    unsigned char f5:1;
    unsigned char f6:1;
    unsigned char f7:1;
};

struct bitflags many_flags[9001];
many_flags[0].f0 = 1;
...