1

I got a problem with C programming.

Here is the Bitmap struct I defined:

typedef struct Bitmap {
    uint *bits;  uint n;    // 规模为n的向量，记录被标记的次序，存储的是标记位在栈stack中的秩
    uint *stack; uint top;  // 容量为n的栈，记录被标记各位秩的栈，以及栈顶指针
    void (*set)(struct Bitmap *map, uint i);    // 将i位标记为1
    bool (*test)(struct Bitmap *map, uint i);   // 判断i位是1还是0
    void (*clear)(struct Bitmap *map, uint i);  // 将i位标记为0
    void (*destroy)(struct Bitmap *map);
} Bitmap;

I an trying to write algorithm of finding all subset using Bitmap, this is the recursive procedure I wrote:

static Bitmap *bitmap;
void subset_using_bitmap(void *arr, uint cur, uint n, enum Types type) {
    if (!bitmap)
        bitmap = getAnBitmap(n);
    if (cur == n) {
        for (uint i = 0; i < cur; ++i)
            if (bitmap->test(bitmap, i))
                print(arr + i, type);
        printf("\n");
        return;
    }

    bitmap->set(bitmap, cur);
    subset_using_bitmap(arr, cur + 1, n, type);
    bitmap->clear(bitmap, cur);
    subset_using_bitmap(arr, cur + 1, n, type);
}

And, below is the getAnBitmap method:

Bitmap *getAnBitmap(uint n) {
    Bitmap map = {
        .bits = (uint *)malloc(sizeof(uint) * n),
        .n = n,
        .stack = (uint *)malloc(sizeof(uint) * n),
        .top = 0,
        .set = set,
        .test = test,
        .clear = clear,
        .destroy = destroy,
    };
    struct Bitmap *bitmap = &map;
    return bitmap;
}

Finally, below is my problem: set() method:

static inline void set(Bitmap *map, uint i) {
    map->stack[map->top] = i;
    map->bits[i] = map->top;
    ++map->top;
}

when the program subset_using_bitmap enter into bitmap->set(bitmap, cur) secondly, the addresses of variables such as *bits, *stack, and the contents of in program become illegal, for example, in my CLion, first *stack is 0x382f08, then second *stack become 0x1, obviously illegal. Does the Inline keyword cause this? Hope expert can help us, Thanks very much!^_^

Jingkun Zhang
  • 11
  • 1
  • Thank you, but it doesn't work. I think this statement is legal, because the content of pointer map does not change. – Jingkun Zhang Jan 06 '20 at 03:33
  • Can you please provide a [minimal verifiable example](https://stackoverflow.com/help/minimal-reproducible-example)? – kaylum Jan 06 '20 at 03:34
  • 1
    `struct Bitmap *bitmap = &map; return bitmap;` Can't do that because `map` is local to the function. Its address and contents are invalid as soon as the function exits. Accessing such pointers is undefined behaviour. – kaylum Jan 06 '20 at 03:35
  • Thank you, the statement `struct Bitmap *bitmap = &map; return bitmap;` works correctly, which means I can get the pointer variable `map` in method `subset_using_bitmap`. When I am debugging the program, the value of pointer variable `map` parameter of `set` method does not change. – Jingkun Zhang Jan 06 '20 at 04:53
  • Thank you very much, I think the [Can a local variable's memory be accessed outside its scope?](https://stackoverflow.com/questions/6441218/can-a-local-variables-memory-be-accessed-outside-its-scope) can solve my problem. – Jingkun Zhang Jan 06 '20 at 05:04

0 Answers0