c-ares / c-ares / #32

92%

push

travis-ci

Modernization: Implement base data-structures and replace usage (#540)

c-ares currently lacks modern data structures that can make coding easier and more efficient. This PR implements a new linked list, skip list (sorted linked list), and hashtable implementation that are easy to use and hard to misuse. Though these implementations use more memory allocations than the prior implementation, the ability to more rapidly iterate on the codebase is a bigger win than any marginal performance difference (which is unlikely to be visible, modern systems are much more powerful than when c-ares was initially created).

The data structure implementation favors readability and audit-ability over performance, however using the algorithmically correct data type for the purpose should offset any perceived losses.

The primary motivation for this PR is to facilitate future implementation for Issues #444, #135, #458, and possibly #301

A couple additional notes:

The ares_timeout() function is now O(1) complexity instead of O(n) due to the use of a skiplist.
Some obscure bugs were uncovered which were actually being incorrectly validated in the test cases. These have been addressed in this PR but are not explicitly discussed.
Fixed some dead code warnings in ares_rand for systems that don't need rc4

Fix By: Brad House (@bradh352)

734 of 734 new or added lines in 16 files covered. (100.0%)

4810 of 5497 relevant lines covered (87.5%)

11686.61 hits per line