1/*
2 * Copyright 2016, Data61
3 * Commonwealth Scientific and Industrial Research Organisation (CSIRO)
4 * ABN 41 687 119 230.
5 *
6 * This software may be distributed and modified according to the terms of
7 * the BSD 2-Clause license. Note that NO WARRANTY is provided.
8 * See "LICENSE_BSD2.txt" for details.
9 *
10 * @TAG(D61_BSD)
11 */
12
13#include <data_struct/cvector.h>
14#include <data_struct/cbpool.h>
15#include <stdlib.h>
16#include <string.h>
17#include <assert.h>
18#include <errno.h>
19
20void cbpool_init_static(cbpool_t *p, uint32_t size, char *buffer, int bufferSize) {
21    assert(p);
22    memset(p, 0, sizeof(cbpool_t));
23    p->size = size;
24    p->size_ntiles = (size / 32) + 1;
25    assert(p->size_ntiles  * sizeof(uint32_t) <= bufferSize);
26    p->bitmap = (uint32_t*) buffer;
27    assert(p->bitmap);
28    memset(p->bitmap, 0, p->size_ntiles * sizeof(uint32_t));
29}
30
31void cbpool_init(cbpool_t *p, uint32_t size) {
32    assert(p);
33    memset(p, 0, sizeof(cbpool_t));
34    p->size = size;
35    p->size_ntiles = (size / 32) + 1;
36    p->bitmap = kmalloc(p->size_ntiles * sizeof(uint32_t));
37    assert(p->bitmap);
38    memset(p->bitmap, 0, p->size_ntiles * sizeof(uint32_t));
39}
40
41void cbpool_release(cbpool_t *p) {
42    if (!p) return;
43    if (p->bitmap) {
44        kfree(p->bitmap);
45    }
46}
47
48uint32_t cbpool_alloc_internal(cbpool_t *p, uint32_t size, int st, int ed, int inc, bool lt) {
49    if (!size) {
50        return CBPOOL_INVALID;
51    }
52    uint32_t freesz = 0;
53    for (int i = st; (lt ? (i < ed) : (i >= ed)); i+=inc) {
54        if (!cbpool_check_single(p, i)) {
55            freesz++;
56            if (freesz >= size) {
57                uint32_t sta = i - (freesz - 1);
58                for (uint32_t j = sta; j <= i; j++) {
59                    cbpool_set_single(p, j, true);
60                }
61                return sta;
62            }
63        } else {
64            freesz = 0;
65        }
66    }
67    return CBPOOL_INVALID;
68}
69
70uint32_t cbpool_alloc(cbpool_t *p, uint32_t size) {
71    return cbpool_alloc_internal(p, size, 0, p->size, 1, true);
72}
73
74void cbpool_free(cbpool_t *p, uint32_t obj, uint32_t size) {
75    if (!size) {
76        return;
77    }
78    uint32_t end = obj + size;
79    if (end >= p->size) end = (p->size - 1);
80    for (int i = obj; i < end; i++) {
81        cbpool_set_single(p, i, false);
82    }
83}
84
85bool cbpool_check_single(cbpool_t *p, uint32_t obj) {
86    assert(p && p->bitmap);
87    uint32_t idx = obj / 32;
88    assert(idx < p->size_ntiles);
89    uint32_t b = p->bitmap[idx];
90    if (b & (1 << (obj % 32))) {
91        return true;
92    }
93    return false;
94}
95
96void cbpool_set_single(cbpool_t *p, uint32_t obj, bool val) {
97    assert(p && p->bitmap);
98    uint32_t idx = obj / 32;
99    assert(idx < p->size_ntiles);
100    if (val) {
101        p->bitmap[idx] |= (1 << (obj % 32));
102    } else {
103        p->bitmap[idx] &= ~(1 << (obj % 32));
104    }
105}
106
107