diff options
| -rw-r--r-- | .clang-format | 6 | ||||
| -rw-r--r-- | .gitignore | 3 | ||||
| -rw-r--r-- | LICENSE | 207 | ||||
| -rw-r--r-- | Makefile | 8 | ||||
| -rw-r--r-- | README.md | 30 | ||||
| -rw-r--r-- | brainfuck.c | 212 | ||||
| -rw-r--r-- | crc32.c | 58 | ||||
| -rw-r--r-- | crc32.h | 11 | ||||
| -rw-r--r-- | helloworld.bf | 12 | ||||
| -rw-r--r-- | htable.c | 112 | ||||
| -rw-r--r-- | htable.h | 31 | ||||
| -rwxr-xr-x | scripts/format.sh | 3 |
12 files changed, 693 insertions, 0 deletions
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 + @@ -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 <dzshy@outlook.com>. All Rights Reserved. +// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0. + +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include <fcntl.h> +#include <sys/mman.h> +#include <sys/stat.h> + +#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; +} @@ -0,0 +1,58 @@ +// Copyright (C) 2023 Dzshy <dzshy@outlook.com>. 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; +} @@ -0,0 +1,11 @@ +// Copyright (C) 2023 Dzshy <dzshy@outlook.com>. All Rights Reserved. +// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0. + +#ifndef CRC32_H_ +#define CRC32_H_ + +#include <stdint.h> + +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 <dzshy@outlook.com>. All Rights Reserved. +// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0. + +#include "htable.h" + +#include <stdlib.h> +#include <string.h> + +#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 <dzshy@outlook.com>. All Rights Reserved. +// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0. + +#ifndef HTABLE_H_ +#define HTABLE_H_ + +#include <stdbool.h> +#include <stdint.h> + +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') |