# test

:::danger
請依據給定格式，重新編撰內容
:notes: jserv
:::

## 7-1
Q1

static inline size_t find_next_bit(const unsigned long *bitmap,
                                   size_t bits,
                                   size_t start)
{
    unsigned long t;
    size_t l = BITS_TO_LONGS(bits);
    size_t first_long = start / BITS_PER_LONG;
    size_t long_lower = start - (start % BITS_PER_LONG);

    if (start >= bits)
        return bits;

    t = bitmap[first_long] & BITMAP_FIRST_WORD_MASK(start);
    for (size_t i = first_long + 1; !t && i < l; i++) {
        long_lower += BITS_PER_LONG;
        t = bitmap[i];
    }
    
    if (!t)
        return bits;

    size_t pos = long_lower + bitops_ffs(t) - 1;;
    if (pos >= bits)
        return bits;
    return pos;
}

Q2

static inline void bitmap_random(unsigned long *bitmap, size_t bits) {
    size_t l = BITS_TO_LONGS(bits);
    if (l > 1)
        memset(bitmap, rand(), (l - 1) * sizeof(unsigned long));
    bitmap[l - 1] = (rand() >> (-(bits) % BITS_PER_LONG));
}

int main(void) {
    for (int i = 1; i < MAX_TEST_BITS; i++) {
        bitmap_fill(test, i);
        assert(find_next_bit(test, i, 0) == 0);
        bitmap_zero(test, i);
        assert(find_next_bit(test, i, 0) == i);
        bitmap_random(test,i);
    }
    return 0;
}

Q3 and Q4

static inline size_t bitops_ffs(unsigned long x) {
    for(size_t i=0 ; i < 64 ;i++){
      if(x&0x01 == 1) break
      x >>= 1
    }
    if(i == 63) return 0;
    return i+1
}

## 7-2
Q1

reference counting 的運作機制是 每一個物件身上都會有一個 counter，當一個 reference 被創造之後，reference count 就會增加，當 reference count 為 0 時就會被視為 garbage 被回收掉。

實做 mark and sweep

mark phase: 把所有有用到的object+上一個mark bit 並設為 1 ，且遞迴的把每一個 object 中的物件的指標指到的物件也設為 1 ，
sweep phase: 把每一垃圾 object mark bit 設為零，並遞迴的把每一個垃圾 object mark bit 設為零 且 把指標反轉。

最後把 sweep 的記憶體位置合併起來，一起釋放掉。

Q2

char *strdup(const char *s) {
    size_t size = strlen(s) + 1;
    char *p = gc_malloc(size);
    if (p) {
        memcpy(p, s, size);
    }
    return p;
}