From 9594210f02572681ed581c5197ace4c207db0917 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Mon, 8 Nov 2021 16:37:57 +0800 Subject: initial commit Now the rough framework is established and the grammar class is sort of ready. It remains to write a general input reading mechanism. --- src/Makefile.am | 32 ++++++ src/config.h | 29 ++++++ src/grammar.c | 106 ++++++++++++++++++++ src/grammar.h | 59 +++++++++++ src/input.c | 1 + src/input.h | 8 ++ src/list.c | 247 +++++++++++++++++++++++++++++++++++++++++++++++ src/list.h | 74 ++++++++++++++ src/test/check_grammar.c | 35 +++++++ src/test/check_list.c | 217 +++++++++++++++++++++++++++++++++++++++++ src/util.h | 34 +++++++ 11 files changed, 842 insertions(+) create mode 100644 src/Makefile.am create mode 100644 src/config.h create mode 100644 src/grammar.c create mode 100644 src/grammar.h create mode 100644 src/input.c create mode 100644 src/input.h create mode 100644 src/list.c create mode 100644 src/list.h create mode 100644 src/test/check_grammar.c create mode 100644 src/test/check_list.c create mode 100644 src/util.h (limited to 'src') diff --git a/src/Makefile.am b/src/Makefile.am new file mode 100644 index 0000000..d38ef1b --- /dev/null +++ b/src/Makefile.am @@ -0,0 +1,32 @@ +AM_CFLAGS = -Wall -Wextra + +noinst_LIBRARIES = libeps.a +libeps_a_SOURCES = grammar.c list.c input.c \ +grammar.h list.h util.h input.h + +libeps_a_CFLAGS = $(AM_CFLAGS) --pedantic + +# Make TAGS automatically + +all-local: MYTAGS + +MYTAGS: $(TAGS_DEPENDENCIES) $(am__tagged_files) + @if $(AM_V_P); then $(MAKE) TAGS; else echo "MAKE TAGS"; \ + $(MAKE) TAGS > /dev/null; fi; + + +CLEANFILES = TAGS + +# tests + +check_PROGRAMS = check_list check_grammar + +check_list_SOURCES = test/check_list.c list.c + +check_grammar_SOURCES = test/check_grammar.c list.c grammar.c + +TESTS = $(check_PROGRAMS) + +AM_COLOR_TESTS = always + + diff --git a/src/config.h b/src/config.h new file mode 100644 index 0000000..b51c0c8 --- /dev/null +++ b/src/config.h @@ -0,0 +1,29 @@ +/* src/config.h. Generated from config.h.in by configure. */ +/* src/config.h.in. Generated from configure.ac by autoheader. */ + +/* Define if one wants to debug the program. */ +/* #undef DEBUG */ + +/* Name of package */ +#define PACKAGE "eps" + +/* Define to the address where bug reports for this package should be sent. */ +#define PACKAGE_BUGREPORT "mmemmew@gmail.com" + +/* Define to the full name of this package. */ +#define PACKAGE_NAME "eps" + +/* Define to the full name and version of this package. */ +#define PACKAGE_STRING "eps 0.1.0" + +/* Define to the one symbol short name of this package. */ +#define PACKAGE_TARNAME "eps" + +/* Define to the home page for this package. */ +#define PACKAGE_URL "" + +/* Define to the version of this package. */ +#define PACKAGE_VERSION "0.1.0" + +/* Version number of package */ +#define VERSION "0.1.0" diff --git a/src/grammar.c b/src/grammar.c new file mode 100644 index 0000000..9265ef5 --- /dev/null +++ b/src/grammar.c @@ -0,0 +1,106 @@ +#include "grammar.h" + +struct TNT_s { + int type; /* 0 => T and NT otherwise */ + union { T t; NT nt; } data; +}; + +struct Rule_s { + NT left; + List *right; +}; + +TNT *new_tnt(int type, ...) +{ + va_list args; + va_start(args, type); + + TNT *result = MYALLOC(TNT, 1); + result->type = type; + + if (type) result->data.nt = va_arg(args, NT); + else result->data.t = va_arg(args, T); + + va_end(args); + + return result; +} + +Rule *new_rule(NT left, List *right) +{ + if (!right) return NULL; + + Rule *rule = MYALLOC(Rule, 1); + + rule->left = left; + rule->right = right; + + return rule; +} + +void print_tnt(void *element) +{ + TNT *tnt = (TNT*) element; + + if (tnt->type) + printf("NT %u, ", tnt->data.nt); + else + printf("T %lu, ", tnt->data.t); +} + +void print_rule(void *r) +{ + Rule *rule = (Rule *)r; + printf("Rule: NT %u => ", rule->left); + + map_list(rule->right, print_tnt); + + printf("\n"); +} + +void print_grammar(Grammar g) +{ + printf("Printing a grammar:\n"); + map_list(g, print_rule); + printf("\n"); +} + +List *new_tnt_string(char *format, int format_len, ...) +{ + /* FORMAT_LEN does not include the terminating null byte, so it + should be > 0. */ + + if (format_len <= 0) return NULL; + + List *result = new_list(); + + va_list args; + va_start(args, format_len); + + for (int point = 0; point < format_len; point++) { + switch (*(format+point)) { + case 'n': + add_to_list(result, new_tnt(1, va_arg(args, NT))); + break; + case 't': + add_to_list(result, new_tnt(0, va_arg(args, T))); + break; + default: + eprintf("Wront character: %c\n", *(format+point)); + destroy_list(result, 1); + va_end(args); + return NULL; + break; + } + } + + va_end(args); + + return result; +} + +void destroy_rule(Rule *rule) +{ + destroy_list(rule->right, 1); + free(rule); +} diff --git a/src/grammar.h b/src/grammar.h new file mode 100644 index 0000000..2baec68 --- /dev/null +++ b/src/grammar.h @@ -0,0 +1,59 @@ +#ifndef GRAMMAR_H +#define GRAMMAR_H + +#include +#include +#include "list.h" + +/* The class file for grammars */ + +/* A grammar is a list of rules. A rule replaces a non-terminal with + a finite string of terminals and non-terminals. + + For us, a terminal is a positive integer, and a non-terminal is a + negative integer. Since the signs of these two types is fixed, we + represent them as unsigned integers. Since we want to deal with + unicode points, the terminal is stored as unsigned long, so that we + can include all unicode poitns. */ + +typedef unsigned long T; +typedef unsigned NT; + +typedef struct TNT_s TNT; +typedef struct Rule_s Rule; + +/* A grammar is a list of rules. */ +typedef List *Grammar; + +/* This accepts one and only one optional argument, which is of type + either T or NT, depending on TYPE being 0 or not. */ +TNT *new_tnt(int type, ...); + +/* For debugging purposes, we need to print out rules to examine their + values. */ + +void print_tnt(void *element); + +void print_rule(void *r); + +/* This will generate errors if G is not a list of rules. */ +void print_grammar(Grammar g); + +/* constructors */ + +/* FORMAT specifies the types of TNTs. It is a string of t and n's. + FORMAT_LEN is the length of FORMAT, excluding the terminating null + byte. + + Upon failure NULL is returned. */ +List *new_tnt_string(char *format, int format_len, ...); + +/* RIGHT should be created by new_tnt_string or something alike. + + If RIGHT is NULL, NULL is returned. */ +Rule *new_rule(NT left, List *right); + +/* destructors */ +void destroy_rule(Rule *rule); + +#endif diff --git a/src/input.c b/src/input.c new file mode 100644 index 0000000..018d9c7 --- /dev/null +++ b/src/input.c @@ -0,0 +1 @@ +#include "input.h" diff --git a/src/input.h b/src/input.h new file mode 100644 index 0000000..16a4ca6 --- /dev/null +++ b/src/input.h @@ -0,0 +1,8 @@ +#ifndef INPUT_H +#define INPUT_H + +#include "grammar.h" + + + +#endif diff --git a/src/list.c b/src/list.c new file mode 100644 index 0000000..8c67a09 --- /dev/null +++ b/src/list.c @@ -0,0 +1,247 @@ +#include "list.h" +#include "util.h" +#include +#include + +struct List_s { + void **array; /* the array of elements */ + NUM len; /* the length of the array */ + NUM capacity; /* the number of pre-allocated bytes + for the array */ +}; + +List * +new_list() +{ + void **array = MYALLOC(void*, LIST_INIT_AMOUNT); + + if (array == NULL) return NULL; + + for (NUM i = 0; i < LIST_INIT_AMOUNT; i++) + *(array+i) = NULL; + + List *list = MYALLOC(List, 1); + + if (list == NULL) return NULL; + + list->array = array; + list->len = 0; + list->capacity = LIST_INIT_AMOUNT; + + return list; +} + +H_ATTR +unsigned char +add_to_list(List *ls, void *element) +{ + if (!(ls->capacity)) { + /* The capacity can be zero only when the list has been destroyed, + in which case adding an element to that list is definitely an + error. */ + eprintf("%s:%d, Adding an element to a destroyed list.\n", + __FILE__, __LINE__); + } + + (ls->len)++; + + if (ls->len >= ls->capacity) { + NUM new_capacity = ((ls->capacity) * 3) >> 1; + + if (new_capacity < ls->capacity + LIST_INIT_AMOUNT) + new_capacity = ls->capacity + LIST_INIT_AMOUNT; + + NUM max_diff = 1 << 20; + if (new_capacity >= ls->capacity + max_diff) + new_capacity = ls->capacity + max_diff; + + void **array = MYALLOC(void *, ls->capacity); + + if (array == NULL) { + ls->len -= 1; + return 1; + } + + for (NUM i = 0; i < ls->capacity; i++) + *(array+i) = *(ls->array+i); + + /* The new_capacity will not be zero, so upon failure it returns + NULL. */ + ls->array = realloc(ls->array, sizeof(void*) * new_capacity); + + if (ls->array == NULL) { + ls->len -= 1; + free(array); + return 1; + } + + for (NUM i = 0; i < ls->capacity; i++) + *(ls->array+i) = *(array+i); + + free(array); + + for (NUM i = ls->capacity; i < new_capacity; i++) + *(ls->array+i) = NULL; + + ls->capacity = new_capacity; + } + + *(ls->array+ls->len-1) = element; + + return 0; +} + +H_ATTR +void * +pop_from_list(List *ls) +{ + if (!(ls->len)) return NULL; + + return *(ls->array+--(ls->len)); +} + +H_ATTR +void +map_list(List *ls, acter f) +{ + for (NUM i = 0; i < ls->len; i++) + f(*(ls->array+i)); +} + +void +print_list(List *ls, printer prt) +{ + printf("printing a list with length = %lu and capacity = %lu\n", + ls->len, ls->capacity); + + map_list(ls, (acter) prt); + + printf("printing terminated\n"); +} + +void * +copy_num(void *p) +{ + NUM *pointer = malloc(sizeof *pointer); + + if (pointer == NULL) return NULL; + + *pointer = *((NUM *) p); + + return pointer; +} + +unsigned char +copy_list(List *dest, List *source, copyer copyf) +{ + unsigned char sign = 0; + + if ((sign = list_assure_size(dest, source->len))) + return sign; + + dest->len = source->len; + + for (NUM i = 0; i < source->len; i++) { + void *pointer = copyf(*(source->array+i)); + if (pointer == NULL) return 1; + *(dest->array+i) = pointer; + } + + return 0; +} + +H_ATTR +void * +list_nth(List *ls, NUM n) +{ + return *(ls->array+n); +} + +H_ATTR +NUM +list_length(List *ls) +{ + return ls->len; +} + +unsigned char +list_assure_size(List *ls, NUM size) +{ + if (ls->capacity >= size) return 0; /* we are good */ + + void **array = MYALLOC(void *, ls->capacity); + + if (array == NULL) return 1; + + for (NUM i = 0; i < ls->capacity; i++) + *(array+i) = *(ls->array+i); + + ls->array = realloc(ls->array, sizeof(void*) * size); + + if (ls->array == NULL) return 1; + + for (NUM i = 0; i < ls->capacity; i++) + *(ls->array+i) = *(array+i); + + free(array); + + for (NUM i = ls->capacity; i < size; i++) + *(ls->array+i) = NULL; + + ls->capacity = size; + + return 0; +} + +unsigned char +list_set_length(List *ls, NUM len) +{ + if (ls->len >= len) return 0; + + NUM *array = MYALLOC(NUM, len - ls->len); + + if (array == NULL) return 1; + + for (NUM i = ls->len; i < len; i++) { + *(array + i - ls->len) = -1; + *(ls->array+i) = array + i - ls->len; + } + + ls->len = len; + + return 0; +} + +void * +list_to_array(List *ls, NUM element_bytes, NUM *num) +{ + /* We shall not use a void pointer here, since standard C does not + allow doing arithmetic on void pointers. So we use a char + pointer here, since the size of char is 1. */ + char *array = malloc(element_bytes * ls->len); + + if (array == NULL) return NULL; + + *num = ls->len; + + for (NUM i = 0; i < *num; i++) + memcpy(array+(element_bytes*i), *(ls->array+i), element_bytes); + + return array; +} + +void +destroy_list(List *ls, unsigned char all_free_p) +{ + if (all_free_p == 1) + for (NUM i = 0; i < ls->len; i++) + free(*(ls->array+i)); + + if (all_free_p == 2) + free(*(ls->array)); + + free(ls->array); + free(ls); + + ls->len = (ls->capacity = 0); +} diff --git a/src/list.h b/src/list.h new file mode 100644 index 0000000..d774f96 --- /dev/null +++ b/src/list.h @@ -0,0 +1,74 @@ +#ifndef LIST_H +#define LIST_H +#include +#include "util.h" + +/* Use an enumeration instead of a MACRO */ +enum { LIST_INIT_AMOUNT = 32 }; + +/* The elements of the list are all void pointers, so the users of the + list should determine the types of the elements manually. */ + +typedef struct List_s List; + +/* allocate a new list */ +/* upon failure return NULL */ +List *new_list(); + +/* add an element to the end of the list */ +/* upon failure return non-zero */ +unsigned char add_to_list(List *ls, void *element); + +/* pop an element from the end of the list, and return that element */ +/* upon failure return NULL */ +void *pop_from_list(List *ls); + +typedef void (*printer)(void *); + +typedef printer acter; /* a type that can act on list + elements */ + +void map_list(List *ls, acter f); + +void print_list(List *ls, printer prt); + +/* COPYER is expected to return NULL when it fails to copy. */ +typedef void *(*copyer)(void *); + +/* upon failure return NULL */ +void *copy_num(void *); + +/* upon failure return 1 */ +unsigned char copy_list(List *dest, List *source, copyer copyf); + +void *list_nth(List *ls, NUM n); + +NUM list_length(List *ls); + +/* Make sure the list has at least SIZE slots to use. This should + only be used to create fixed capacity arrays, otherwise we risk + frequently re-allocating and hence losing performance. */ +/* Upon failure return non-zero. */ +unsigned char list_assure_size(List *ls, NUM size); + +/* This is mainly used to set the length of a sparse list, since only + when dealing with sparse lists do we not need to care about the + elements. */ +/* Upon failure return non-zero. */ +unsigned char list_set_length(List *ls, NUM len); + +/* Convert a list to an array. + + ELEMENT_BYTES means the size of the type of elements. This is used + to calculate the number of elements in the array. + + The number of elements of the array will be stored in *NUM. */ +void *list_to_array(List *ls, NUM element_bytes, NUM *num); + +/* destroy the list: If ALL_FREE_P is 1, this frees every void + pointers contained in the list; if it is 2, this frees the first + pointer. In any case, the list is de-allocated. */ +void destroy_list(List *ls, unsigned char all_free_p); + + +#endif diff --git a/src/test/check_grammar.c b/src/test/check_grammar.c new file mode 100644 index 0000000..1fe27dd --- /dev/null +++ b/src/test/check_grammar.c @@ -0,0 +1,35 @@ +#include +#include +#include "../grammar.h" + +int main(U_ATTR int argc, U_ATTR char **argv) +{ + /* check new_tnt and print it */ + TNT *tnt = new_tnt(1, 12); + + printf("Print a TNT value of type NT: "); + print_tnt(tnt); + printf("\n"); + + free(tnt); + + /* check new_tnt_string */ + + List *tnt_string = new_tnt_string("tntnt", 5, + (T) 1, (NT) 2, (T) 3, (NT) 4, (T) 15); + + if (!tnt_string) { + eprintf("error!\n"); + return 1; + } + + /* check new_rule, print_rule, and destroy_rule. */ + + Rule *rule = new_rule(1, tnt_string); + + print_rule(rule); + + destroy_rule(rule); + + return 0; +} diff --git a/src/test/check_list.c b/src/test/check_list.c new file mode 100644 index 0000000..8677cd3 --- /dev/null +++ b/src/test/check_list.c @@ -0,0 +1,217 @@ +#include +#include +#include "../list.h" + +void +print_int(void *p) +{ + printf("%d\n", *((int *)p)); +} + +int +main(U_ATTR int argc, U_ATTR char **argv) +{ + List *ls = new_list(); + + if (!ls) { + eprintf("%s:%d, failed to create a new list\n", + __FILE__, __LINE__); + exit(1); + } + + unsigned char result = 0; + + int x[] = { 1, 2, 3, 4, 1 }; + + for (size_t i = 0; i < sizeof(x) / sizeof(*x); i++) { + if (add_to_list(ls, x+i)) { + eprintf("failed to add %ld-th element to LS\n", + i); + exit(1); + } + } + + print_list(ls, print_int); + + NUM expected_ls_len = sizeof(x) / sizeof(*x); + + if (list_length(ls) != expected_ls_len) { + eprintf("The length of the list is wrong!\n"); + exit(1); + } + + eprintf("The length is correct!\n"); + + NUM array_len = 0; + int *array = list_to_array(ls, sizeof(*array), &array_len); + + if (!array) { + eprintf("%s:%d, failed to convert the list to an array\n", + __FILE__, __LINE__); + exit(1); + } + + if (array_len != expected_ls_len) { + eprintf("The length of the array is wrong!\n"); + exit(1); + } + + eprintf("The length of the array is correct!\n"); + + for (NUM i = 0; i < expected_ls_len; i++) { + if (*(array+i) != *(x+i)) { + eprintf("The %lu-th element of array = %d, x = %d\n", + i, *(array+i), *(x+i)); + exit(1); + } + } + + eprintf("Every element of the array is as expected!\n"); + + for (NUM i = 0; i < expected_ls_len; i++) { + int *pointer = pop_from_list(ls); + + if (!pointer) { + eprintf("%s:%d, i = %ld, Popping returns NULL\n", + __FILE__, __LINE__, i); + exit(1); + } + + if (*pointer != *(x+expected_ls_len-i-1)) { + eprintf("i = %ld, *pointer = %d, and x = %d\n", + i, *pointer, *(x+expected_ls_len-i-1)); + exit(1); + } + } + + eprintf("pop_from_list works as expected.\n"); + + print_list(ls, print_int); + + expected_ls_len = 5; + + for (NUM i = 0; i < expected_ls_len; i++) { + int *pointer = malloc(sizeof *pointer * 1); + + if (!pointer) { + eprintf("%s:%d, i = %ld, failed to malloc\n", + __FILE__, __LINE__, i); + exit(1); + } + + *pointer = expected_ls_len-1-i; + if (add_to_list(ls, pointer)) { + eprintf("%s:%d, i = %ld, failed to add element\n", + __FILE__, __LINE__, i); + exit(1); + } + } + + print_list(ls, print_int); + + destroy_list(ls, 1); + + eprintf("Successfully destroyed the list and freed every element\n"); + + free(array); + + ls = new_list(); + + if (!ls) { + eprintf("%s:%d, failed to create a new list\n", + __FILE__, __LINE__); + exit(1); + } + + if (list_assure_size(ls, 513)) { + eprintf("%s:%d, failed to assure size\n", + __FILE__, __LINE__); + exit(1); + } + + if (list_set_length(ls, 513)) { + eprintf("%s:%d, failed to set length\n", + __FILE__, __LINE__); + exit(1); + } + + print_list(ls, print_int); + + destroy_list(ls, 2); + + eprintf("Successfully destroyed the list\n"); + + if (!(ls = new_list())) { + eprintf("%s:%d, failed to create a new list\n", + __FILE__, __LINE__); + exit(1); + } + + List *ls2 = new_list(); + + if (!ls2) { + eprintf("%s:%d, failed to create a new list\n", + __FILE__, __LINE__); + exit(1); + } + + for (NUM i = 0; i < 5; i++) { + int *pointer = malloc(sizeof *pointer * 1); + + if (!pointer) { + eprintf("%s:%d, failed to malloc\n", + __FILE__, __LINE__); + exit(1); + } + + *pointer = 4-i; + + if (add_to_list(ls2, pointer)) { + eprintf("%s:%d, i = %ld, failed to add to list\n", + __FILE__, __LINE__, i); + exit(1); + } + } + + print_list(ls2, print_int); + + result = copy_list(ls, ls2, copy_num); + + if (result) { + eprintf("%s:%d, failed to copy list\n", + __FILE__, __LINE__); + exit(1); + } + + destroy_list(ls2, 1); + destroy_list(ls, 1); + + eprintf("Successfully destroyed lists!\n"); + + /* test a list with pointers in an array */ + + if (!(ls = new_list())) { + eprintf("%s:%d, failed to create a new list\n", + __FILE__, __LINE__); + exit(1); + } + + NUM arr[10]; + + for (NUM i = 0; i < 10; i++) { + arr[i] = i*i-i+1; + if (add_to_list(ls, arr+i)) { + eprintf("%s:%d, i = %ld, failed to add element\n", + __FILE__, __LINE__, i); + exit(1); + } + } + + print_list(ls, print_int); + + destroy_list(ls, 0); + + printf("Every test is successful!\n"); + + return 0; +} diff --git a/src/util.h b/src/util.h new file mode 100644 index 0000000..d657f0e --- /dev/null +++ b/src/util.h @@ -0,0 +1,34 @@ +#ifndef UTIL_H +#define UTIL_H +#include + +/* This is commonly used, so put here for easy access. */ +#define MYALLOC(TYPE, LEN) (TYPE*)malloc(sizeof(TYPE) * (LEN)) + + +typedef long DATA; +typedef long NUM; +typedef unsigned long long UNUM; /* definitely bigger than size_t */ + + +#define HC_ATTR __attribute__((__hot__, __const__)) +#define H_ATTR __attribute__((__hot__)) +#define P_ATTR __attribute__((__pure__)) +#define UNUSED __attribute__((__unused__)) +#define U_ATTR UNUSED + +#define D_ATTR(X) __attribute__((__unused__, __deprecated__("This is deprecated.\n" \ + "Please use " X \ + " instead"))) + +#define UD_ATTR __attribute__((__unused__, __deprecated__)) +#define UC_ATTR __attribute__((__unused__, __const__)) +#define UH_ATTR __attribute__((__unused__, __hot__)) +#define UHP_ATTR __attribute__((__unused__, __hot__, __pure__)) + + +#define eprintf(...) fprintf(stderr, __VA_ARGS__) + + + +#endif -- cgit v1.2.3-18-g5258