Как правильно reallo c битовый массив в C - PullRequest
Новая
       75

Как правильно reallo c битовый массив в C

3 голосов
/ 26 марта 2020

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

  1. Valgrind сообщает о нескольких недопустимых операциях чтения / записи
  2. Общее количество бит 968 вместо 999 (я полагаю, это связано с # 1) 
==109614== Invalid read of size 4
==109614==    at 0x10926F: get_bit (a.c:26)
==109614==    by 0x1093EF: main (a.c:56)
==109614==  Address 0x4a27094 is 0 bytes after a block of size 4 alloc'd
==109614==    at 0x483BB65: calloc (vg_replace_malloc.c:762)
==109614==    by 0x1092C8: init (a.c:32)
==109614==    by 0x10939A: main (a.c:50)
==109614== 
==109614== Invalid read of size 4
==109614==    at 0x1091A6: set_bit (a.c:18)
==109614==    by 0x109407: main (a.c:57)
==109614==  Address 0x4a27094 is 0 bytes after a block of size 4 alloc'd
==109614==    at 0x483BB65: calloc (vg_replace_malloc.c:762)
==109614==    by 0x1092C8: init (a.c:32)
==109614==    by 0x10939A: main (a.c:50)
==109614== 
==109614== Invalid write of size 4
==109614==    at 0x1091D9: set_bit (a.c:18)
==109614==    by 0x109407: main (a.c:57)
==109614==  Address 0x4a27094 is 0 bytes after a block of size 4 alloc'd
==109614==    at 0x483BB65: calloc (vg_replace_malloc.c:762)
==109614==    by 0x1092C8: init (a.c:32)
==109614==    by 0x10939A: main (a.c:50)
==109614== 
val=999
total bits set=968
..

#include <limits.h>    /* for CHAR_BIT */
#include <string.h>
#include <stdint.h>   /* for uint32_t */
#include <stdio.h>
#include <stdlib.h>

typedef uint32_t word_t; // I want to change this, from uint32_t to uint64_t
enum { BITS_PER_WORD = sizeof(word_t) * CHAR_BIT };
#define WORD_OFFSET(b) ((b) / BITS_PER_WORD)
#define BIT_OFFSET(b)  ((b) % BITS_PER_WORD)

typedef struct bm_ {
  word_t *bmp;
  int size;
} bm;

void set_bit(word_t *words, int n) {
  words[WORD_OFFSET(n)] |= ((word_t)1 << BIT_OFFSET(n));
}

void clear_bit(word_t *words, int n) {
  words[WORD_OFFSET(n)] &= ~((word_t)1 << BIT_OFFSET(n));
}

int get_bit(word_t *words, int n) {
  word_t bit = words[WORD_OFFSET(n)] & ((word_t)1 << BIT_OFFSET(n));
  return bit != 0;
}

bm *init(uint32_t s) {
  bm *bim = calloc(1, sizeof(bm));
  bim->bmp = calloc(s, sizeof(word_t));
  bim->size = s;
  return bim;
}

uint32_t calc(uint32_t i) {
  return (((i) + (BITS_PER_WORD)-1) / (BITS_PER_WORD));
}

int mrealloc (bm *b, int bits) {
  int more = calc(bits);
  uint32_t *t = realloc (b->bmp, more * sizeof(word_t));
  memset (t + b->size, 0, (more - b->size) * sizeof(word_t));
  b->bmp = t;
  b->size = more;
}

int main(){
  bm *b = init(1);
  uint32_t i = 1, val = 0, cnt = 0;
  for (i = 1; i < 1000; i++) {
    val = i;
    uint32_t bytes = calc(val);
    if(bytes <= b->size) {
      if(!get_bit(b->bmp, val))
        set_bit(b->bmp, val);
    }else{
      mrealloc(b, val);
      set_bit(b->bmp, val);
    }
  }
  printf("val=%d\n",val);

  for (uint32_t j=0; j < b->size; j++)
    cnt+=__builtin_popcount(b->bmp[j]);
  printf("total bits set=%d\n",cnt);

  free (b->bmp);
  free (b);

  return 0;
}

1 Ответ

3 голосов
/ 26 марта 2020

Попытка выхода за пределы индекса - и код не проверяет индекс. 

mrealloc(b, val);
set_bit(b->bmp, val);  // 1 passed end

Я думаю, что OP хотел 

mrealloc(b, val);
set_bit(b->bmp, val-1);
...