|
16fe837d
|
2019-11-02T16:19:32
|
|
atom: rewrite as a hash table
While the previous 1987-style[0] scheme was fun (and I reasonably
optimized it for a fair comparison), this task is more suited to a hash
table. Even a simple implementation beats the old one.
[0] Seems to have first appeared in X11R1, released September 1987.
See server/dix/atom.c here: https://www.x.org/releases/X11R1/X.V11R1.tar.gz
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
|
40aab05e
|
2019-12-27T13:03:20
|
|
build: include config.h manually
Previously we included it with an `-include` compiler directive. But
that's not portable. And it's better to be explicit anyway.
Every .c file should have `include "config.h"` first thing.
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
|
4849bc19
|
2019-11-09T22:07:15
|
|
atom: a string is greater than its prefix
Bug accidentally introduced in 9a92b46.
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
|
c79c8033
|
2019-11-09T21:25:01
|
|
atom: combine atom_intern() and atom_lookup()
Use an "add" bool parameter instead. This simplifies the code a bit.
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
|
adbd9c6f
|
2019-11-09T13:47:16
|
|
atom: correct iteration count in hash function
Fixup of ccab349 - unlike the commit message, hash a byte twice instead
of zero times, which is probably better. This is how it was before.
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
|
9ebf97d7
|
2019-11-09T13:12:02
|
|
atom: describe how this odd data structure works
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
|
ccab349c
|
2019-11-09T12:43:04
|
|
atom: use a better hash function
FNV-1a instead of the djb2-like one from before.
Keep the unrolling since it seems quite beneficial, even though it loses
one byte if the length is odd...
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
|
9a92b464
|
2019-11-09T11:49:25
|
|
atom: style changes
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
|
1fe1b653
|
2019-11-09T11:39:17
|
|
atom: remove handling of garbage input
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
|
a5f95c2b
|
2019-11-09T11:33:45
|
|
atom: use explicit size for fingerprint
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
|
8ea4a001
|
2019-11-09T00:20:45
|
|
atom: replace an avoidable strlen
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
|
6f8bb5ee
|
2019-11-09T00:05:59
|
|
atom: remove redundant field
The field is redundant.
Due to alignment, this will only save memory on 32bit architectures.
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
|
2af474e8
|
2019-11-02T13:31:44
|
|
parser: get rid of "stealing" atoms
This requires (well, at least implemented by) casting away `const` which
is undefined behavior, and clang started to warn about it.
The micro optimization didn't save too many allocations, anyway.
Signed-off-by: Ran Benita <ran@unusedvar.com>
|
|
9a3c115b
|
2013-12-02T17:13:50
|
|
atom: don't malloc every node separately
Instead of having a darray of pointers to malloc'ed atom_node's, make it
a darray of atom_node's directly.
This makes the code a bit simpler, saves on some malloc's, and the
memory gain/loss even out.
Unfortunately, we are no longer Three Star Programmers ;(
http://c2.com/cgi/wiki?ThreeStarProgrammer
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
1374b50e
|
2013-12-02T14:25:51
|
|
atom: tiny style fixes
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
048ee703
|
2013-12-02T14:23:59
|
|
atom: allow passing NULLs to find_node_pointer()
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
d873693b
|
2013-12-02T14:15:58
|
|
atom: allow interning empty string
Which is different than XKB_ATOM_NONE, as in "" != NULL.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
58345f4e
|
2013-12-02T14:14:41
|
|
atom: drop {xkb_,}atom_strdup
Even though in 112cccb18ad1bc877b3c4a87fa536ea085c761b5 I said it might
be useful, it's not. So remove it.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
c00ea5ff
|
2013-07-22T10:51:22
|
|
atom: really work with non-NUL-terminated strings
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
7e0ae4b4
|
2013-07-21T16:41:27
|
|
atom: allow interning non-NUL-terminated strings
We need this later. The strlen was calculated anyway, so no loss here.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
9cd29453
|
2013-07-21T16:32:21
|
|
atom: expand variable names
A bit easier to understand at a glance.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
b2110705
|
2012-09-16T14:45:32
|
|
Organize src/ and test/ headers
- Add context.h and move context-related functions from xkb-priv.h to
it.
- Move xkb_context definition back to context.c.
- Add keysym.h and move keysym upper/lower/keypad from xkb-priv.h to it.
- Rename xkb-priv.h to map.h since it only contains keymap-related
definitions and declarations now.
- Remove unnecessary includes and some and some other small cleanups.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
7aa31097
|
2012-08-31T18:52:26
|
|
atom: add xkb_atom_lookup
This will only lookup the string and return the atom if found; it will
not intern it if not. This is useful when e.g. getting a string from the
user (which may be arbitrary) and comparing against atoms.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
651e1dab
|
2012-08-31T18:47:28
|
|
atom: separate lookup logic from atom_intern
This would allow us to add a non-interning xkb_atom_lookup function.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
f205d0f9
|
2012-08-31T18:22:03
|
|
atom: make type and name of the 'a' field clearer
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
89723b7c
|
2012-07-24T19:54:14
|
|
utils: add/replace string equality macros
It's more tidy and less error prone, since we use strcasecmp == 0 a lot.
We replace strcmp == 0 by streq, strcasecmp == 0 by istreq,
uStrCasePrefix by istreq_prefix and uDupString by strdup_safe.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
112cccb1
|
2012-07-23T16:03:34
|
|
Some atom related optimizations
We often get a strdup'd string, just to pass it over the atom_intern and
then immediately free it. But atom_intern then strdup's it again (if
it's not interned already); so instead we can have the interning "steal"
the memory instead of allocing a new one and freeing the old one. This
is done by a new xkb_atom_steal function.
It also turns out, that every time we strdup an atom, we don't actually
modify it afterwards. Since we are guaranteed that the atom table will
live as long as the context, we can just use xkb_atom_text instead. This
removes a some more dynamic allocations.
For this change we had to remove the ability to append two strings, e.g.
"foo" + "bar" -> "foobar"
which is only possible with string literals. This is unused and quite
useless for our purposes.
xkb_atom_strdup is left unused, as it may still be useful.
Running rulescomp in valgrind, Before:
==7907== total heap usage: 173,698 allocs, 173,698 frees, 9,775,973 bytes allocated
After:
==6348== total heap usage: 168,403 allocs, 168,403 frees, 9,732,648 bytes allocated
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
9308a460
|
2012-07-17T10:20:15
|
|
Run source tree through uncrustify
.uncrustify.cfg committed for future reference also, but had to manually
fix up a few things: it really likes justifying struct initialisers.
Signed-off-by: Daniel Stone <daniel@fooishbar.org>
|
|
|
57f184e2
|
2012-05-30T15:55:21
|
|
darray: tweak parameters a bit for better memory usage
Here are some quick numbers from valgrind, running rulescomp only with a
simple, common "us,de" rule set:
before darray: cb047bb
total heap usage: 44,924 allocs, 44,924 frees, 3,162,342 bytes allocated
after darray: c87468e
total heap usage: 52,670 allocs, 52,670 frees, 2,844,517 bytes allocated
tweaking specific inital allocation sizes:
total heap usage: 52,652 allocs, 52,652 frees, 2,841,814 bytes allocated
changing initial alloc = 2 globally
total heap usage: 47,802 allocs, 47,802 frees, 2,833,614 bytes allocated
changing initial alloc = 3 globally
total heap usage: 47,346 allocs, 47,346 frees, 3,307,110 bytes allocated
changing initial alloc = 4 globally
total heap usage: 44,643 allocs, 44,643 frees, 2,853,646 bytes allocated
[ Changing the geometric progression constant from 2 only made things
worse. I tried the golden ratio - not so golden :) ]
The last one is obviously the best, so it was chosen, with the specific
tweaks thrown in as well (these were there before but don't make much
difference). Overall it seems to do better than the previous manual
allocations which is a bit surprising.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
ef51b572
|
2012-05-22T00:26:58
|
|
atom: use darray for the node_table
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
699a0b84
|
2012-05-09T14:02:26
|
|
Contextualize the atom table
Each context gets its own table, i.e. interning a string in one context
does not affect any other context.
The existing xkb_atom_* functions are turned into wrappers around a new
standalone atom_table object.
Signed-off-by: Ran Benita <ran234@gmail.com>
[daniels: Updated for xkb -> keymap.]
|
|
|
cdd2906d
|
2012-05-09T13:50:05
|
|
Make the context available for XkbcAtomText
And rename the function to xkb_atom_text.
Signed-off-by: Ran Benita <ran234@gmail.com>
[daniels: Updated for xkb -> keymap.]
|
|
|
8d680e80
|
2012-05-09T12:01:03
|
|
Make the context available for XkbcAtomGetString
In preparation of contextualizing atom handling.
Since we touch every function call, we also rename the function to
xkb_atom_strdup to match xkb_atom_intern, and be more descriptive.
Signed-off-by: Ran Benita <ran234@gmail.com>
[daniels: Updated for xkb -> keymap.]
|
|
|
c117318f
|
2012-05-09T11:47:20
|
|
Make the context available to xkb_intern_atom
In preparation of contextualizing the atom table.
Since we touch every function call, also rename the function to
xkb_atom_intern, to match better with the rest (which will also be
renamed).
Signed-off-by: Ran Benita <ran234@gmail.com>
[daniels: Fixed for 'xkb' -> 'keymap'.]
|
|
|
b610b2b9
|
2012-05-08T14:52:23
|
|
Rename XKBcommonint.h to xkb-priv.h and use it
Make the files in the src/* directory use their own header or a
consilidated private header. This makes the file dependencies clearer.
Also drop the pointless "xkb" file name prefix, add split a few
declarations to their own files (atom.h and text.h).
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
8fbd44fd
|
2012-04-06T03:12:50
|
|
Implicitly include config.h in all files
The definitions in config.h should be available in all files an
implementation detail; it can be included through the build system
instead of having each file pull it every time.
This is especially helpful with AC_USE_SYSTEM_EXTENSIONS, as _GNU_SOURCE
and friends can have an effect by merely being defined, which can lead
to some confusion if its effective for only half the files.
And we don't really support a build _without_ config.h; so, one less
thing to worry about.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
3c949379
|
2012-03-31T00:02:12
|
|
Fix bugs to allow multiple keymaps in one process
These were several initializations that were forgotten in the previous
memory leak fixes.
Now several xkb_desc's can coexist (relatively) peacefully.
Signed-off-by: Ran Benita <ran234@gmail.com>
[daniels: Only the atom.c is relevant with the new context API.]
|
|
|
ffb610c9
|
2012-03-31T02:26:24
|
|
Remove useless check from xkb_intern_atom
The "makeit" variable is always true. Remove it and de-indent.
(Also change the type of the "len" variable to size_t to avoid some
useless casting).
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
d3908b63
|
2012-03-24T12:33:28
|
|
Define our own None atom value
Since we define our own xkb_atom_t type, it makes sense not to use the
X11/X.h None value. This way we can also remove a lot of X11 includes.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
d67a94d3
|
2012-03-09T18:57:14
|
|
Remove atom functions from public API
They're no longer needed since we don't expose any atoms in the
published API anymore. As a result, we don't need to support external
atom implementations either. Result!
Signed-off-by: Daniel Stone <daniel@fooishbar.org>
|
|
|
a0e756fd
|
2012-03-09T19:09:25
|
|
Introduce xkb_atom_t type
Signed-off-by: Daniel Stone <daniel@fooishbar.org>
|
|
|
19e99bb2
|
2012-03-01T20:41:34
|
|
Free all atoms along with keymap
The code to do this is taken from xserver, dix/atom.c.
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
266dfae5
|
2012-02-29T21:26:28
|
|
Remove useless casts
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
a3e40917
|
2012-03-01T23:43:51
|
|
Remove return's at the end of void functions
Signed-off-by: Ran Benita <ran234@gmail.com>
|
|
|
ead9d0cb
|
2012-02-15T11:49:10
|
|
Move include path from X11/extensions/ to xkbcommon/
Signed-off-by: Daniel Stone <daniel@fooishbar.org>
|
|
a63e82be
|
2010-12-17T21:14:54
|
|
Rename XkbcInternAtom() to xkb_intern_atom() and export
Signed-off-by: Kristian Høgsberg <krh@bitplanet.net>
|
|
73ca959d
|
2010-09-27T16:05:52
|
|
Dead code removal and static markup
Signed-off-by: Adam Jackson <ajax@redhat.com>
|
|
|
3f0034a9
|
2010-07-02T11:50:01
|
|
Rename public entry points to lowercase and underscore
|
|
|
e10e16ad
|
2010-06-30T17:20:56
|
|
Constify XkbcAtomText()
Atoms aren't mutable and this lets us put tbGetBuffer() back in the box.
|
|
|
d95b2893
|
2010-06-30T17:13:21
|
|
Make XkbcInitAtoms() call optional
|
|
|
0ece2cdb
|
2010-06-30T16:56:24
|
|
Drop more malloc/free wrappers
|
|
|
47d3b396
|
2010-06-28T06:50:12
|
|
Drop CARD32 and Opaque types
|
|
|
2c4a045a
|
2010-06-21T14:22:26
|
|
Allow external atom databases
Allow people to plug in an external atom database (e.g. the X server's),
so we don't have to migrate our own atoms over later. We are a bit
over-keen on atoms at the moment, so it does pollute the atom database a
bit though.
Signed-off-by: Daniel Stone <daniel@fooishbar.org>
|
|
|
48baabeb
|
2010-06-15T19:30:30
|
|
Atoms: Avoid allocations in XkbAtomText()
XkbAtomGetString() returns a freshly-allocated string, whereas
XkbAtomText() returns the same in a temporary buffer. XkbAtomText used
to call XkbAtomGetString() and then free the result, which seems quite
spectacularly pointless when you think about it. Shuffle the atom code
around so we don't have to allocate for XkbAtomText().
This changes semantics slightly wrt non-printable characters, but I
haven't been able to see any effect so far. And it may well be ever so
slightly quicker.
Signed-off-by: Daniel Stone <daniel@fooishbar.org>
|
|
6a84a34d
|
2009-04-08T07:46:25
|
|
Remove all non-public API from XKBcommon.h header
The noble intention was to expose all the new API and new generic types
in the split out kbproto headers through XKBcommon.h. It turns out that
would be a massive amount of work in the server. Someday, but first just
wedging in XkbCompileKeymap* would be good.
Most of the API is in new internal xkb*.h headers. In order to allow the
XKBcommon.h header to be used from the server, we can't pull in other
headers from kbproto since the server has its own copies. However, types
that are different (XkbDescRec, XkbAction) still have Xkbc equivalents
here, and I think they should be used in the server.
|
|
|
433a405c
|
2009-03-25T19:17:33
|
|
atom: Coding-style cleanup and refactor
Some coding style nits were cleaned up. Additionally, most of the
functions have been collapsed from the libxkbfile version where there's
distinction with the Xlib atom functions when Display was set. Finally,
the InitAtoms function tests whether the table has already been created
by testing the pointer rather than using a static int.
|
|
|
c88c0ba7
|
2009-03-25T19:00:49
|
|
Borrow atom implementation from libxkbfile
We need an atom implementation not relying on XInternAtom and friends.
The original code is in
libxkbfile/src/xkbatom.c
|