X-Git-Url: https://git.distorted.org.uk/~mdw/runlisp/blobdiff_plain/7b8ff279e7304e41b243459d78c3b6703bb8c3f5..e4b13205c44ec284966bfe9931ad48fed3484497:/lib.h diff --git a/lib.h b/lib.h index 2209c30..9bf07d9 100644 --- a/lib.h +++ b/lib.h @@ -40,7 +40,9 @@ /*----- Handy macros ------------------------------------------------------*/ #define N(v) (sizeof(v)/sizeof((v)[0])) + /* The number of elements in the array V. */ +/* Figure out the compiler version to see whether fancy tricks will work. */ #if defined(__GNUC__) # define GCC_VERSION_P(maj, min) \ (__GNUC__ > (maj) || (__GNUC__ == (maj) && __GNUC_MINOR__ >= (min))) @@ -57,258 +59,683 @@ #endif #if GCC_VERSION_P(2, 5) || CLANG_VERSION_P(3, 3) + # define NORETURN __attribute__((__noreturn__)) + /* Mark a function as not returning. */ + # define PRINTF_LIKE(fix, aix) __attribute__((__format__(printf, fix, aix))) + /* Mark a function as accepting a printf(3)-like format string as + * argument FIX, with arguments to be substituted starting at AIX. + */ #endif #if GCC_VERSION_P(4, 0) || CLANG_VERSION_P(3, 3) + # define EXECL_LIKE(ntrail) __attribute__((__sentinel__(ntrail))) + /* Mark a function as expecting a variable number of arguments + * terminated by a null pointer, followed by NTRAIL further + * arguments. + */ + #endif +/* Couldn't detect fancy compiler features. We'll have to make do + * without. + */ +#ifndef NORETURN +# define NORETURN +#endif +#ifndef PRINTF_LIKE +# define PRINTF_LIKE(fix, aix) +#endif +#ifndef EXECL_LIKE +# define EXECL_LIKE(ntrail) +#endif + +#define DISCARD(x) do if (x); while (0) + /* Discard the result of evaluating expression X, without upsetting + * the compiler. + */ + +#define END ((const char *)0) + /* A null pointer to terminate the argument tail to an `EXECL_LIKE' + * function. (Note that `NULL' is /not/ adequate for this purpose, + * since it might expand simply to `0', which is an integer, not a + * pointer, and might well be the wrong size and/or value.) + */ + +/* Wrap up macros with explicit conversions to `unsigned char'. */ #define CTYPE_HACK(func, ch) (func((unsigned char)(ch))) #define ISSPACE(ch) CTYPE_HACK(isspace, ch) #define ISALNUM(ch) CTYPE_HACK(isalnum, ch) +#define ISXDIGIT(ch) CTYPE_HACK(isxdigit, ch) +#define TOLOWER(ch) CTYPE_HACK(tolower, ch) +#define TOUPPER(ch) CTYPE_HACK(toupper, ch) +/* Wrap up comparison functions to take an ordering relation as part of their + * syntax. This makes it much harder to screw up. + */ #define MEMCMP(x, op, y, n) (memcmp((x), (y), (n)) op 0) #define STRCMP(x, op, y) (strcmp((x), (y)) op 0) #define STRNCMP(x, op, y, n) (strncmp((x), (y), (n)) op 0) -#define DISCARD(x) do if (x); while (0) - -#define END ((const char *)0) - #ifndef SIZE_MAX # define SIZE_MAX (-(size_t)1) #endif - -/*----- Miscellany --------------------------------------------------------*/ - -extern int str_lt(const char */*a*/, size_t /*an*/, - const char */*b*/, size_t /*bn*/); + /* The largest value that can be stored in an object of type + * `size_t'. A proper setting would be a preprocessor- + * time constant, but we don't actually need that. + */ /*----- Diagnostic utilities ----------------------------------------------*/ extern const char *progname; + /* Our program name, for use in error messages. */ extern void set_progname(const char */*prog*/); + /* Set `progname' from the pathname in PROG (typically from + * `argv[0]'). + */ + extern void vmoan(const char */*msg*/, va_list /*ap*/); + /* Report an error or warning in Unix style, given a captured + * argument cursor. + */ + extern PRINTF_LIKE(1, 2) void moan(const char */*msg*/, ...); + /* Issue a warning message. */ + extern NORETURN PRINTF_LIKE(1, 2) void lose(const char */*msg*/, ...); + /* Issue a fatal error message and exit unsuccessfully. */ /*----- Memory allocation -------------------------------------------------*/ extern void *xmalloc(size_t /*n*/); + /* Allocate and return a pointer to N bytes, or report a fatal error. + * + * Release the pointer using `free' as usual. If N is zero, returns + * null (but you are not expected to check for this). + */ + extern void *xrealloc(void */*p*/, size_t /*n*/); + /* Resize the block at P (from `malloc' or `xmalloc') to be N bytes + * long. + * + * The block might (and probably will) move, so it returns the new + * address. If N is zero, then the block is freed (if necessary) and + * a null pointer returned; otherwise, if P is null then a fresh + * block is allocated. If allocation fails, then a fatal error is + * reported. + */ + extern char *xstrndup(const char */*p*/, size_t /*n*/); + /* Allocate and return a copy of the N-byte string starting at P. + * + * The new string is null-terminated, though P need not be. If + * allocation fails, then a fatal error is reported. + */ + extern char *xstrdup(const char */*p*/); + /* Allocate and return a copy of the null-terminated string starting + * at P. + * + * If allocation fails, then a fatal error is reported. + */ /*----- Dynamic strings ---------------------------------------------------*/ +/* A dynamic string. + * + * Note that the string might not be null-terminated. + */ struct dstr { - char *p; - size_t len, sz; + char *p; /* string base address */ + size_t len; /* current string length */ + size_t sz; /* allocated size of buffer */ }; #define DSTR_INIT { 0, 0, 0 } extern void dstr_init(struct dstr */*d*/); + /* Initialize the string D. + * + * Usually you'd use the static initializer `DSTR_INIT'. + */ + extern void dstr_reset(struct dstr */*d*/); + /* Reset string D so it's empty again. */ + extern void dstr_ensure(struct dstr */*d*/, size_t /*n*/); + /* Ensure that D has at least N unused bytes available. */ + extern void dstr_release(struct dstr */*d*/); + /* Release the memory held by D. + * + * It must be reinitialized (e.g., by `dstr_init') before it can be + * used again. + */ + extern void dstr_putm(struct dstr */*d*/, const void */*p*/, size_t /*n*/); + /* Append the N-byte string at P to D. + * + * P need not be null-terminated. D will not be null-terminated + * afterwards. + */ + extern void dstr_puts(struct dstr */*d*/, const char */*p*/); + /* Append the null-terminated string P to D. + * + * D /is/ guaranteed to be null-terminated after this. + */ + extern void dstr_putc(struct dstr */*d*/, int /*ch*/); + /* Append the single character CH to D. + * + * D will not be null-terminated afterwards. + */ + +extern void dstr_putcn(struct dstr */*d*/, int /*ch*/, size_t /*n*/); + /* Append N copies of the character CH to D. + * + * D will not be null-terminated afterwards. + */ + extern void dstr_putz(struct dstr */*d*/); + /* Null-terminate the string D. + * + * This doesn't change the length of D. If further stuff is appended + * then the null terminator will be overwritten. + */ + extern void dstr_vputf(struct dstr */*d*/, const char */*p*/, va_list /*ap*/); + /* Append stuff to D, determined by printf(3) format string P and + * argument tail AP. + * + * D will not be null-terminated afterwards. + */ + extern PRINTF_LIKE(2, 3) void dstr_putf(struct dstr */*d*/, const char */*p*/, ...); + /* Append stuff to D, determined by printf(3) format string P and + * arguments. + * + * D will not be null-terminated afterwards. + */ + extern int dstr_readline(struct dstr */*d*/, FILE */*fp*/); + /* Append the next input line from FP to D. + * + * Return 0 on success, or -1 if reading immediately fails or + * encounters end-of-file (call ferror(3) to distinguish). Any + * trailing newline is discarded: it is not possible to determine + * whether the last line was ended with a newline. D is guaranteed + * to be null-terminated afterwards. + */ /*----- Dynamic vectors of strings ----------------------------------------*/ +/* A dynamic vector of strings. + * + * This machinery only actually tracks character pointers. It assumes that + * the caller will manage the underlying storage for the strings. + * + * Note that `v' always points to the first element in the vector. The + * underlying storage starts `o' slots before this. +*/ struct argv { - const char **v; - size_t o, n, sz; + char **v; /* pointer the first element */ + size_t n; /* length of the vector */ + size_t o; /* number of spare slots at start */ + size_t sz; /* allocated size (in slots) */ }; #define ARGV_INIT { 0, 0, 0, 0 } extern void argv_init(struct argv */*a*/v); + /* Initialize the vector AV. + * + * Usually you'd use the static initializer `ARGV_INIT'. + */ + extern void argv_reset(struct argv */*av*/); + /* Reset the vector AV so that it's empty again. */ + extern void argv_ensure(struct argv */*av*/, size_t /*n*/); + /* Ensure that AV has at least N unused slots at the end. */ + extern void argv_ensure_offset(struct argv */*av*/, size_t /*n*/); + /* Ensure that AV has at least N unused slots at the /start/. */ + extern void argv_release(struct argv */*av*/); -extern void argv_append(struct argv */*av*/, const char */*p*/); + /* Release the memory held by AV. + * + * It must be reinitialized (e.g., by `argv_init') before it can be + * used again. + */ + +extern void argv_append(struct argv */*av*/, char */*p*/); + /* Append the pointer P to AV. */ + extern void argv_appendz(struct argv */*av*/); + /* Append a null pointer to AV, without extending the vactor length. + * + * The null pointer will be overwritten when the next string is + * appended. + */ + extern void argv_appendn(struct argv */*av*/, - const char *const */*v*/, size_t /*n*/); + char *const */*v*/, size_t /*n*/); + /* Append a N-element vector V of pointers to AV. */ + extern void argv_appendav(struct argv */*av*/, const struct argv */*bv*/); + /* Append the variable-length vector BV to AV. */ + extern void argv_appendv(struct argv */*av*/, va_list /*ap*/); + /* Append the pointers from a variable-length argument list AP to AV. + * + * The list is terminated by a null pointer. + */ + extern EXECL_LIKE(0) void argv_appendl(struct argv */*av*/, ...); -extern void argv_prepend(struct argv */*av*/, const char */*p*/); + /* Append the argument pointers, terminated by a null pointer, to + * AV. + */ + +extern void argv_prepend(struct argv */*av*/, char */*p*/); + /* Prepend the pointer P to AV. */ + extern void argv_prependn(struct argv */*av*/, - const char *const */*v*/, size_t /*n*/); + char *const */*v*/, size_t /*n*/); + /* Prepend a N-element vector V of pointers to AV. */ + extern void argv_prependav(struct argv */*av*/, const struct argv */*bv*/); + /* Prepend the variable-length vector BV to AV. */ + extern void argv_prependv(struct argv */*av*/, va_list /*ap*/); + /* Prepend the pointers from a variable-length argument list AP to + * AV. + * + * The list is terminated by a null pointer. + */ + extern EXECL_LIKE(0) void argv_prependl(struct argv */*av*/, ...); + /* Prepend the argument pointers, terminated by a null pointer, to + * AV. + */ /*----- Treaps ------------------------------------------------------------*/ +/* A `treap' is a data structure for associating values with keys. This + * implementation assumes that keys are simply text strings. + */ struct treap { struct treap_node *root; }; #define TREAP_INIT { 0 } +/* A treap is a combination of a binary search tree and a binary heap. The + * nodes are ordered according to the search keys, in the usual way, so that + * all the keys in a node's left subtree precede that node's key, and all of + * the keys in its right subtree follow the node's key. The trick is that + * the tree must /also/ satisfy the heap condition regarding randomly + * assigned `weights' attached to each node: so a node's weight must not be + * less than their weight of either of its children. + * + * This combination uniquely determines the structure of the tree, except for + * nodes whose weights exactly match one (or both) of their children. (The + * root must be the heaviest node in the tree. The root's key splits the + * remaining nodes into left and right subtrees, whose structure is then + * uniquely determined by induction.) + * + * This is an /intrusive/ data structure. A caller is expected to include a + * `struct treap_node' as (probably) the initial part of a larger structure. + */ struct treap_node { - unsigned wt; - struct treap_node *left, *right; - char *k; size_t kn; + unsigned wt; /* weight (randomly assigned) */ + struct treap_node *left, *right; /* left and right subtrees */ + char *k; size_t kn; /* key pointer and length */ }; #define TREAP_NODE_KEY(n) (((const struct treap_node *)(n))->k + 0) #define TREAP_NODE_KEYLEN(n) (((const struct treap_node *)(n))->kn + 0) +/* We can't allocate nodes ourselves, because only the caller knows how. + * Instead, insertion is split into two operations: `treap_probe' looks to + * see whether a matching node is already in the treap, and returns it if so; + * otherwise, it flls in this `treap_path' structure, which is passed back to + * `treap_insert' to help it add the fresh node into the treap. (See the + * commentary in `treap_probe' and `treap_insert' for the details.) + */ #define TREAP_PATHMAX 64 struct treap_path { struct treap_node **path[TREAP_PATHMAX]; unsigned nsteps; }; +/* An external iterator for a treap. (See the commentary for + * `treap_start_iter' and `treap_next' for the details.) + */ struct treap_iter { struct treap_node *stack[TREAP_PATHMAX]; unsigned sp; }; extern void treap_init(struct treap */*t*/); + /* Initialize the treap T. + * + * Usually you'd use the static initializer `TREAP_INIT'. + */ + extern void *treap_lookup(const struct treap */*t*/, const char */*k*/, size_t /*kn*/); + /* Look up the KN-byte key K in the treap T. + * + * Return a pointer to the matching node if one was found, or null + * otherwise. + */ + extern void *treap_probe(struct treap */*t*/, const char */*k*/, size_t /*kn*/, struct treap_path */*p*/); + /* Look up the KN-byte K in the treap T, recording a path in P. + * + * This is similar to `treap_lookup', in that it returns the + * requested node if it already exists, or null otherwise, but it + * also records in P information to be used by `treap_insert' to + * insert a new node with the given key if it's not there already. + */ + extern void treap_insert(struct treap */*t*/, const struct treap_path */*p*/, struct treap_node */*n*/, const char */*k*/, size_t /*kn*/); + /* Insert a new node N into T, associating it with the KN-byte key K. + * + * Use the path data P, from `treap_probe', to help with insertion. + */ + extern void *treap_remove(struct treap */*t*/, const char */*k*/, size_t /*kn*/); + /* Remove the node with the KN-byte K from T. + * + * Return the address of the node we removed, or null if it couldn't + * be found. + */ + extern void treap_start_iter(struct treap */*t*/, struct treap_iter */*i*/); + /* Initialize an iterator I over T's nodes. */ + extern void *treap_next(struct treap_iter */*i*/); + /* Return the next node from I, in ascending order by key. + * + * If there are no more nodes, then return null. + */ + extern void treap_check(struct treap */*t*/); + /* Check the treap structure rules for T. */ + extern void treap_dump(struct treap */*t*/); + /* Dump the treap T to standard output, for debugging purposes. */ /*----- Configuration file parsing ----------------------------------------*/ +/* A configuration file. */ struct config { - struct treap sections; - struct config_section *head, **tail; - struct config_section *fallback; + struct treap sections; /* treap of sections */ + struct config_section *head, **tail; /* section list, in creation order */ + struct config_section *fallback; /* default parent section */ }; #define CONFIG_INIT { TREAP_INIT, 0, 0 } +/* A configuration section. */ struct config_section { - struct treap_node _node; - struct config_section *next; - struct config_section **parents; size_t nparents; - struct treap vars; - struct treap cache; + struct treap_node _node; /* treap intrustion */ + struct config_section *next; /* next section in creation order */ + struct config_section **parents; size_t nparents; /* vector of parents */ + struct treap vars; /* treap of variables */ + struct treap cache; /* inheritance cache */ }; #define CONFIG_SECTION_NAME(sect) TREAP_NODE_KEY(sect) #define CONFIG_SECTION_NAMELEN(sect) TREAP_NODE_KEYLEN(sect) +/* An entry in a section's inheritance cache: see `search_recursive' for + * details. + */ struct config_cache_entry { - struct treap_node _node; - unsigned f; -#define CF_OPEN 1u - struct config_var *var; + struct treap_node _node; /* treap intrusion */ + unsigned f; /* flags */ +#define CF_OPEN 1u /* traps inheritance cycles */ + struct config_var *var; /* pointer to inherited variable */ }; +/* A configuration variable. */ struct config_var { - struct treap_node _node; - char *file; unsigned line; - char *val; size_t n; - unsigned f; + struct treap_node _node; /* treap intrusion */ + char *file; unsigned line; /* source location, or null/0 */ + char *val; size_t n; /* value pointer and length */ + unsigned f; /* flags */ +#define CF_LITERAL 1u /* value should not be expanded */ +#define CF_EXPAND 2u /* traps expansion cycles */ +#define CF_OVERRIDE 4u /* override settings from files */ }; #define CONFIG_VAR_NAME(var) TREAP_NODE_KEY(var) #define CONFIG_VAR_NAMELEN(var) TREAP_NODE_KEYLEN(var) -#define CF_LITERAL 1u -#define CF_EXPAND 2u -#define CF_OVERRIDE 4u +/* A section iterator. + * + * (Sections are visited in the order in which they were created.) + */ struct config_section_iter { - struct config_section *sect; + struct config_section *sect; /* next section to return */ }; +/* A variable iterator. + * + * (Variables are visited in lexicographical order.) + */ struct config_var_iter { struct treap_iter i; }; +/* Common flags. */ +#define CF_CREAT 1u /* create section or variable */ +#define CF_INHERIT 2u /* look up variable in parents */ + extern void config_init(struct config */*conf*/); + /* Initialize the configuration state CONF. + * + * Usually you'd use the static initializer `CONFIG_INIT'. + */ extern struct config_section *config_find_section(struct config */*conf*/, unsigned /*f*/, const char */*name*/); + /* Find and return the section with null-terminated NAME in CONF. + * + * If no section is found, the behaviour depends on whether + * `CF_CREAT' is set in F: if so, an empty section is created and + * returned; otherwise, a null pointer is returned. + */ + extern struct config_section *config_find_section_n(struct config */*conf*/, unsigned /*f*/, const char */*name*/, size_t /*sz*/); -#define CF_CREAT 1u + /* Find and return the section with the given SZ-byte NAME in CONF. + * + * This works like `config_find_section', but with an explicit length + * for the NAME rather than null-termination. + */ extern void config_set_fallback(struct config */*conf*/, struct config_section */*sect*/); + /* Set the fallback section for CONF to be SECT. + * + * That is, if a section has no explicit parents, then by default it + * will have a single parent which is SECT. If SECT is null then + * there is no fallback section, and sections which don't have + * explicitly specified parents have no parents at all. (This is the + * default situation.) + */ + extern void config_set_parent(struct config_section */*sect*/, struct config_section */*parent*/); + /* Arrange that SECT has PARENT as its single parent section. + * + * If PARENT is null, then arrange that SECT has no parents at all. + * In either case, any `@parents' setting will be ignored. + */ extern void config_start_section_iter(struct config */*conf*/, struct config_section_iter */*i*/); + /* Initialize I to iterate over the sections defined in CONF. */ + extern struct config_section *config_next_section (struct config_section_iter */*i*/); + /* Return the next section from I, in order of creation. + * + * If there are no more sections, then return null. + */ extern struct config_var *config_find_var(struct config */*conf*/, struct config_section */*sect*/, unsigned /*f*/, const char */*name*/); + /* Find and return the variable with null-terminated NAME in SECT. + * + * If `CF_INHERIT' is set in F, then the function searches the + * section's parents recursively; otherwise, it only checks to see + * whether the variable is set directly in SECT. + * + * If no variable is found, the behaviour depends on whether + * `CF_CREAT' is set in F: if so, an empty variable is created and + * returned; otherwise, a null pointer is returned. + * + * Setting both `CF_INHERIT' and `CF_CREAT' is not useful. + */ + extern struct config_var *config_find_var_n(struct config */*conf*/, struct config_section */*sect*/, unsigned /*f*/, const char */*name*/, size_t /*sz*/); -#define CF_INHERIT 2u - -extern void config_set_var(struct config */*conf*/, - struct config_section */*sect*/, unsigned /*f*/, - const char */*name*/, const char */*value*/); -extern void config_set_var_n(struct config */*conf*/, - struct config_section */*sect*/, unsigned /*f*/, - const char */*name*/, size_t /*namelen*/, - const char */*value*/, size_t /*valuelen*/); -extern void config_start_var_iter(struct config_section */*sect*/, + /* Find and return the variable with the given SZ-byte NAME in SECT. + * + * This works like `config_find_var', but with an explicit length for + * the NAME rather than null-termination. + */ + +extern struct config_var *config_set_var(struct config */*conf*/, + struct config_section */*sect*/, + unsigned /*f*/, + const char */*name*/, + const char */*value*/); + /* Set variable NAME to VALUE in SECT, with associated flags F. + * + * The names are null-terminated. The flags are variable flags: see + * `struct config_var' for details. Returns the variable. + * + * If the variable is already set and has the `CF_OVERRIDE' flag, + * then this function does nothing unless `CF_OVERRIDE' is /also/ set + * in F. + */ + +extern struct config_var *config_set_var_n(struct config */*conf*/, + struct config_section */*sect*/, + unsigned /*f*/, + const char */*name*/, + size_t /*namelen*/, + const char */*value*/, + size_t /*valuelen*/); + /* As `config_set_var', except that the variable NAME and VALUE have + * explicit lengths (NAMELEN and VALUELEN, respectively) rather than + * being null- terminated. + */ + +extern void config_start_var_iter(struct config */*conf*/, + struct config_section */*sect*/, struct config_var_iter */*i*/); + /* Initialize I to iterate over the variables directly defined in + * SECT. + */ + extern struct config_var *config_next_var(struct config_var_iter */*i*/); + /* Return next variable from I, in ascending lexicographical order. + * + * If there are no more variables, then return null. + */ extern int config_read_file(struct config */*conf*/, const char */*file*/, unsigned /*f*/); -extern int config_read_dir(struct config */*conf*/, - const char */*dir*/, unsigned /*f*/); +#define CF_NOENTOK 1u + /* Read and parse configuration FILE, applying its settings to CONF. + * + * If all goes well, the function returns 0. If the file is not + * found, then the behaviour depends on whether `CF_NOENTOK' is set + * in F: if so, then the function simply returns -1. Otherwise, a + * fatal error is reported. Note that this /only/ applies if the + * file does not exist (specifically, opening it fails with `ENOENT') + * -- any other problems are reported as fatal errors regardless of + * the flag setting. + */ + extern void config_read_env(struct config */*conf*/, struct config_section */*sect*/); -#define CF_NOENTOK 1u + /* Populate SECT with environment variables. + * + * Environment variables are always set with `CF_LITERAL'. + */ extern void config_subst_string(struct config */*config*/, struct config_section */*home*/, const char */*what*/, const char */*p*/, struct dstr */*d*/); + /* Expand substitutions in a string. + * + * Expand the null-terminated string P relative to the HOME section, + * using configuration CONFIG, and appending the result to dynamic + * string D. Blame WHAT in any error messages. + */ + extern char *config_subst_string_alloc(struct config */*config*/, struct config_section */*home*/, const char */*what*/, const char */*p*/); + /* Expand substitutions in a string. + * + * Expand the null-terminated string P relative to the HOME section, + * using configuration CONFIG, returning the result as a freshly + * malloc(3)ed string. Blame WHAT in any error messages. + */ + extern void config_subst_var(struct config */*config*/, struct config_section */*home*/, struct config_var */*var*/, struct dstr */*d*/); + /* Expand substitutions in a variable. + * + * Expand the value of the variable VAR relative to the HOME section, + * using configuration CONFIG, appending the result to dynamic string + * D. + */ + extern char *config_subst_var_alloc(struct config */*config*/, struct config_section */*home*/, struct config_var */*var*/); + /* Expand substitutions in a variable. + * + * Expand the value of the variable VAR relative to the HOME section, + * using configuration CONFIG, returning the result as a freshly + * malloc(3)ed string. + */ + extern void config_subst_split_var(struct config */*config*/, struct config_section */*home*/, struct config_var */*var*/, struct argv */*av*/); + /* Expand substitutions in a variable and split into words. + * + * Expand and word-split the value of the variable VAR relative to + * the HOME section, using configuration CONFIG, appending the + * resulting words into the vector AV. + */ /*----- That's all, folks -------------------------------------------------*/