arena allocator
1.0.0
Alokasi arena single-header. C89 kompatibel.
arena.h Alokasi Arena adalah cara sederhana untuk mencapai manajemen memori dinamis yang lebih mudah, lebih cepat, dan lebih aman dengan memungkinkan beberapa alokasi dibebaskan sebagai kelompok. Ini dilakukan dengan mengalokasikan memori di daerah besar dan kemudian mendistribusikan bagian -bagian dari memori itu sesuai kebutuhan, mengurangi jumlah panggilan malloc (yang lambat dibandingkan dengan aritmatika pointer sederhana).
Saat Anda menghancurkan arena, Anda juga membebaskannya dan semua isinya, mengurangi jumlah panggilan free yang juga lambat. Lebih jauh, Anda dapat menghapus arena hanya dengan mengatur ulang pointer memori mereka ke 0 , memungkinkan Anda untuk menggunakan kembali mereka dan menghilangkan kebutuhan akan lebih banyak malloc dan free .
Anda dapat mempelajari lebih lanjut tentang alokasi arena/zona/wilayah dengan membaca artikel yang fantastis ini.
Saya akan membuat ini singkat. Saya mempertahankan kepatuhan C89 untuk bersenang -senang, bukan karena saya menggunakannya. Saya pribadi adalah penikmat C11. Jika Anda berpikir C89 adalah satu -satunya cara, yah, bagus untuk Anda! Tapi kamu salah.
Setiap kali saya membagikan proyek ini dengan programmer lain, salah satu tanggapan paling umum yang saya terima adalah sesuatu di sepanjang baris: Anda tidak boleh memasukkan kode implementasi/logika dalam file header! Saya mengambil masalah dengan pernyataan ini karena tiga alasan ...
Ini menunjukkan bahwa konsekuensi yang sudah ketinggalan zaman dan, konsekuensi, konstruksi berbahaya masih ditegakkan dalam sistem pendidikan, yang merupakan di mana konstruk tersebut biasanya diperkenalkan.
Sangat jarang orang yang membuat pernyataan ini memiliki alasan aktual untuk mempercayainya. Apakah orang ini pernah memikirkan mengapa mereka "tidak pernah memasukkan kode implementasi/logika ke dalam file header"? Cukup memuntahkan apa yang telah mereka dengar tanpa dasar mengapa mereka memilih untuk setuju dengan itu tidak membantu saya dengan cara apa pun, dan orang ini seharusnya tidak mengharapkan saya hanya menerimanya seperti yang telah mereka lakukan.
Kritik terbesar dan paling valid dari perpustakaan header-only/header adalah bahwa perubahan ke header memerlukan kompilasi ulang semua file yang memasukkannya. Dalam kasus proyek saya, membuat perubahan pada arena.h , meskipun implementasi aktual hanya terkandung dalam unit terjemahan yang #define dari makro ARENA_IMPLEMENTATION , akan menghasilkan pembangunan kembali semua file yang memasukkannya. Solusinya? Setelah arena.h berada dalam keadaan yang diinginkan, berhentilah membuat perubahan!
Tautan lamban dan rumit. Banyak pemula sering kali berjuang untuk mempelajari proses penghubung, dan mereka juga merupakan penyebab terbesar dalam hal menulis kode yang tidak aman. Ini saja adalah alasan yang cukup bagi saya untuk menjadikan pengalokasi arena ini sebagai perpustakaan header saja. Kode saya (dalam keadaan saat ini) sangat kecil, sekitar 300 baris. Mengapa saya membuat Anda membangun dan menautkan implementasi sekecil itu ketika Anda bisa #include sekali dan mulai menggunakannya di luar kotak? Jika Anda benar-benar memiliki masalah dengan itu, pengalokasi ini dalam format header tunggal tidak mencegah Anda mengikuti konstruksi sumber+header jika Anda menginginkannya. Heck, jangan ragu untuk jaring dan menjadikannya sumber+header, ini open source karena suatu alasan!
Ini tidak mengimplementasikan alokasi tingkat kernel, tetapi sebaliknya membungkus malloc dan free (pustaka standar atau kustom, pilihan Anda).
Meskipun saya percaya perangkat lunak harus open source, saya tidak percaya akan etis untuk meminta perangkat lunak yang menggunakan pustaka ini juga menjadi open source. Di era teknologi modern dan keadaan dunia saat ini, menulis kode yang aman lebih penting dari sebelumnya. Untuk alasan ini, perangkat lunak ini dilisensikan di bawah Lisensi Apache versi 2.0. Anda sangat dianjurkan untuk membaca LICENSE (termasuk di bawah ini, di arena.h , dan file sendiri dalam repo ini) jika Anda mempertimbangkan untuk menggunakan perangkat lunak, kecuali jika Anda yakin Anda 100% akrab dengan syarat dan ketentuan.
Apache License
Version 2.0, January 2004
http://www.apache.org/licenses/
TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
1. Definitions.
"License" shall mean the terms and conditions for use, reproduction,
and distribution as defined by Sections 1 through 9 of this document.
"Licensor" shall mean the copyright owner or entity authorized by
the copyright owner that is granting the License.
"Legal Entity" shall mean the union of the acting entity and all
other entities that control, are controlled by, or are under common
control with that entity. For the purposes of this definition,
"control" means (i) the power, direct or indirect, to cause the
direction or management of such entity, whether by contract or
otherwise, or (ii) ownership of fifty percent (50%) or more of the
outstanding shares, or (iii) beneficial ownership of such entity.
"You" (or "Your") shall mean an individual or Legal Entity
exercising permissions granted by this License.
"Source" form shall mean the preferred form for making modifications,
including but not limited to software source code, documentation
source, and configuration files.
"Object" form shall mean any form resulting from mechanical
transformation or translation of a Source form, including but
not limited to compiled object code, generated documentation,
and conversions to other media types.
"Work" shall mean the work of authorship, whether in Source or
Object form, made available under the License, as indicated by a
copyright notice that is included in or attached to the work
(an example is provided in the Appendix below).
"Derivative Works" shall mean any work, whether in Source or Object
form, that is based on (or derived from) the Work and for which the
editorial revisions, annotations, elaborations, or other modifications
represent, as a whole, an original work of authorship. For the purposes
of this License, Derivative Works shall not include works that remain
separable from, or merely link (or bind by name) to the interfaces of,
the Work and Derivative Works thereof.
"Contribution" shall mean any work of authorship, including
the original version of the Work and any modifications or additions
to that Work or Derivative Works thereof, that is intentionally
submitted to Licensor for inclusion in the Work by the copyright owner
or by an individual or Legal Entity authorized to submit on behalf of
the copyright owner. For the purposes of this definition, "submitted"
means any form of electronic, verbal, or written communication sent
to the Licensor or its representatives, including but not limited to
communication on electronic mailing lists, source code control systems,
and issue tracking systems that are managed by, or on behalf of, the
Licensor for the purpose of discussing and improving the Work, but
excluding communication that is conspicuously marked or otherwise
designated in writing by the copyright owner as "Not a Contribution."
"Contributor" shall mean Licensor and any individual or Legal Entity
on behalf of whom a Contribution has been received by Licensor and
subsequently incorporated within the Work.
2. Grant of Copyright License. Subject to the terms and conditions of
this License, each Contributor hereby grants to You a perpetual,
worldwide, non-exclusive, no-charge, royalty-free, irrevocable
copyright license to reproduce, prepare Derivative Works of,
publicly display, publicly perform, sublicense, and distribute the
Work and such Derivative Works in Source or Object form.
3. Grant of Patent License. Subject to the terms and conditions of
this License, each Contributor hereby grants to You a perpetual,
worldwide, non-exclusive, no-charge, royalty-free, irrevocable
(except as stated in this section) patent license to make, have made,
use, offer to sell, sell, import, and otherwise transfer the Work,
where such license applies only to those patent claims licensable
by such Contributor that are necessarily infringed by their
Contribution(s) alone or by combination of their Contribution(s)
with the Work to which such Contribution(s) was submitted. If You
institute patent litigation against any entity (including a
cross-claim or counterclaim in a lawsuit) alleging that the Work
or a Contribution incorporated within the Work constitutes direct
or contributory patent infringement, then any patent licenses
granted to You under this License for that Work shall terminate
as of the date such litigation is filed.
4. Redistribution. You may reproduce and distribute copies of the
Work or Derivative Works thereof in any medium, with or without
modifications, and in Source or Object form, provided that You
meet the following conditions:
(a) You must give any other recipients of the Work or
Derivative Works a copy of this License; and
(b) You must cause any modified files to carry prominent notices
stating that You changed the files; and
(c) You must retain, in the Source form of any Derivative Works
that You distribute, all copyright, patent, trademark, and
attribution notices from the Source form of the Work,
excluding those notices that do not pertain to any part of
the Derivative Works; and
(d) If the Work includes a "NOTICE" text file as part of its
distribution, then any Derivative Works that You distribute must
include a readable copy of the attribution notices contained
within such NOTICE file, excluding those notices that do not
pertain to any part of the Derivative Works, in at least one
of the following places: within a NOTICE text file distributed
as part of the Derivative Works; within the Source form or
documentation, if provided along with the Derivative Works; or,
within a display generated by the Derivative Works, if and
wherever such third-party notices normally appear. The contents
of the NOTICE file are for informational purposes only and
do not modify the License. You may add Your own attribution
notices within Derivative Works that You distribute, alongside
or as an addendum to the NOTICE text from the Work, provided
that such additional attribution notices cannot be construed
as modifying the License.
You may add Your own copyright statement to Your modifications and
may provide additional or different license terms and conditions
for use, reproduction, or distribution of Your modifications, or
for any such Derivative Works as a whole, provided Your use,
reproduction, and distribution of the Work otherwise complies with
the conditions stated in this License.
5. Submission of Contributions. Unless You explicitly state otherwise,
any Contribution intentionally submitted for inclusion in the Work
by You to the Licensor shall be under the terms and conditions of
this License, without any additional terms or conditions.
Notwithstanding the above, nothing herein shall supersede or modify
the terms of any separate license agreement you may have executed
with Licensor regarding such Contributions.
6. Trademarks. This License does not grant permission to use the trade
names, trademarks, service marks, or product names of the Licensor,
except as required for reasonable and customary use in describing the
origin of the Work and reproducing the content of the NOTICE file.
7. Disclaimer of Warranty. Unless required by applicable law or
agreed to in writing, Licensor provides the Work (and each
Contributor provides its Contributions) on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied, including, without limitation, any warranties or conditions
of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
PARTICULAR PURPOSE. You are solely responsible for determining the
appropriateness of using or redistributing the Work and assume any
risks associated with Your exercise of permissions under this License.
8. Limitation of Liability. In no event and under no legal theory,
whether in tort (including negligence), contract, or otherwise,
unless required by applicable law (such as deliberate and grossly
negligent acts) or agreed to in writing, shall any Contributor be
liable to You for damages, including any direct, indirect, special,
incidental, or consequential damages of any character arising as a
result of this License or out of the use or inability to use the
Work (including but not limited to damages for loss of goodwill,
work stoppage, computer failure or malfunction, or any and all
other commercial damages or losses), even if such Contributor
has been advised of the possibility of such damages.
9. Accepting Warranty or Additional Liability. While redistributing
the Work or Derivative Works thereof, You may choose to offer,
and charge a fee for, acceptance of support, warranty, indemnity,
or other liability obligations and/or rights consistent with this
License. However, in accepting such obligations, You may act only
on Your own behalf and on Your sole responsibility, not on behalf
of any other Contributor, and only if You agree to indemnify,
defend, and hold each Contributor harmless for any liability
incurred by, or claims asserted against, such Contributor by reason
of your accepting any such warranty or additional liability.
END OF TERMS AND CONDITIONS
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
Copyright 2024 Carter Dugan
Dokumentasi untuk Allocator Arena semuanya dapat ditemukan di arena.h . Ada komentar di bagian atas file header dengan instruksi cepat untuk penggunaan untuk kenyamanan Anda.
Untuk satu file di satu unit terjemahan , Anda membutuhkan yang berikut:
#define ARENA_IMPLEMENTATION
#include "arena.h" Sejak saat itu, file lain di unit terjemahan lain dapat dengan mudah #include "arena.h" secara normal. Ada makro tambahan yang dapat Anda definisikan/gunakan. Lihat bagian fungsi dan makro.
Ada dua struct yang didefinisikan dalam arena.h . Ini mencantumkan masing -masing bersama dengan anggotanya.
Arena_Allocation struktur data untuk alokasi arena. Hanya tersedia saat ARENA_DEBUG didefinisikan.
size_t index indeks di arena di mana awal alokasi berada.size_t size ukuran memori yang dialokasikan untuk alokasi ini dalam byte.char *pointer pointer yang terkait untuk alokasi.struct Arena_Allocation_s *next alokasi berikutnya dalam daftar tertaut. Arena struktur data untuk arena.
char *region wilayah memori yang dialokasikan.size_t index indeks wilayah untuk penunjuk berikutnya yang akan didistribusikan.size_t size ukuran memori yang dialokasikan ke arena dalam byte.unsigned long allocations jumlah alokasi arena yang telah dibuat. Hanya tersedia saat ARENA_DEBUG didefinisikan.Arena_Allocation *head_allocation alokasi pertama yang dibuat di arena (digunakan untuk daftar tertaut). Hanya tersedia saat ARENA_DEBUG didefinisikan. /*
Allocate and return a pointer to memory to the arena
with a region with the specified size. Providing a
size of zero results in a failure.
Parameters:
size_t size | The size (in bytes) of the arena
memory region.
Return:
Pointer to arena on success, NULL on failure
*/
Arena * arena_create ( size_t size );
/*
Return a pointer to a portion of specified size of the
specified arena's region. Nothing will restrict you
from allocating more memory than you specified, so be
mindful of your memory (as you should anyways) or you
will get some hard-to-track bugs. By default, memory is
aligned by alignof(size_t), but you can change this by
#defining ARENA_DEFAULT_ALIGNMENT before #include'ing
arena.h. Providing a size of zero results in a failure.
Parameters:
Arena *arena | The arena of which the pointer
from the region will be
distributed
size_t size | The size (in bytes) of
allocated memory planned to be
used.
Return:
Pointer to arena region segment on success, NULL on
failure.
*/
ARENA_INLINE void * arena_alloc ( Arena * arena , size_t size );
/*
Same as arena_alloc, except you can specify a memory
alignment for allocations.
Return a pointer to a portion of specified size of the
specified arena's region. Nothing will restrict you
from allocating more memory than you specified, so be
mindful of your memory (as you should anyways) or you
will get some hard-to-track bugs. Providing a size of
zero results in a failure.
Parameters:
Arena *arena | The arena of which the pointer
from the region will be
distributed
size_t size | The size (in bytes) of
allocated memory planned to be
used.
unsigned int alignment | Alignment (in bytes) for each
memory allocation.
Return:
Pointer to arena region segment on success, NULL on
failure.
*/
void * arena_alloc_aligned ( Arena * arena , size_t size , unsigned int alignment );
/*
Copy the memory contents of one arena to another.
Parameters:
Arena *src | The arena being copied, the source.
Arena *dest | The arena being copied to. Must be created/allocated
already.
Return:
Number of bytes copied.
*/
ARENA_INLINE size_t arena_copy ( Arena * dest , Arena * src );
/*
Reset the pointer to the arena region to the beginning
of the allocation. Allows reuse of the memory without
realloc or frees.
Parameters:
Arena *arena | The arena to be cleared.
*/
ARENA_INLINE void arena_clear ( Arena * arena );
/*
Free the memory allocated for the entire arena region.
Parameters:
Arena *arena | The arena to be destroyed.
*/
ARENA_INLINE void arena_destroy ( Arena * arena );
/*
Returns a pointer to the allocation struct associated
with a pointer to a segment in the specified arena's
region.
Parameters:
Arena *arena | The arena whose region should
have a portion pointed to by
ptr.
void *ptr | The ptr being searched for
within the arena in order to
find an allocation struct
associated with it.
*/
Arena_Allocation * arena_get_allocation_struct ( Arena * arena , void * ptr );
/*
Adds an arena allocation to the arena's linked list of
allocations under debug.
Parameters:
Arena *arena | The arena whose allocation list
should be added to
size_t size | The size of the allocation being
added.
*/
void arena_add_allocation ( Arena * arena , size_t size );
/*
Deletes the arena's linked list of allocations under
debug.
Parameters:
Arena *arena | The arena whose allocation list
is being deleted.
*/
void arena_delete_allocation_list ( Arena * arena ); Dalam kode Anda, Anda dapat menentukan beberapa makro opsional. ARENA_MALLOC , ARENA_FREE dan ARENA_MEMCPY dapat ditugaskan ke fungsi seperti malloc , free -bebas, dan seperti memcpy , dan arena.h akan menggunakannya sebagai pengganti fungsi perpustakaan standar. Anda dapat mengakses fungsionalitas debug tambahan untuk melacak alokasi dengan mendefinisikan ARENA_DEBUG . Akhirnya, Anda juga dapat menentukan nilai default untuk penyelarasan alokasi dengan mendefinisikan nilai untuk ARENA_DEFAULT_ALIGNMENT . Lihat di bawah untuk contoh.
// All of these are optional
// Replace standard library functions
#define ARENA_MALLOC <stdlib_malloc_like_allocator>
#define ARENA_FREE <stdlib_free_like_deallocator>
#define ARENA_MEMCPY <stdlib_memcpy_like_copier>
// for debug functionality:
#define ARENA_DEBUG
// If you would like to change the default alignment for
// allocations:
#define ARENA_DEFAULT_ALIGNMENT <alignment_value> Ada juga makro untuk menentukan penyelarasan jenis. Seperti yang lainnya, ini juga ramah C89, meskipun ketika dikompilasi di bawah C11 akan menggunakan stdalign.h 's alignof .
ARENA_ALIGNOF ( type ) // Gives alignment of `type` Kode ini ditulis untuk dibangun dengan kompiler apa pun yang mendukung standar C89 dan berjalan di platform apa pun. Namun, ada beberapa masalah dengan membangun di jendela dengan Makefile . Harap baca semua informasi di bawah ini.
Tes dan contoh telah dikompilasi dan berhasil dijalankan di bawah kompiler dan versi berikut:
Tes dan contoh disusun dan berhasil dijalankan pada sistem operasi berikut:
Catatan Makefile saat ini belum dikonfigurasi untuk bekerja di Windows saat menjalankan $ make test karena penggunaan Valgrind dan absennya ekstensi .exe . Ini harus menjadi perbaikan sederhana dan ada di daftar TODO saya (jangan ragu untuk membuka masalah dan memperbaikinya sendiri!).
Proyek ini memiliki pedoman yang sangat sederhana untuk berkontribusi.
Untuk setiap kontribusi pada kode arena.h , buka permintaan tarik hanya jika Anda menangani masalah untuk memenuhi permintaan fitur atau memperbaiki bug . Ikuti gaya kode dan jalankan tes otomatis sebelum membuka permintaan tarik. Semua tes harus dilewati.
Untuk permintaan atau bug fitur, buka masalah . Anda kemudian dapat mengatasi masalah ini sendiri.
Untuk hal lain , buka masalah dan kami akan membahasnya.
arena.hSaat ini tidak ada dokumentasi untuk gaya kode, tetapi harus relatif cukup sederhana untuk diambil melalui membaca kode yang ada untuk sebagian besar hal. Jika Anda mengalami masalah, jangan ragu untuk membuka masalah untuk FR. Jika sudah ada, komentari itu menggambarkan apa yang Anda bingung.
Jika Anda memodifikasi arena.h apapun, Anda harus menjalankan tes. Lihat bagian selanjutnya.
Jika Anda menambahkan fitur di dalam arena.h , Anda harus membuat tes atau tes yang memadai dalam test.c
Jika Anda menambahkan fitur di dalam arena.h , Anda harus contoh yang memadai dalam code_examples/ dan menambahkannya ke makefile , tetapi itu tidak diperlukan.
Jika Anda mengubah arena.h apapun, jalankan tes sebelum membuka PR . Jika Anda membuka PR dengan modifikasi pada kode dan tes tidak semua lulus, buat komentar pada PR Anda yang menyatakan tes mana yang Anda yakini salah dan mencegah Anda lulus semua tes. Jika ada tes yang gagal dan PR Anda tidak memiliki komentar yang mengklaim untuk memperbaiki tes yang gagal, PR Anda akan diabaikan ditutup.
Di luar mengatasi bug dan permintaan fitur, memenuhi permintaan fitur atau perbaikan bug untuk fungsionalitas di dalam arena.h memungkinkan memodifikasi atau menambahkan kode pengujian yang relevan dalam test.c , dan Anda harus melakukannya jika Anda ingin PR Anda diakui. Ada dokumentasi untuk menguji kode dalam test.c di bagian atas file dalam bentuk komentar.
Tes juga harus melewati Valgrind bebas bocor, dan arena.h harus sesuai dengan C89. Anda harus memeriksa ini menggunakan Makefile , tetapi jika karena alasan tertentu Anda tidak dapat atau tidak mau, kompilasi test.c
-Werror -Wall -Wextra -Wstrict-prototypes -Wold-style-definition -Wmissing-prototypes -Wmissing-declarations -Wdeclaration-after-statement
Dan untuk kepatuhan, kompilasi test_compliance.c dengan
-pedantic -std=c89 -Werror -Wall -Wextra -Wstrict-prototypes -Wold-style-definition -Wmissing-prototypes -Wmissing-declarations -Wdeclaration-after-statement
Seperti yang saya katakan, Anda dapat melakukan semua ini dengan Makefile
$ make test
Pengidentifikasi
variable_name . Untuk petunjuk , tanda bintang ( * ) harus dilampirkan pada nama variabel, bukan tipe, misalnya type *variable_name .type function_name(p1, p2, ...) . Dalam kasus pointer, tanda bintang ( * ) harus dilampirkan pada tipe untuk kepadatan, misalnya type* function_name(p1, p2, ...) . Fungsi harus memiliki deklarasi ke depan dengan komentar untuk dokumentasi di atasnya di sekitar file, pastikan pesanan relatif terhadap fungsi lain konsisten.struct StructName . Mereka harus diketik dan terletak di sekitar bagian atas file header.ARENA_ , misalnya ARENA_MACRO_NAME . Tolong hindari menambahkan makro tanpa berkonsultasi dengan saya terlebih dahulu . Jangan ragu untuk membuat perubahan pada makro yang ada.Ruang putih didasarkan pada relevansi baris kode dengan orang -orang di sekitarnya. Jika Anda tidak mengerti apa arti poin -poin ini, silakan lihat kodenya. Itu harus diformat sebagai berikut:
Pemeriksaan kesalahan harus dilakukan jika memungkinkan dan meniru perilaku implementasi perpustakaan standar, seperti mengembalikan NULL pada kesalahan dalam fungsi yang mengembalikan pointer atau mengembalikan nilai kesalahan integer dari fungsi integer. Anda harus menggunakan pemeriksaan kesalahan awal , yang berarti memeriksa kesalahan segera setelah dapat diproduksi, misalnya. Memeriksa NULL yang dikembalikan setelah panggilan malloc yang gagal.
Komentar harus menjelaskan mengapa Anda melakukan sesuatu, bukan apa yang Anda lakukan. Dengan kata lain, kode Anda harus jelas. Dokumentasi untuk fungsi dalam bentuk komentar harus ditempatkan di atas fungsi dalam format berikut:
/*
Description of function, description of function description of function.
Description of function description of function, description of function
description of function.
Parameters:
paramter1_type paramter1_name | Description of parameter 1, description
of parameter one description of paramter
1.
paramter2_type paramter2_name | Description of parameter 2, description
of parameter one description of paramter
2.
Return:
Description of return value, description of return value description of return value.
*/
