summaryrefslogtreecommitdiff
path: root/base
Commit message (Collapse)AuthorAgeFilesLines
* gcc: use more zero length arraysZdenek Kabelac2021-09-221-1/+1
| | | | Define last array struct member with zero size.
* hash: replace hash with better functionZdenek Kabelac2021-03-081-18/+74
| | | | | | | | | | 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.
* hash: speed up hash tablesZdenek Kabelac2021-03-081-32/+58
| | | | | | | | | | | | | | | 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.)
* hash: use unsigned sizeZdenek Kabelac2021-03-081-3/+3
| | | | | There is not much point in using 64bit hash size, since we hash with way less bits anyway. So keep size 32bit.
* cleanup: better expressing passing key arg to _hashZdenek Kabelac2020-09-011-4/+5
|
* cov: explicitely ignore function resultZdenek Kabelac2020-09-011-1/+1
|
* gcc: zero-sized array to fexlible array C99Zdenek Kabelac2020-09-012-2/+2
| | | | | | | | | | | | | | 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.
* container_of: drop needless const converionZdenek Kabelac2020-08-281-1/+1
|
* list: use container_ofZdenek Kabelac2020-05-201-2/+2
| | | | Reuse macro
* container_of: use offsetof from stddefZdenek Kabelac2020-03-051-2/+4
| | | | | Use standardized offsetof() macro from stddef. Helps to build valid code with latest gcc10 with -O2.
* libdm: fix dm_list pointer arithmentic for new gcc 10 optimizationZdenek Kabelac2020-03-051-2/+4
|
* configure: avoid repeative inclusion of configure.hZdenek Kabelac2018-12-212-3/+0
| | | | | | | | | | 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.
* makefiles: correcting login of makefileZdenek Kabelac2018-12-171-13/+8
| | | | | | Fixing some ordering issue with inclusion of common make.tmpl. Correcting dependency calculation Simplifying inclusive makefile
* makefiles: sortZdenek Kabelac2018-12-171-2/+2
|
* headers: use configure.h as 1st. headerZdenek Kabelac2018-12-143-1/+4
| | | | | | | | | | | 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.
* gcc: avoid shadowing indexZdenek Kabelac2018-12-011-5/+5
| | | | | Some older headers were declaring 'index' so avoid its usage. /usr/include/string.h:489: warning: shadowed declaration is here
* makefiles: improving cleaning rulesZdenek Kabelac2018-11-291-5/+7
|
* makefiles: avoid dependency calcs for base dirZdenek Kabelac2018-11-291-1/+9
| | | | | | | 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.
* base: use callocZdenek Kabelac2018-11-291-4/+1
| | | | Make zalloc a wrapper over calloc
* cov: mark warning as expected oneZdenek Kabelac2018-11-031-0/+1
|
* cov: overflow before widenZdenek Kabelac2018-11-031-1/+1
| | | | | Evaluate as 64bit arithmetic (instead of doing 32bit mults which can in this case purely teoretically overflow).
* cov: add at least ASSERTZdenek Kabelac2018-10-151-0/+6
| | | | | Seems lot of code here can't handle failing allocation. Meanwhile before bigger fix put in asserts in place.
* cov: fix missing null allocation checkZdenek Kabelac2018-10-151-1/+2
|
* Merge branch '2018-09-13-radix-tree-bug'Joe Thornber2018-09-202-12/+38
|\
| * [build] switch back to the adaptive radix treeJoe Thornber2018-09-201-1/+1
| |
| * [radix-tree] tidy up _degrade_to_n48Joe Thornber2018-09-201-6/+6
| | | | | | | | Shouldn't be any functional changes.
| * [radix-tree] Fix bug in _degrade_to_n16Joe Thornber2018-09-201-2/+1
| | | | | | | | Values were getting shuffled
| * [radix-tree] Fix bug in _dumpJoe Thornber2018-09-201-3/+4
| | | | | | | | Values in an n48 were not being printed in the correct order.
| * [radix-tree] Add some extra checks to is_well_formed()Joe Thornber2018-09-201-0/+26
| |
* | radix-tree: default to simple versionDavid Teigland2018-09-171-1/+2
|/ | | | Avoid problems with the advanced version.
* [radix-tree] alternative radix-tree implementation.Joe Thornber2018-09-114-1246/+1526
| | | | | Sacrifices performance for simplicity, meant only for verification of the real adaptive implementation.
* radix-tree: Fix bug in remove_prefix()Joe Thornber2018-08-201-0/+3
| | | | | Accidental decrement of the nr entries when a n256 didn't have the entry in the first place.
* radix-tree: squash a pointer arithmetic warningJoe Thornber2018-06-211-1/+1
|
* radix-tree: fix bug when erasing elts in remove_prefixJoe Thornber2018-06-211-6/+6
| | | | | _erase_elt() now zeroes the last element of the array (ie. sets to UNSET). Previously remove() was doing this, but not remove_prefix().
* radix-tree: More debugging of removeJoe Thornber2018-06-212-17/+142
| | | | | | | There's now a pretty printer called radix_tree_dump() n4, n16, and n48 weren't UNSETting the last entry after sliding values down.
* radix-tree: FIx various bugs to do with removalJoe Thornber2018-06-212-34/+312
| | | | | | | | | 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.
* device_mapper: move hash.[hc] to base/data-structJoe Thornber2018-06-083-0/+489
|
* base: Move list to base/data-structJoe Thornber2018-06-083-0/+380
|
* build: base/MakefileJoe Thornber2018-06-041-0/+29
| | | | .gitignore hid it.
* radix-tree: fix some bugs in remove_prefix and iterateJoe Thornber2018-05-301-2/+20
| | | | These weren't working if the prefix key was part of a prefix_chain.
* radix-tree: radix_tree_iterate()Joe Thornber2018-05-292-35/+119
|
* radix-tree: radix_tree_remove_prefix()Joe Thornber2018-05-292-8/+29
|
* radix-tree: call the value dtr when removing an entry.Joe Thornber2018-05-291-20/+26
|
* Merge branch '2018-05-29-radix-tree-iterate' into 2018-05-23-radix-tree-removeJoe Thornber2018-05-292-7/+10
|\
| * data-struct/radix-tree: pass the value dtr into create.Joe Thornber2018-05-292-7/+10
| | | | | | | | Rather than having to pass it into every method that removes items.
* | radix_tree: add remove methodJoe Thornber2018-05-232-6/+181
|/
* radix-tree: remove some unneccessary includesJoe Thornber2018-05-111-3/+0
|
* radix-tree: First drop of radix tree.Joe Thornber2018-05-114-0/+670
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.
View Lorry Controller Status