leetcode/lcBitmap.h at master · ChaserTlss/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#ifndef __BITMAP__H_
#define __BITMAP__H_

#include <stdlib.h>
#include <string.h>

#define DIV_ROUND_UP(a, b) ((a + b - 1) / b)
typedef unsigned int bitmap_t;
#define __BITMAP_BITW__ (sizeof(bitmap_t) * 8)

struct bitmap {
	size_t elementCount;
	bitmap_t buffer[0];
};

static inline size_t sizeBitmap(struct bitmap *bitmap)
{
	return DIV_ROUND_UP(bitmap->elementCount, __BITMAP_BITW__) * sizeof(bitmap->buffer[0]);
}

static inline void setAllBitmap(struct bitmap *bitmap, bool v)
{
	memset(bitmap->buffer, v?0xff:0, sizeBitmap(bitmap));
}

static inline struct bitmap *newBitmap(size_t elementCount)
{
	struct bitmap *bitmap = malloc(sizeof(struct bitmap)
			+ DIV_ROUND_UP(elementCount, __BITMAP_BITW__) * sizeof(bitmap->buffer[0]));

	if (!bitmap)
		return bitmap;

	bitmap->elementCount = elementCount;
	return bitmap;
}

static inline void setBitmap(struct bitmap *bitmap, size_t index)
{
	if (index > bitmap->elementCount)
		return;

	bitmap->buffer[index/__BITMAP_BITW__] |= (bitmap_t)1 << (index%__BITMAP_BITW__);
}

static inline bool getBitmap(struct bitmap *bitmap, size_t index)
{
	if (index > bitmap->elementCount)
		return false;

	return bitmap->buffer[index/__BITMAP_BITW__] & (bitmap_t)1 << (index%__BITMAP_BITW__);
}

static inline ssize_t ffsBitmap(struct bitmap *bitmap)
{
	int i = 0;
	for (i = 0; i < DIV_ROUND_UP(bitmap->elementCount, __BITMAP_BITW__); i++) {
		if (bitmap->buffer[i])
			break;
	}

	if (i == DIV_ROUND_UP(bitmap->elementCount, __BITMAP_BITW__))
		return -1;

	size_t index = i * __BITMAP_BITW__ + ffs(bitmap->buffer[i]) - 1;

	if (index >= bitmap->elementCount)
		return -1;
	return index;
}

static inline void clearBitmap(struct bitmap *bitmap, size_t index)
{
	if (index > bitmap->elementCount)
		return;
	bitmap->buffer[index/__BITMAP_BITW__] &= ~((bitmap_t)1 << (index%__BITMAP_BITW__));
}

#endif