LF OS
Hobby operating system for amd64 with high ambitions
|
Go to the source code of this file.
Data Structures | |
struct | tpa_page_header |
Header of a tpa page. Data follows after this until &tpa_page_header+tpa->page_size. More... | |
struct | tpa |
Header of a TPA. More... | |
Functions | |
tpa_t * | tpa_new (allocator_t *alloc, uint64_t entry_size, uint64_t page_size, tpa_t *tpa) |
void | tpa_delete (tpa_t *tpa) |
size_t | tpa_size (tpa_t *tpa) |
size_t | tpa_entries_per_page (tpa_t *tpa) |
ssize_t | tpa_length (tpa_t *tpa) |
uint64_t | tpa_offset_in_page (tpa_t *tpa, uint64_t idx) |
uint64_t * | tpa_get_marker (tpa_t *tpa, struct tpa_page_header *page, uint64_t idx) |
bool | tpa_entry_exists_in_page (tpa_t *tpa, struct tpa_page_header *page, uint64_t idx) |
size_t | tpa_entries (tpa_t *tpa) |
struct tpa_page_header * | tpa_get_page_for_idx (tpa_t *tpa, uint64_t idx) |
void * | tpa_get (tpa_t *tpa, uint64_t idx) |
void | tpa_clean_page (tpa_t *tpa, struct tpa_page_header *page) |
void | tpa_set (tpa_t *tpa, uint64_t idx, void *data) |
size_t | tpa_next (tpa_t *tpa, size_t cur) |
This file and tpa.h are the implementation of a thin provisioned array, an array with unlimited size and holes for unused data.
There is a small data overhead (8 byte per entry, could be 4 byte on 32bit platforms. aligned) and quite some important runtime overhead (linked list to find the correct page, array access in page).
However, the implementation is simple and for many use cases this is a practical thing :)
You can look at /t/kernel/tpa.c for some examples.
License: MIT Author: Mara Sophie Grosch (littl.nosp@m.efox.nosp@m.@lf-n.nosp@m.et.o.nosp@m.rg)
Definition in file tpa.c.
struct tpa_page_header |
Header of a tpa page. Data follows after this until &tpa_page_header+tpa->page_size.
Data Fields | ||
---|---|---|
struct tpa_page_header * | next | Pointer to the next page. |
struct tpa_page_header * | prev | |
uint64_t | start_idx | First index in this page. |
struct tpa |
Data Fields | ||
---|---|---|
allocator_t * | allocator | Allocator for new tpa pages. |
uint64_t | entry_size | Size of each entry. |
struct tpa_page_header * | first | Pointer to the first data page. |
uint64_t | page_size | Size of each data page. |
void tpa_clean_page | ( | tpa_t * | tpa, |
struct tpa_page_header * | page | ||
) |
Definition at line 156 of file tpa.c.
References tpa::allocator, allocator::dealloc, tpa::first, tpa_page_header::next, tpa_page_header::prev, tpa_entries_per_page(), and tpa_entry_exists_in_page().
void tpa_delete | ( | tpa_t * | tpa | ) |
Deallocate every data in use by the given TPA And the TPA itself
tpa | The TPA to destroy |
Definition at line 61 of file tpa.c.
References tpa::allocator, allocator::dealloc, tpa::first, and tpa_page_header::next.
Counts the number of existing entries in the TPA
tpa | The TPA |
Definition at line 110 of file tpa.c.
References tpa::first, tpa_page_header::next, tpa_entries_per_page(), and tpa_entry_exists_in_page().
Definition at line 83 of file tpa.c.
References tpa::entry_size, and tpa::page_size.
bool tpa_entry_exists_in_page | ( | tpa_t * | tpa, |
struct tpa_page_header * | page, | ||
uint64_t | idx | ||
) |
Definition at line 106 of file tpa.c.
References tpa_get_marker().
Retrieve a given element from the TPA or NULL if the element is not present
tpa | The TPA |
idx | The index of the element to retrieve |
Definition at line 144 of file tpa.c.
References tpa_page_header::start_idx, tpa_entry_exists_in_page(), tpa_get_page_for_idx(), and tpa_offset_in_page().
uint64_t * tpa_get_marker | ( | tpa_t * | tpa, |
struct tpa_page_header * | page, | ||
uint64_t | idx | ||
) |
Definition at line 102 of file tpa.c.
References tpa_offset_in_page().
struct tpa_page_header * tpa_get_page_for_idx | ( | tpa_t * | tpa, |
uint64_t | idx | ||
) |
Definition at line 127 of file tpa.c.
References tpa::first, tpa_page_header::next, tpa_page_header::start_idx, and tpa_entries_per_page().
Retrieve the highest index currently possible without new allocation
tpa | The TPA |
Definition at line 87 of file tpa.c.
References tpa::first, tpa_page_header::next, tpa_page_header::start_idx, and tpa_entries_per_page().
tpa_t * tpa_new | ( | allocator_t * | alloc, |
uint64_t | entry_size, | ||
uint64_t | page_size, | ||
tpa_t * | tpa | ||
) |
Allocate and initialize a new Thin Provisioned Array
alloc | Allocator function to use |
dealloc | Deallocator function to use |
entry_size | Size of each entry |
page_size | Size of each data page |
tpa | Pointer to a memory region to use as tpa, 0 to alloc internally |
Definition at line 48 of file tpa.c.
References allocator::alloc, alloc, tpa::allocator, tpa::entry_size, tpa::first, and tpa::page_size.
Returns the next non-empty element after cur
tpa | The TPA |
cur | The current index |
Definition at line 223 of file tpa.c.
References tpa::first, tpa_page_header::next, tpa_page_header::start_idx, tpa_entries_per_page(), and tpa_get_marker().
Set new data at the given index
tpa | The TPA |
idx | Where to place the new entry |
data | Pointer to the first byte of the data to store |
Definition at line 174 of file tpa.c.
References allocator::alloc, tpa::allocator, tpa::entry_size, tpa::first, memcpy(), memset(), tpa_page_header::next, tpa::page_size, tpa_page_header::prev, tpa_page_header::start_idx, tpa_clean_page(), tpa_entries_per_page(), tpa_get_marker(), tpa_get_page_for_idx(), and tpa_offset_in_page().
Returns the allocated size of the TPA in bytes
Definition at line 72 of file tpa.c.
References tpa::first, tpa_page_header::next, and tpa::page_size.