如何在 C 中正确地重新分配一个位数组

Question

我正尝试在输入更多值时动态增加位数组。到目前为止我有两个问题。我 gdb 进入了它，但在重新分配位数组时我真的看不到我缺少的部分，这是我看到的问题：

Valgrind 报告几个无效 Reads/Writes
总位数是 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;
}

Answer 1

尝试超出索引范围 - 并且代码不检查索引。

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

我觉得 OP 想要

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

如何在 C 中正确地重新分配一个位数组

How to properly realloc a bit array in C

c

bitmap

bit

realloc

bitarray