| Commit message (Collapse) | Author | Age | Files | Lines |
|
|
|
| |
Define last array struct member with zero size.
|
|
|
|
|
|
|
|
|
|
| |
Add Bob Jenkins hash function to get better working hash function,
which does genarate way less colisions (especially with similar
strings).
For a comparision also a kernel function used in DM kernel is include.
While it's better then our existing one, it's still far worse,
then Bob Jenkins hash.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Enhance hash perfomance by remembering the computed
hash value for the hashed node - this allows to speedup
lookup of nodes with the hash collision when
different keys map to the same masked hash value.
For the easier use 'num_slots' become 'mask_slots',
so we only add '1' in rare case of need of the original
num_slots value.
Also add statistic counters for hashes and print stats in
debug build (-DDEBUG) on hash wiping.
(so badly performing hash can be optimized.)
|
|
|
|
|
| |
There is not much point in using 64bit hash size, since we hash
with way less bits anyway. So keep size 32bit.
|
| |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Switch remaining zero sized struct to flexible arrays to be C99
complient.
These simple rules should apply:
- The incomplete array type must be the last element within the structure.
- There cannot be an array of structures that contain a flexible array member.
- Structures that contain a flexible array member cannot be used as a member of another structure.
- The structure must contain at least one named member in addition to the flexible array member.
Although some of the code pieces should be still improved.
|
| |
|
|
|
|
| |
Reuse macro
|
|
|
|
|
| |
Use standardized offsetof() macro from stddef.
Helps to build valid code with latest gcc10 with -O2.
|
| |
|
|
|
|
|
|
|
|
|
|
| |
Since configure.h is a generated header and it's missing traditional
ifdefs preambule - it can be included & parsed multiple times.
Normally compiler is fine when defines have same value and there is
no warning - yet we don't need to parse this several times
and by adding -include directive we can ensure every file
in the package is rightly compile with configure.h as the
first header file.
|
|
|
|
|
|
| |
Fixing some ordering issue with inclusion of common make.tmpl.
Correcting dependency calculation
Simplifying inclusive makefile
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
Ensure configure.h is always 1st. included header.
Maybe we could eventually introduce gcc -include option, but for now
this better uses dependency tracking.
Also move _REENTRANT and _GNU_SOURCE into configure.h so it
doesn't need to be present in various source files.
This ensures consistent compilation of headers like stdio.h since
it may produce different declaration.
|
|
|
|
|
| |
Some older headers were declaring 'index' so avoid its usage.
/usr/include/string.h:489: warning: shadowed declaration is here
|
| |
|
|
|
|
|
|
|
| |
For some targets we do not want to generate dependencies.
Also add note about usage of such Makefile - it might be
possibly better to rename it to different filename to avoid
any confusion.
|
|
|
|
| |
Make zalloc a wrapper over calloc
|
| |
|
|
|
|
|
| |
Evaluate as 64bit arithmetic (instead of doing 32bit mults which can
in this case purely teoretically overflow).
|
|
|
|
|
| |
Seems lot of code here can't handle failing allocation.
Meanwhile before bigger fix put in asserts in place.
|
| |
|
|\ |
|
| | |
|
| |
| |
| |
| | |
Shouldn't be any functional changes.
|
| |
| |
| |
| | |
Values were getting shuffled
|
| |
| |
| |
| | |
Values in an n48 were not being printed in the correct order.
|
| | |
|
|/
|
|
| |
Avoid problems with the advanced version.
|
|
|
|
|
| |
Sacrifices performance for simplicity, meant only for verification of
the real adaptive implementation.
|
|
|
|
|
| |
Accidental decrement of the nr entries when a n256 didn't have the
entry in the first place.
|
| |
|
|
|
|
|
| |
_erase_elt() now zeroes the last element of the array (ie. sets to
UNSET). Previously remove() was doing this, but not remove_prefix().
|
|
|
|
|
|
|
| |
There's now a pretty printer called radix_tree_dump()
n4, n16, and n48 weren't UNSETting the last entry after
sliding values down.
|
|
|
|
|
|
|
|
|
| |
Add radix_tree_is_well_formed() which does some sanity checking
of the tree.
Call the above a lot in the unit tests.
Fix revealed bugs.
|
| |
|
| |
|
|
|
|
| |
.gitignore hid it.
|
|
|
|
| |
These weren't working if the prefix key was part of a prefix_chain.
|
| |
|
| |
|
| |
|
|\ |
|
| |
| |
| |
| | |
Rather than having to pass it into every method that removes items.
|
|/ |
|
| |
|
|
An implementation of an adaptive radix tree. Has the following nice
properties:
- At least as fast as the hash table
- Uses less memory
- You don't need to give an expected size when you create
- It scales nicely (ie. no large reallocations like the hash table).
- You can iterate the keys in lexicographical order.
Only insert and lookup are implemented so far. Plus there's a lot
more performance to come.
|