c - 如何在 C 中正确重新分配位数组
问题描述
随着输入更多值,我正在尝试动态增长位数组。到目前为止,我有两个问题。我 gdb 进入了它,但在重新分配位数组时我真的看不到我缺少什么部分,这是我看到的问题:
- Valgrind 报告了几个无效的读/写
- 总位数是 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;
}
解决方案
超出索引范围的尝试 - 并且代码不检查索引。
mrealloc(b, val);
set_bit(b->bmp, val); // 1 passed end
我认为OP想要
mrealloc(b, val);
set_bit(b->bmp, val-1);
推荐阅读
- reactjs - 如何在隐藏文件时导入文件,而不将它们添加到本地目录?
- spring-boot - 使用 HTML5 视频播放器进行视频流式传输
- javascript - 如何使用正则表达式替换功能一次替换多个东西?可能吗?尝试学习正则表达式
- php - 注意:未定义的变量,但我已经定义了它
- docker - 我的 Dockerfile 哪里出了问题?
- python - django migrate ModuleNotFoundError 的含义
- optimization - 使用 Pyomo Bilevel 解决 maxmin 问题
- reactjs - Reactjs Portal 容器重新渲染
- swift - 如何将 UIPicker 的选择推送到 Firebase
- php - PHP:从 txt 文件中列出的 url 列表中抓取电子邮件