/*
* Character classes and character maps
* Copyright
* (C) 2015 Joseph H. Allen
*
* This file is part of JOE (Joe's Own Editor)
*/
/* An interval. A character matches if it's in the range.
An array of these can be used to define a character class. */
struct interval {
int first;
int last;
};
/* Sort an struct interval array */
void interval_sort(struct interval *array, ptrdiff_t size);
/* Test if character is in a sorted interval array using binary search.
Returns -1 if not found, or index to matching struct interval */
ptrdiff_t interval_test(struct interval *array, ptrdiff_t size, int ch);
/* An interval list item. This is one implementation of character -> pointer maps. */
struct interval_list {
struct interval_list *next; /* Next item in list */
struct interval interval; /* Range of characters */
void *map;
};
struct interval_list *mkinterval(struct interval_list *next, int first, int last, void *map);
void rminterval(struct interval_list *item);
/* Add a single interval to an interval list */
struct interval_list *interval_add(struct interval_list *interval_list, int first, int last, void *map);
/* Add set of intervals (a character class) to an interval list */
struct interval_list *interval_set(struct interval_list *list, struct interval *array, int size, void *map);
/* Look up single character in an interval list, return what it's mapped to */
void *interval_lookup(struct interval_list *list, void *dflt, int ch);
/* Show an interval list */
void interval_show(struct interval_list *list);
/* A character classes and maps implemented as radix trees */
#define LEAFSIZE 16
#define LEAFMASK 0xF
#define LEAFSHIFT 0
#define THIRDSIZE 32
#define THIRDMASK 0x1f
#define THIRDSHIFT 4
#define SECONDSIZE 32
#define SECONDMASK 0x1f
#define SECONDSHIFT 9
#define TOPSIZE 68
#define TOPMASK 0x7f
#define TOPSHIFT 14
struct First {
short entry[TOPSIZE];
};
struct Mid {
short entry[SECONDSIZE]; /* THIRDSIZE too */
};
struct Leaf {
void *entry[LEAFSIZE];
int refcount; /* No. references */
};
struct Ileaf {
int entry[LEAFSIZE];
int refcount;
};
struct Level {
int alloc; /* Allocation index */
int size; /* Malloc size */
union {
struct Mid *b;
struct Mid *c;
struct Leaf *d;
struct Ileaf *e;
} table;
};
/* A radix tree bit-map for character classes */
struct Rset {
struct First top;
struct Level second;
struct Mid mid;
struct Level third;
};
void rset_init(struct Rset *r);
void rset_clr(struct Rset *r);
int rset_lookup(struct Rset *r, int ch);
int rset_lookup_unopt(struct Rset *r, int ch);
void rset_add(struct Rset *r, int ch, int che);
void rset_opt(struct Rset *r);
void rset_set(struct Rset *r, struct interval *array, ptrdiff_t size);
void rset_show(struct Rset *r);
/* A radix tree map: (Unicode character) -> (void *) or (Unicode character) -> (int) */
struct Rtree {
struct First top;
struct Level second;
struct Mid mid;
struct Level third;
struct Level leaf;
};
/* Functions for character -> pointer maps */
void rtree_init(struct Rtree *r);
void rtree_clr(struct Rtree *r);
void *rtree_lookup(struct Rtree *r, int ch);
void *rtree_lookup_unopt(struct Rtree *r, int ch);
void rtree_add(struct Rtree *r, int ch, int che, void *map);
void rtree_opt(struct Rtree *r);
void rtree_set(struct Rtree *r, struct interval *array, ptrdiff_t len, void *map);
void rtree_build(struct Rtree *r, struct interval_list *l);
void rtree_show(struct Rtree *r);
/* Functions for character -> int maps */
void rmap_init(struct Rtree *r);
void rmap_clr(struct Rtree *r);
int rmap_lookup(struct Rtree *r, int ch, int dflt);
int rmap_lookup_unopt(struct Rtree *r, int ch, int dflt);
void rmap_add(struct Rtree *r, int ch, int che, int map, int dflt);
void rmap_opt(struct Rtree *r);
void rmap_set(struct Rtree *r, struct interval *array, ptrdiff_t len, int map, int dflt);
void rmap_show(struct Rtree *r);
/* A character class */
struct Cclass {
ptrdiff_t size; /* Malloc size of intervals */
ptrdiff_t len; /* Number of entries in intervals */
struct interval *intervals; /* sorted, non-overlapping, non-adjacent */
struct Rset rset[1]; /* Radix tree version of character class */
};
/* Initialize a character class */
void cclass_init(struct Cclass *cclass);
/* Free memory used by a Cclass (does not free cclass itself) */
void cclass_clr(struct Cclass *cclass);
/* Add a range to a character class */
void cclass_add(struct Cclass *cclass, int first, int last);
/* Remove a range to a character class */
void cclass_sub(struct Cclass *cclass, int first, int last);
/* Merge one character class into another */
void cclass_union(struct Cclass *cclass, struct Cclass *n);
void cclass_merge(struct Cclass *cclass, struct interval *intervals, int len);
/* Subtract one character class from another */
void cclass_diff(struct Cclass *cclass, struct Cclass *n);
/* Compute inverse of a character class */
void cclass_inv(struct Cclass *cclass);
/* Lookup a character in a character class using binary search.
Return true if character is in the class. */
int cclass_lookup_unopt(struct Cclass *m, int ch);
/* Optimize a character class for fast lookup with cclass_lookup. Generates a radix tree
version of the character class. */
void cclass_opt(struct Cclass *cclass);
/* Return true if character is in the class */
int cclass_lookup(struct Cclass *cclass, int ch);
void cclass_show(struct Cclass *cclass);
/* Remap a character class */
struct Cclass *cclass_remap(struct Cclass *m, struct charmap *map);
