|
7c42945e
|
2019-11-13T22:41:38
|
|
parser: fix quadratic pointer chasing
In the AST, lists (e.g. the list of statements in a file) are kept in
singly-linked lists -- each AST node has a `next` pointer available for
this purpose.
Previously, a node was added to the list by starting from the head,
chasing to the last, and appending. So creating a list of length N would
take ~N^2/2 pointer dereferences.
Now, we always (temporarily) keep the last as well, so appending is O(1)
instead of O(N).
Given a keymap
xkb_keymap {
xkb_keycodes {
minimum = 8;
minimum = 8;
minimum = 8;
minimum = 8;
minimum = 8;
[... repeated N times ...]
};
xkb_types {};
xkb_compat {};
xkb_symbols {};
};
The compilation times are
N | Before | After
--------|----------|-------
10,000 | 0.407s | 0.006s
20,000 | 1.851s | 0.015s
30,000 | 5.737s | 0.021s
40,000 | 12.759s | 0.023s
50,000 | 21.489s | 0.035s
60,000 | 40.473s | 0.041s
70,000 | 53.336s | 0.039s
80,000 | 72.485s | 0.044s
90,000 | 94.703s | 0.048s
100,000 | 118.390s | 0.057s
Another option is to ditch the linked lists and use arrays instead. I
got it to work, but its more involved and allocation heavy so turns out
to be worse without further optimizations.
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
|
400cc849
|
2019-11-12T20:04:13
|
|
ast: use a separate expr struct for action list
Currently it's under UnaryExpr, which just doesn't make sense.
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
e3cacae7
|
2018-03-10T23:32:12
|
|
xkbcomp: fix crashes in the parser when geometry tokens appear
In the XKB format, floats and various keywords can only be used in the
xkb_geometry section. xkbcommon removed support xkb_geometry, but still
parses it for backward compatibility. As part of ignoring it, the float
AST node and various keywords were removed, and instead NULL was
returned by their parsing actions. However, the rest of the code does
not handle NULLs, and so when they appear crashes usually ensue.
To fix this, restore the float AST node and the ignored keywords. None
of the evaluating code expects them, so nice error are displayed.
Caught with the afl fuzzer.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
16aab829
|
2014-02-09T23:21:19
|
|
ast: remove unneeded 'ctx' param to XkbFileCreate
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
6ea15719
|
2014-02-08T01:26:35
|
|
ast: use more suitable types in a few ast nodes
The int ones cannot be signed (they come as such from the scanner, and
NEGATE is never applied to them).
The uint32_t one is really an atom, but presumably the type was never
converted to xkb_atom_t.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
b63fa3b1
|
2013-12-01T13:32:51
|
|
expr: make Expr creation naming and file location consistent
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
068016e4
|
2013-12-01T10:45:52
|
|
parser, symbols: drop unnecessary casts
It's casted into ExprDef and then uncasted for no reason.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
c24b6420
|
2013-11-30T23:24:18
|
|
expr: add constructor for boolean expressions
Also add a 'bool set' to the ExprDef union, instead of using 'ival' as a
bool.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
c5d85938
|
2013-11-30T23:12:45
|
|
expr: add constructors for more expression types
This makes the parser a bit more declarative. But really it might make
error handling easier.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
9dc5b8cb
|
2013-11-27T13:49:13
|
|
Resolve keysyms early in parser
Instead of having the parser passing strings to the AST, and
symbols/compat etc. resolving them themselves. This simplifies the code
a bit, and makes it possible to print where exactly in the file the bad
keysym originates from.
The previous lazy approach had an advantage of not needlessly resolving
keysyms from unrelated maps. However, I think reporting these errors in
*any* map is better, and the parser is also a bit smarter then old
xkbcomp and doesn't parse many useless maps. So there's no discernible
speed/memory difference with this change.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
044d4b5f
|
2013-11-08T17:08:35
|
|
Make XkbFileCreate argument types match between header & implementation
Fixes build failure with Solaris Studio compilers:
"src/xkbcomp/ast-build.c", line 492: identifier redeclared: XkbFileCreate
current : function(..., enum xkb_map_flags)
previous: function(..., unsigned int) : "src/xkbcomp/ast-build.h", line 98
Signed-off-by: Alan Coopersmith <alan.coopersmith@oracle.com>
|
|
|
8cee7490
|
2013-02-17T22:18:57
|
|
Change 'indicator' to 'led' everywhere possible
The code currently uses the two names interchangeably.
Settle on 'led', because it is shorter, more recognizable, and what we
use in our API (though of course the parser still uses 'indicator').
In camel case we make it 'Led'.
We change 'xkb_indicator_map' to just 'xkb_led' and the variables of
this type are 'led'. This mimics 'xkb_key' and 'key'.
IndicatorNameInfo and LEDInfo are changed to 'LedNameInfo' and
'LedInfo', and the variables are 'ledi' (like 'keyi' etc.). This is
instead of 'ii' and 'im'.
This might make a few places a bit confusing, but less than before I
think. It's also shorter.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
41a7fed3
|
2012-09-27T19:21:26
|
|
Fix type of keycode in parser and ast
For some reason keycodes were listed under mapFlags in the yylval union.
Fix it and some sanity checks.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
3b389b15
|
2012-09-27T18:49:13
|
|
Don't limit key names to 4 characters
Currently you can't give a key in xkb_keycodes a name of more than
XKB_KEY_NAME_LENGTH (= 4) chars. This is a pretty annoying and arbitrary
limitation; it leads to names such as <RTSH>, <COMP>, <PRSC>, <KPAD>
etc. which may be hard to decipher, and makes it impossible to give
more standard names (e.g. from linux/input.h) to keycodes.
The purpose of this, as far as I can tell, was to save memory and to
allow encoding a key name directly to a 32 bit value (unsigned long it
was).
We remove this limitation by just storing the names as atoms; this lifts
the limit, allows for easy comparison like the unsigned long thing, and
doesn't use more memory than previous solution. It also relieves us from
doing all of the annoying conversions to/from long.
This has a large diffstat only because KeyNameText, which is used a lot,
now needs to take the context in order to resolve the atom.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
f5dffd2b
|
2012-08-21T11:21:19
|
|
kbproto untanglement: XkbKeyNameLength
Define it ourselves as XKB_KEY_NAME_LENGTH and use that, instead of the
one from XKB.h.
Signed-off-by: Daniel Stone <daniel@fooishbar.org>
|
|
|
cdc228ea
|
2012-08-13T11:00:43
|
|
Organize xkbcomp/ header files
Various non-functional changes:
- Re-add keycodes.h and move some stuff there.
- Add parser-priv.h for internal bison/flex stuff.
- Don't include headers from other headers, such that file dependencies
are immediate in each file.
- Rename xkbcomp.h -> ast.h, parseutils.{c,h} -> ast-build.{c,h}
- Rename path.{c,h} -> include.{c,h}
- Rename keytypes.c -> types.c
- Make the naming of XkbFile-related functions more consistent.
- Move xkb_map_{new,ref,unref} to map.c.
- Remove most extern keyword from function declarations, it's just
noise (XKB_EXPORT is what's important here).
- Append XKBCOMP_ to include guards.
- Shuffle some code around to make all of this work.
Splitting this would be a headache..
Signed-off-by: Ran Benita <ran234@gmail.com>
|