From 2161797b19b068622a692628f352c78254d8a354 Mon Sep 17 00:00:00 2001 From: Nebula Moe Date: Mon, 24 Jul 2023 19:47:03 +0800 Subject: init --- .clang-format | 6 ++ .gitignore | 3 + LICENSE | 207 ++++++++++++++++++++++++++++++++++++++++++++++++++++ Makefile | 8 +++ README.md | 30 ++++++++ brainfuck.c | 212 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ crc32.c | 58 +++++++++++++++ crc32.h | 11 +++ helloworld.bf | 12 ++++ htable.c | 112 +++++++++++++++++++++++++++++ htable.h | 31 ++++++++ scripts/format.sh | 3 + 12 files changed, 693 insertions(+) create mode 100644 .clang-format create mode 100644 .gitignore create mode 100644 LICENSE create mode 100644 Makefile create mode 100644 README.md create mode 100644 brainfuck.c create mode 100644 crc32.c create mode 100644 crc32.h create mode 100644 helloworld.bf create mode 100644 htable.c create mode 100644 htable.h create mode 100755 scripts/format.sh diff --git a/.clang-format b/.clang-format new file mode 100644 index 0000000..6422547 --- /dev/null +++ b/.clang-format @@ -0,0 +1,6 @@ +BasedOnStyle: LLVM +IndentWidth: 4 +UseTab: Never +BreakBeforeBraces: Linux +AllowShortIfStatementsOnASingleLine: false +IndentCaseLabels: false diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..29f57a2 --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +brainfuck +bflisp.bf + diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..08b9123 --- /dev/null +++ b/LICENSE @@ -0,0 +1,207 @@ +Non-Profit Open Software License (“Non-Profit OSL”) 3.0 + +This Non-Profit Open Software License (“Non-Profit OSL”) version 3.0 +(the“License”) applies to any original work of authorship (the +“Original Work”) whose owner (the “Licensor”) has placed the following +licensing notice adjacent to the copyright notice for the Original +Work: + +Licensed under the Non-Profit Open Software License version 3.0 + +1. Grant of Copyright License. Licensor grants You a worldwide, +royalty-free, non-exclusive, sublicensable license, for the duration +of the copyright, to do the following: + + a. to reproduce the Original Work in copies, either alone or as part + of a collective work; + b. to translate, adapt, alter, transform, modify, or arrange the + Original Work, thereby creating derivative works (“Derivative Works”) + based upon the Original Work; + c. to distribute or communicate copies of the Original Work and + Derivative Works to the public, with the proviso that copies of + Original Work or Derivative Works that You distribute or communicate + shall be licensed under this Non-Profit Open Software License or as + provided in section 17(d); + d. to perform the Original Work publicly; and + e. to display the Original Work publicly. + +2. Grant of Patent License. Licensor grants You a worldwide, +royalty-free, non-exclusive, sublicensable license, under patent +claims owned or controlled by the Licensor that are embodied in the +Original Work as furnished by the Licensor, for the duration of the +patents, to make, use, sell, offer for sale, have made, and import the +Original Work and Derivative Works. + +3. Grant of Source Code License. The term “Source Code” means the +preferred form of the Original Work for making modifications to it and +all available documentation describing how to modify the Original +Work. Licensor agrees to provide a machine-readable copy of the Source +Code of the Original Work along with each copy of the Original Work +that Licensor distributes. Licensor reserves the right to satisfy this +obligation by placing a machine-readable copy of the Source Code in an +information repository reasonably calculated to permit inexpensive and +convenient access by You for as long as Licensor continues to +distribute the Original Work. + +4. Exclusions From License Grant. Neither the names of Licensor, nor +the names of any contributors to the Original Work, nor any of their +trademarks or service marks, may be used to endorse or promote +products derived from this Original Work without express prior +permission of the Licensor. Except as expressly stated herein, nothing +in this License grants any license to Licensor’s trademarks, +copyrights, patents, trade secrets or any other intellectual property. +No patent license is granted to make, use, sell, offer for sale, have +made, or import embodiments of any patent claims other than the +licensed claims defined in Section 2. No license is granted to the +trademarks of Licensor even if such marks are included in the Original +Work. Nothing in this License shall be interpreted to prohibit +Licensor from licensing under terms different from this License any +Original Work that Licensor otherwise would have a right to license. + +5. External Deployment. The term “External Deployment” means the use, +distribution, or communication of the Original Work or Derivative +Works in any way such that the Original Work or Derivative Works may +be used by anyone other than You, whether those works are distributed +or communicated to those persons or made available as an application +intended for use over a network. As an express condition for the +grants of license hereunder, You must treat any External Deployment by +You of the Original Work or a Derivative Work as a distribution under +section 1(c). + +6. Attribution Rights. You must retain, in the Source Code of any +Derivative Works that You create, all copyright, patent, or trademark +notices from the Source Code of the Original Work, as well as any +notices of licensing and any descriptive text identified therein as an +“Attribution Notice.” You must cause the Source Code for any +Derivative Works that You create to carry a prominent Attribution +Notice reasonably calculated to inform recipients that You have +modified the Original Work. + +7. Warranty of Provenance and Disclaimer of Warranty. The Original +Work is provided under this License on an “AS IS” BASIS and WITHOUT +WARRANTY, either express or implied, including, without limitation, +the warranties of non-infringement, merchantability or fitness for a +particular purpose. THE ENTIRE RISK AS TO THE QUALITY OF THE ORIGINAL +WORK IS WITH YOU. This DISCLAIMER OF WARRANTY constitutes an essential +part of this License. No license to the Original Work is granted by +this License except under this disclaimer. + +8. Limitation of Liability. Under no circumstances and under no legal +theory, whether in tort (including negligence), contract, or otherwise, +shall the Licensor be liable to anyone for any direct, indirect, +special, incidental, or consequential damages of any character arising +as a result of this License or the use of the Original Work including, +without limitation, damages for loss of goodwill, work stoppage, +computer failure or malfunction, or any and all other commercial +damages or losses. This limitation of liability shall not apply to the +extent applicable law prohibits such limitation. + +9. Acceptance and Termination. If, at any time, You expressly assented +to this License, that assent indicates your clear and irrevocable +acceptance of this License and all of its terms and conditions. If You +distribute or communicate copies of the Original Work or a Derivative +Work, You must make a reasonable effort under the circumstances to +obtain the express assent of recipients to the terms of this License. +This License conditions your rights to undertake the activities listed +in Section 1, including your right to create Derivative Works based +upon the Original Work, and doing so without honoring these terms and +conditions is prohibited by copyright law and international treaty. +Nothing in this License is intended to affect copyright exceptions and +limitations (including “fair use” or “fair dealing”). This License +shall terminate immediately and You may no longer exercise any of the +rights granted to You by this License upon your failure to honor the +conditions in Section 1(c). + +10. Termination for Patent Action. This License shall terminate +automatically and You may no longer exercise any of the rights granted +to You by this License as of the date You commence an action, +including a cross-claim or counterclaim, against Licensor or any +licensee alleging that the Original Work infringes a patent. This +termination provision shall not apply for an action alleging patent +infringement by combinations of the Original Work with other software +or hardware. + +11. Jurisdiction, Venue and Governing Law. Any action or suit relating +to this License may be brought only in the courts of a jurisdiction +wherein the Licensor resides or in which Licensor conducts its primary +business, and under the laws of that jurisdiction excluding its +conflict-of-law provisions. The application of the United Nations +Convention on Contracts for the International Sale of Goods is +expressly excluded. Any use of the Original Work outside the scope of +this License or after its termination shall be subject to the +requirements and penalties of copyright or patent law in the +appropriate jurisdiction. This section shall survive the termination +of this License. + +12. Attorneys’ Fees. In any action to enforce the terms of this +License or seeking damages relating thereto, the prevailing party +shall be entitled to recover its costs and expenses, including, +without limitation, reasonable attorneys’ fees and costs incurred in +connection with such action, including any appeal of such action. This +section shall survive the termination of this License. + +13. Miscellaneous. If any provision of this License is held to be +unenforceable, such provision shall be reformed only to the extent +necessary to make it enforceable. + +14. Definition of “You” in This License. “You” throughout this License, +whether in upper or lower case, means an individual or a legal entity +exercising rights under, and complying with all of the terms of, this +License. For legal entities, “You” includes any entity that controls, +is controlled by, or is under common control with you. For 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. + +15. Right to Use. You may use the Original Work in all ways not +otherwise restricted or conditioned by this License or by law, and +Licensor promises not to interfere with or be responsible for such +uses by You. + +16. Modification of This License. This License is Copyright © 2005 +Lawrence Rosen. Permission is granted to copy, distribute, or +communicate this License without modification. Nothing in this License +permits You to modify this License as applied to the Original Work or +to Derivative Works. However, You may modify the text of this License +and copy, distribute or communicate your modified version (the +“Modified License”) and apply it to other original works of authorship +subject to the following conditions: (i) You may not indicate in any +way that your Modified License is the “Open Software License” or “OSL” +and you may not use those names in the name of your Modified License; +(ii) You must replace the notice specified in the first paragraph +above with the notice“Licensed under ” or with a notice of your own +that is not confusingly similar to the notice in this License; and +(iii) You may not claim that your original works are open source +software unless your Modified License has been approved by Open Source +Initiative (OSI) and You comply with its license review and +certification process. + +17. Non-Profit Amendment. The name of this amended version of the Open +Software License (“OSL 3.0”) is “Non-Profit Open Software License 3.0” +. The original OSL 3.0 license has been amended as follows: + + a. Licensor represents and declares that it is a not-for-profit + organization that derives no revenue whatsoever from the distribution + of the Original Work or Derivative Works thereof, or from support or + services relating thereto. + b. The first sentence of Section 7 [“Warranty of Provenance”] of OSL + 3.0 has been stricken. For Original Works licensed under this + Non-Profit OSL 3.0, LICENSOR OFFERS NO WARRANTIES WHATSOEVER. + c. In the first sentence of Section 8 [“Limitation of Liability”] of + this Non-Profit OSL 3.0, the list of damages for which LIABILITY IS + LIMITED now includes “direct” damages. + d. The proviso in Section 1(c) of this License now refers to this + “Non-Profit Open Software License” rather than the “Open Software + License”. You may distribute or communicate the Original Work or + Derivative Works thereof under this Non-Profit OSL 3.0 license only if + You make the representation and declaration in paragraph (a) of this + Section 17. Otherwise, You shall distribute or communicate the + Original Work or Derivative Works thereof only under the OSL 3.0 + license and You shall publish clear licensing notices so stating. Also + by way of clarification, this License does not authorize You to + distribute or communicate works under this Non-Profit OSL 3.0 if You + received them under the original OSL 3.0 license. + e. Original Works licensed under this license shall reference + “Non-Profit OSL 3.0” in licensing notices to distinguish them from + works licensed under the original OSL 3.0 license. diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..4605125 --- /dev/null +++ b/Makefile @@ -0,0 +1,8 @@ +brainfuck: brainfuck.c htable.c crc32.c + gcc -O3 $^ -o $@ + +run: brainfuck + ./brainfuck helloworld.bf + +clean: + -rm brainfuck diff --git a/README.md b/README.md new file mode 100644 index 0000000..6c125e4 --- /dev/null +++ b/README.md @@ -0,0 +1,30 @@ +# brainfuck + +A brainfuck interpreter + +## Build + +``` +make +``` + +## Hello World + +``` +./brainfuck ./helloworld.bf +``` + +## Lisp! + +``` +wget https://raw.githubusercontent.com/shinh/bflisp/master/bflisp.bf +echo "(car (quote (a b c)))" | ./brainfuck bflisp.bf +``` + +WARNING: It's very slow, may takes ~10 minutes to run a `(car (quote (a b c)))`. + +## License + +You are free to copy, distribute and transmit this software for non-profit purposes under Non-Profit Open Software License 3.0. + +See LICENSE for details. \ No newline at end of file diff --git a/brainfuck.c b/brainfuck.c new file mode 100644 index 0000000..1579231 --- /dev/null +++ b/brainfuck.c @@ -0,0 +1,212 @@ +// Copyright (C) 2023 Dzshy . All Rights Reserved. +// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0. + +#include +#include +#include +#include + +#include +#include +#include + +#include "crc32.h" +#include "htable.h" + +#define LOGGER(s, ...) \ + do { \ + fprintf(stderr, s "\n", ##__VA_ARGS__); \ + } while (0) + +uint8_t *pbuf; +uint8_t *nbuf; +long nsz, psz; +static const int INIT_SZ = 128; + +typedef struct { + long key; + long val; +} JmpTblEntry; + +static bool jmptbl_eq(void *x, void *y) +{ + long *a = x, *b = y; + return *a == *b; +} + +static uint32_t jmptbl_hash(void *k) { return crc32(0, k, sizeof(long)); } + +HTable jmptbl; + +struct listnode { + struct listnode *next; + long val; +}; +typedef struct { + struct listnode *head; +} Stack; + +void stack_push(Stack *s, long val) +{ + struct listnode *n = malloc(sizeof(struct listnode)); + n->next = s->head; + n->val = val; + s->head = n; +} + +long *stack_top(Stack *s) +{ + if (s->head == NULL) + return NULL; + return &(s->head->val); +} + +void stack_pop(Stack *s) +{ + if (s->head == NULL) + return; + struct listnode *next = s->head->next; + free(s->head); + s->head = next; +} + +void buildjmptable(char *buf, long len) +{ + Stack s = {0}; + htable_init(&jmptbl, sizeof(JmpTblEntry), -1, jmptbl_hash, jmptbl_eq); + for (long i = 0; i < len; i++) { + if (buf[i] == '[') { + stack_push(&s, i); + } else if (buf[i] == ']') { + long j = *stack_top(&s); + stack_pop(&s); + JmpTblEntry e1 = {i, j}; + JmpTblEntry e2 = {j, i}; + htable_insert(&jmptbl, &e1); + htable_insert(&jmptbl, &e2); + } + } +} + +static long tbllookup(long pos) +{ + JmpTblEntry *iter = htable_find(&jmptbl, &pos); + return iter->val; +} + +void ensurespc_impl(uint8_t **buf, long *cursz, long ptr) +{ + if (ptr > *cursz) { + *buf = realloc(*buf, ptr * 2); + memset((*buf) + (*cursz), 0, 2 * ptr - (*cursz)); + *cursz = ptr * 2; + } +} + +void ensurespc(long ptr) +{ + if (ptr >= 0) { + ensurespc_impl(&pbuf, &psz, ptr); + } else { + ensurespc_impl(&nbuf, &nsz, -ptr); + } +} + +uint8_t getdata(long ptr) +{ + ensurespc(ptr); + if (ptr >= 0) + return pbuf[ptr]; + else + return nbuf[-ptr]; +} + +void setdata(long ptr, uint8_t val) +{ + ensurespc(ptr); + if (ptr >= 0) + pbuf[ptr] = val; + else + nbuf[-ptr] = val; +} + +void interp(char *prog, long prog_sz) +{ + long prog_p = 0; + long data_p = 0; + nbuf = malloc(INIT_SZ); + pbuf = malloc(INIT_SZ); + nsz = INIT_SZ; + psz = INIT_SZ; + memset(nbuf, 0, INIT_SZ); + memset(pbuf, 0, INIT_SZ); + + while (prog_p < prog_sz) { + switch (prog[prog_p]) { + case '>': + data_p++; + break; + case '<': + data_p--; + break; + case '+': + setdata(data_p, getdata(data_p) + 1); + break; + case '-': + setdata(data_p, getdata(data_p) - 1); + break; + case '.': + putchar(getdata(data_p)); + break; + case ',': + setdata(data_p, getchar()); + break; + case '[': + if (getdata(data_p) == 0) { + prog_p = tbllookup(prog_p); + } + break; + case ']': + if (getdata(data_p) != 0) { + prog_p = tbllookup(prog_p); + } + break; + default: + break; + } + prog_p++; + } +} + +int main(int argc, char **argv) +{ + if (argc < 2) { + LOGGER("invalid args"); + return EXIT_FAILURE; + } + int fd = open(argv[1], O_RDONLY); + if (fd < 0) { + return EXIT_FAILURE; + } + struct stat fst; + int ret = fstat(fd, &fst); + if (ret != 0) { + LOGGER("error: failed to get file stat"); + return EXIT_FAILURE; + } + long filesz = fst.st_size; + char *prog = malloc(filesz); + FILE *fp = fdopen(fd, "r"); + if (fp == NULL) { + LOGGER("error opening file"); + exit(-1); + } + size_t read = fread(prog, 1, filesz, fp); + if (read < filesz) { + LOGGER("erro reading"); + exit(-1); + } + buildjmptable(prog, filesz); + interp(prog, filesz); + return EXIT_SUCCESS; +} diff --git a/crc32.c b/crc32.c new file mode 100644 index 0000000..23436dc --- /dev/null +++ b/crc32.c @@ -0,0 +1,58 @@ +// Copyright (C) 2023 Dzshy . All Rights Reserved. +// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0. + +#include "crc32.h" + +const uint32_t crc32_tab[] = { + 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, + 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, + 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, + 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, + 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, + 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, + 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, + 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, + 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, + 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, + 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, + 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, + 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, + 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, + 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, + 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, + 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, + 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, + 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, + 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, + 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, + 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, + 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, + 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, + 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, + 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, + 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, + 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, + 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, + 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, + 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, + 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, + 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, + 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, + 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, + 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, + 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, + 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, + 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, + 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, + 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, + 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, + 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d}; + +uint32_t crc32(uint32_t crc, void *buf, int size) +{ + uint8_t *p = buf; + crc = ~crc; + while (size--) + crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8); + return ~crc; +} diff --git a/crc32.h b/crc32.h new file mode 100644 index 0000000..7055a1c --- /dev/null +++ b/crc32.h @@ -0,0 +1,11 @@ +// Copyright (C) 2023 Dzshy . All Rights Reserved. +// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0. + +#ifndef CRC32_H_ +#define CRC32_H_ + +#include + +uint32_t crc32(uint32_t r, void *buf, int size); + +#endif diff --git a/helloworld.bf b/helloworld.bf new file mode 100644 index 0000000..4e1d726 --- /dev/null +++ b/helloworld.bf @@ -0,0 +1,12 @@ +>++++++++[<+++++++++>-]<. +>++++[<+++++++>-]<+. ++++++++.. ++++. +>>++++++[<+++++++>-]<++. +------------. +>++++++[<+++++++++>-]<+. +<. ++++. +------. +--------. +>>>++++[<++++++++>-]<+. diff --git a/htable.c b/htable.c new file mode 100644 index 0000000..66ae607 --- /dev/null +++ b/htable.c @@ -0,0 +1,112 @@ +// Copyright (C) 2023 Dzshy . All Rights Reserved. +// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0. + +#include "htable.h" + +#include +#include + +#define HTFL_NUL 0 +#define HTFL_VAL 1 +#define HTFL_DEL 2 + +static void *htable_end(HTable *ht) +{ + return ht->buf + ht->cap * (ht->elemsz + 1); +} + +static void rebuild(HTable *ht) +{ + HTable newht; + htable_init(&newht, ht->elemsz, ht->size * 8, ht->hash, ht->eq); + void *iter = htable_begin(ht); + while (iter != NULL) { + htable_insert(&newht, iter); + iter = htable_next(ht, iter); + } + free(ht->buf); + *ht = newht; +} + +static uint8_t getflag(void *iter) { return *(uint8_t *)(iter - 1); } + +static void setflag(void *iter, uint8_t flag) { *(uint8_t *)(iter - 1) = flag; } + +void htable_init(HTable *ht, int elemsz, int cap, uint32_t (*hash)(void *), + bool (*eq)(void *, void *)) +{ + if (cap < 16) + cap = 16; + ht->buf = malloc(cap * (elemsz + 1)); + memset(ht->buf, 0, cap * (elemsz + 1)); + ht->size = 0; + ht->cap = cap; + ht->taken = 0; + ht->begin = NULL; + ht->elemsz = elemsz; + ht->hash = hash; + ht->eq = eq; +} + +bool htable_insert(HTable *ht, void *elem) +{ + if (ht->taken + 1 > ht->cap / 4) { + rebuild(ht); + } + ht->taken++; + ht->size++; + int hashcode = ht->hash(elem) % ht->cap; + void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1; + while (getflag(pos) != HTFL_NUL) { + if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem)) + return false; + pos += ht->elemsz + 1; + if (pos >= htable_end(ht)) { // arrived end, restart from beginning + pos = ht->buf + 1; + } + } + memcpy(pos, elem, ht->elemsz); + setflag(pos, HTFL_VAL); + if (pos < ht->begin || ht->begin == NULL) { + ht->begin = pos; + } +} + +void htable_del(HTable *ht, void *iter) +{ + ht->size--; + setflag(iter, HTFL_DEL); + if (iter == ht->begin) { + ht->begin = htable_next(ht, iter); + } +} + +void *htable_find(HTable *ht, void *elem) +{ + int hashcode = ht->hash(elem) % ht->cap; + void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1; + while (getflag(pos) != HTFL_NUL) { + if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem)) + return pos; + pos += ht->elemsz + 1; + if (pos >= htable_end(ht)) { // arrived end, restart from beginning + pos = ht->buf + 1; + } + } + return NULL; +} + +void *htable_begin(HTable *ht) { return ht->begin; } + +void *htable_next(HTable *ht, void *iter) +{ + void *pos = iter; + pos += ht->elemsz + 1; + while (getflag(pos) != HTFL_VAL) { + pos += ht->elemsz + 1; + if (pos >= htable_end(ht)) { // arrived end, restart from beginning + return NULL; + } + } + return pos; +} diff --git a/htable.h b/htable.h new file mode 100644 index 0000000..c373baa --- /dev/null +++ b/htable.h @@ -0,0 +1,31 @@ +// Copyright (C) 2023 Dzshy . All Rights Reserved. +// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0. + +#ifndef HTABLE_H_ +#define HTABLE_H_ + +#include +#include + +typedef struct { + void *buf; + int size; + int cap; + int taken; + void *begin; + int elemsz; + uint32_t (*hash)(void *); + bool (*eq)(void *, void *); +} HTable; + +void htable_init(HTable *ht, int elemsz, int cap, uint32_t (*hash)(void *), + bool (*eq)(void *, void *)); +bool htable_insert(HTable *ht, void *elem); +void htable_del(HTable *ht, void *iter); + +// return a iterator +void *htable_find(HTable *ht, void *elem); +void *htable_begin(HTable *ht); +void *htable_next(HTable *ht, void *iter); + +#endif diff --git a/scripts/format.sh b/scripts/format.sh new file mode 100755 index 0000000..6dade1b --- /dev/null +++ b/scripts/format.sh @@ -0,0 +1,3 @@ +#!/bin/bash + +clang-format -i $(find . -name '*.c' -or -name '*.h') -- cgit v1.0