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/cpool.h>
15#include <assert.h>
16#include <errno.h>
17
18void
19cpool_init(cpool_t *p, uint32_t start, uint32_t end)
20{
21    assert(p);
22    p->start = start;
23    p->end = end;
24    p->mx = start;
25    cvector_init(&p->freelist);
26}
27
28void
29cpool_release(cpool_t *p) {
30    if (!p) {
31        return;
32    }
33    cvector_free(&p->freelist);
34    cpool_init(p, 0, 0);
35}
36
37uint32_t
38cpool_alloc(cpool_t *p)
39{
40    assert(p);
41
42    // First try to allocate from the free list.
43    size_t fSz = cvector_count(&p->freelist);
44    if (fSz > 0) {
45        // Allocate the last item available on the free list.
46        cvector_item_t obj = cvector_get(&p->freelist, fSz - 1);
47        cvector_delete(&p->freelist, fSz - 1);
48        return (uint32_t) obj;
49    }
50
51    // Free list exhausted, allocate by increasing max obj ID..
52    if (p->mx <= p->end) {
53        return (uint32_t) p->mx++;
54    }
55
56    // Out of object to allocate.
57    return 0;
58}
59
60void
61cpool_free(cpool_t *p, uint32_t obj)
62{
63    assert(p);
64    if (obj < p->start || obj > p->end || obj >= p->mx) {
65        return;
66    }
67    if (obj == p->mx) {
68        // Decrease max obj ID.
69        // Note that this implementation doesn't decrease mx for all cases;
70        // decreasing mx properly would require a periodic sort of the freelist,
71        // and a O(n) loop from the end. Doesn't save _that_ much memory.
72        p->mx = (obj - 1);
73        return;
74    }
75    // Add to free list.
76    cvector_add(&p->freelist, (cvector_item_t)obj);
77}
78
79bool cpool_check(cpool_t *p, uint32_t obj) {
80    if (obj < p->start || obj > p->end) {
81        // Not free if out of range.
82        return false;
83    }
84    if (obj > p->mx) {
85        // Free if in the not-allocated-yet range.
86        return true;
87    }
88    size_t sz = cvector_count(&p->freelist);
89    for (int i = 0; i < sz; i++) {
90        uint32_t x = (uint32_t)cvector_get(&p->freelist, i);
91        if (x == obj) {
92            return true;
93        }
94    }
95    return false;
96}
97