lirobot / ulib Goto Github PK
View Code? Open in Web Editor NEWAutomatically exported from code.google.com/p/ulib
Automatically exported from code.google.com/p/ulib
The goal of this project is to provide extremely efficient implementations of some fundamental data structures and algorithms. The interface of each component has been made general and self-explanatory, one can grasp the usage by looking at the header of the component. I've implemented most of the components and the rest were ported from other open-source projects, such as the Linux kernel, of which all credits go the original authors. Main Features An extremely efficient open addressing hash table, comparable or even better performance than STL hashmap, Google sparse/dense hash, EASTL hashmap and RDESTL hashmap. A chaining hash table, corner stone for building concurrent hash tables. A concurrent hash table based on the chaining hash table. Significantly faster (~30%) than several popular ones, e.g., TBB(http://threadingbuildingblocks.org), nbds(http://code.google.com/p/nbds/) and Visual Studio 2012. LocksCanMakeSense provides some analysis. The fast-hash hash function http://fast-hash.googlecode.com. Efficient and robust general purpose hash function. A set of robust, efficient, and invertible integer hash functions. Heap and heapsort. Improved performance than STL. A text binary search algorithm. A robust O(n) median algorithm. Various random number generators, e.g. Zipf RNG, Normal RNG, and Gamma RNG. General AVL and Splay trees. Faster than Solaris Kernel AVL and libavl. Bit tricks. Cryptographic algorithms. Parallel Programming MapReduce framework for multicores. A set of scalable locks. Atomic primitives for x86_64. Update History 08/01/2013 Added a patch to the SVN trunk. This patch fixes a segmentation fault raised in the sort() method of hash_chain. This issue only occurs when it is complied by certain buggy GCCs. If you have the hash_chain tests failed due to segmentation fault, please consider applying this patch. Start from the version 2.0.0 beta, the ulib library targets only x86_64 architecture. In other words, newer versions may not compile/work on other architectures. Performance Test codes can be located under perf/. Hash table performance AlignedHashingPerformance. AVL tree performance AVLPerformance. Analysis of FastHash http://code.google.com/p/fast-hash/. Core Items bfilter.{h,c}: the Bloom filter bitmap.{h,c}: generic bitmap crypt_aes.{h,c}: the AES crypt crypt_md5.{h,c}: the MD5 algorithm crypt_rc4.{h,c}: the RC4 crypt crypt_sha1.{h,c}: the SHA1 algorithm crypt_sha256.{h,c}: the SHA256 algorithm hash_open.h: C++ containers for the open addressing hashmap and hashset hash_open_prot.h: prototypes for the open addressing hashmap and hashset hash_chain.h: C++ container for the chain hashmap hash_chain_prot.h: prototype for the chain hashmap hash_func.{h,c}: hash functions heap_prot.h: generic heap prototype list.h: doubly linked list, can be used to implement queue and stack math_bit.h: bit operations math_bn.{h,c}: big number arithmetics math_comb.{h,c}: combinatorics enumerator math_factorial.{h,c}: factorial approximations math_gcd.{h,c}: Euclidean and the Extended Euclidean GCD algorithms math_lcm.{h,c}: the least common multiple math_rand_prot.h: pseudo-random number generators, mix functions, and etc math_rng_gamma.{h,c}: gamma distribution RNG math_rng_normal.{h,c}: normal distribution RNG math_rng_zipf.{h,c}: Zipf distribution RNG search_line.{h,c}: binary search for the text lines sort_heap_prot.h: prototype for the heapsort sort_list.{h,c}: list sort sort_median_prot.h: prototype for the median algorithm str_util.{h,c}: parallel/supplementary string utilities tree.{h,c}: various binary search trees tree_util.{h,c}: tree utilities ulib_ver.{h,c}: ulib version util_algo.h: basic algorithms util_console.{h,c}: command-line parser util_hexdump: the hexdump utilities util_log.h: logging utilities util_timer.h: high-precision timer Parallel Items hash_chain_r.h: concurrent chain hashmap hash_multi_r.h: concurrent multiple hashmap mr_dataset.{h,cpp}: the MapReduce data abstraction mr_engine.h: the MapReduce engine mr_interm.h: the MapReduce intermediate storage abstraction os_atomic_intel64.h: atomic operations for the x86_64 os_rdtsc.h: the Intel rdtsc instruction os_regionlock.h: region locks os_spinlock.h: various spinlocks for the x86_64 os_thread.{h,cpp}: thread wrapper class os_typelock.h: typed locks for C++
What steps will reproduce the problem?
1. tar xvzf ulib-2.0.0beta_src.tar.gz
2. cd ulib-svn
3. make
What is the expected output? What do you see instead?
lch@hyperstream:/DT/local/ulib-svn$ make
make -C src/
make[1]: Entering directory `/DT/local/ulib-svn/src'
make -C base/
make[2]: Entering directory `/DT/local/ulib-svn/src/base'
AR ../../lib/libbase.a
make[2]: Leaving directory `/DT/local/ulib-svn/src/base'
make -C ext1/
make[2]: Entering directory `/DT/local/ulib-svn/src/ext1'
make -C c++/
make[3]: Entering directory `/DT/local/ulib-svn/src/ext1/c++'
make[3]: Leaving directory `/DT/local/ulib-svn/src/ext1/c++'
make -C bloom_filter/
make[3]: Entering directory `/DT/local/ulib-svn/src/ext1/bloom_filter'
AR ../../../lib/libbfilter.a
make[3]: Leaving directory `/DT/local/ulib-svn/src/ext1/bloom_filter'
make -C comb/
make[3]: Entering directory `/DT/local/ulib-svn/src/ext1/comb'
AR ../../../lib/libcomb.a
make[3]: Leaving directory `/DT/local/ulib-svn/src/ext1/comb'
make -C console/
make[3]: Entering directory `/DT/local/ulib-svn/src/ext1/console'
AR ../../../lib/libconsole.a
make[3]: Leaving directory `/DT/local/ulib-svn/src/ext1/console'
make -C rng/
make[3]: Entering directory `/DT/local/ulib-svn/src/ext1/rng'
AR ../../../lib/librng.a
make[3]: Leaving directory `/DT/local/ulib-svn/src/ext1/rng'
make[2]: Leaving directory `/DT/local/ulib-svn/src/ext1'
make -C ext2/
make[2]: Entering directory `/DT/local/ulib-svn/src/ext2'
make -C thread
make[3]: Entering directory `/DT/local/ulib-svn/src/ext2/thread'
AR ../../../lib/libthread.a
make[3]: Leaving directory `/DT/local/ulib-svn/src/ext2/thread'
make -C osdep
make[3]: Entering directory `/DT/local/ulib-svn/src/ext2/osdep'
make[3]: Leaving directory `/DT/local/ulib-svn/src/ext2/osdep'
make -C reentrant
make[3]: Entering directory `/DT/local/ulib-svn/src/ext2/reentrant'
make[3]: Leaving directory `/DT/local/ulib-svn/src/ext2/reentrant'
make -C mapreduce
make[3]: Entering directory `/DT/local/ulib-svn/src/ext2/mapreduce'
AR ../../../lib/libmr.a
make[3]: Leaving directory `/DT/local/ulib-svn/src/ext2/mapreduce'
make[2]: Leaving directory `/DT/local/ulib-svn/src/ext2'
make[1]: Leaving directory `/DT/local/ulib-svn/src'
make -C lib/
make[1]: Entering directory `/DT/local/ulib-svn/lib'
make[1]: `libulib.a' is up to date.
make[1]: Leaving directory `/DT/local/ulib-svn/lib'
make -C test/
make[1]: Entering directory `/DT/local/ulib-svn/test'
-e GEN hash_chain_r1.test
In file included from ../include/ulib/os_typelock.h:30:0,
from ../include/ulib/os_regionlock.h:32,
from ../include/ulib/hash_chain_r.h:32,
from hash_chain_r1.cpp:3:
../include/ulib/os_spinlock.h: In function ‘void
spin_lock_ticket(ticket_lock_t*)’:
../include/ulib/os_spinlock.h:302:37: error: expected primary-expression before
‘.’ token
../include/ulib/os_spinlock.h: In function ‘void
spin_wrlock_ticket(ticket_rwlock_t*)’:
../include/ulib/os_spinlock.h:357:39: error: expected primary-expression before
‘.’ token
../include/ulib/os_spinlock.h: In function ‘void
spin_wrunlock_ticket(ticket_rwlock_t*)’:
../include/ulib/os_spinlock.h:375:39: error: expected primary-expression before
‘.’ token
../include/ulib/os_spinlock.h: In function ‘void
spin_rdlock_ticket(ticket_rwlock_t*)’:
../include/ulib/os_spinlock.h:403:39: error: expected primary-expression before
‘.’ token
make[1]: *** [hash_chain_r1.test] Error 1
make[1]: Leaving directory `/DT/local/ulib-svn/test'
make: *** [all] Error 2
What version of the product are you using? On what operating system?
Ubuntu 12.04.2 LTS
Please provide any additional information below.
Here the generated code. There is a ".head_tail" instead of "inc.head_tail":
static __always_inline void spin_lock_ticket(ticket_lock_t *lock)
{
register union ticket_lock inc = { .head_tail = 1 << TICKET_SHIFT };
#ifdef LARGE_CPUSET
inc.head_tail = atomic_fetchadd32(&lock->tickets, inc.head_tail);
#else
inc.head_tail = atomic_fetchadd16(&lock->tickets, inc.head_tail);
#endif
[...]
Original issue reported on code.google.com by [email protected]
on 4 Apr 2013 at 1:42
What steps will reproduce the problem?
executing the test case
What is the expected output? What do you see instead?
/tmp/ccb66wEl.o: In function `ulib::thread::stop_and_join()':
/home/dgu/ExtProject/ulib-read-only/test/../include/ulib/thread.h:68: undefined
reference to `pthread_join'
What version of the product are you using? On what operating system?
the latest
Please provide any additional information below.
Original issue reported on code.google.com by [email protected]
on 23 Dec 2012 at 1:08
What steps will reproduce the problem?
1. make
2. make test
What is the expected output? What do you see instead?
hash_align.test: hash_align.cpp:42: int main(): Assertion `months["april"] ==
30' failed.
Aborted (core dumped)
hash_multihash_r.test: hash_multihash_r.cpp:70: int main(): Assertion `map[num]
== -1' failed.
Aborted (core dumped)
[main:6] [W] warning log
[main:8] [E] fatal log
median.test: median.cpp:32: int main(): Assertion `m == data[k]' failed.
Aborted (core dumped)
55 success
58 in all
What version of the product are you using? On what operating system?
$ uname -a
Linux server1 3.8.0-19-generic #29-Ubuntu SMP Wed Apr 17 18:16:28 UTC 2013
x86_64 x86_64 x86_64 GNU/Linux
Please provide any additional information below.
Original issue reported on code.google.com by [email protected]
on 14 May 2013 at 8:42
What steps will reproduce the problem?
1. svn checkout http://ulib.googlecode.com/svn/trunk/ ulib
2. cd ulib
3. make
[...]
cc1: warnings being treated as errors
argv_split.c: In function ‘argv_split’:
argv_split.c:95: warning: implicit declaration of function ‘strndup’
argv_split.c:95: warning: incompatible implicit declaration of built-in
function ‘strndup’
make[3]: *** [argv_split.o] Error 1
make[2]: *** [all] Error 2
make[1]: *** [all] Error 2
make: *** [ulib_dist.tar.gz] Error 2
What is the expected output? What do you see instead?
strndup function is missing on OSX and -L can't be used with extra space.
What version of the product are you using? On what operating system?
ulib from subversion (trunk)
Please provide any additional information below.
The following patch (ulib-osx.patch) fix all the compile problem on OSX
(10.6.8+).
Original issue reported on code.google.com by [email protected]
on 29 Jan 2012 at 4:39
Attachments:
What steps will reproduce the problem?
1. Use aligned has of std::string to int or a custom string class to int;
compilers Win/Vis Studio 11 or linux/gcc 4.4.6 (the std gcc on latest redhat).
2. I get a crash right away: on first cal of insert.
3. Debugging is near impossible, due to most code being in #define macros!
What is the expected output? What do you see instead?
What version of the product are you using? On what operating system?
Please provide any additional information below.
Silly question: I was just interested to know if this C++ class is tested and
works correctly without mem corruption or leaks? Or do you only use/test the C
version? Looks e.g. that code assignes into area that is only allocated by C,
so are we sure construction/destruction for objects works?
Original issue reported on code.google.com by [email protected]
on 31 Jul 2012 at 11:33
Purpose of code changes on this branch:
add gtest.h
When reviewing my code changes, please focus on:
After the review, I'll merge this branch into:
/trunk
Original issue reported on code.google.com by [email protected]
on 16 Sep 2011 at 3:54
Attachments:
What steps will reproduce the problem?
1. define an open_hash_set<uint64_t> as my_set, then insert [0,1<<26) as keys
into it by step N in a loop
2. define an open_hash_map<uint64_t, uint64_t> as my_map
3. iterate the open_hash_set and get iterator's key() as my_map's key, then set
my_map[key] = 1
4. change loop's step N, and watch the costing time of my_map's operation
What is the expected output? What do you see instead?
Expected output: costing time should be less and less as N increasing
I see: the costing time is not correct(more than 20 seconds when N is 3)
What version of the product are you using? On what operating system?
Version: 2.0.1
OS: debian7 64bit, gcc 4.7.2
Please provide any additional information below.
Original issue reported on code.google.com by [email protected]
on 21 Nov 2013 at 6:07
Attachments:
What steps will reproduce the problem?
1. make
What is the expected output? What do you see instead?
ld: library not found for -lrt
clang: error: linker command failed with exit code 1 (use -v to see invocation)
make[1]: *** [aes.test] Error 1
make: *** [all] Error 2
What version of the product are you using? On what operating system?
2.0.1
Please provide any additional information below.
I am using OSX Mavericks with latest Xcode command line tools
Original issue reported on code.google.com by [email protected]
on 28 Nov 2013 at 8:43
Hi
i just downloaded the source tar from site
wget http://ulib.googlecode.com/files/ulib-2.0.1_src.tar.gz
i checked the checksum its correct.
i extracted the file and did make and i found following issue
i am using Ubuntu 13.04 over Intel® Core™ i7-2630QM CPU @ 2.00GHz × 8
below is the problem listed.
amey@axps:~/work/installables/ulib-svn$ make
make -C src/
make[1]: Entering directory `/home/amey/work/installables/ulib-svn/src'
make -C base/
make[2]: Entering directory `/home/amey/work/installables/ulib-svn/src/base'
-e CC bitmap.c
-e CC crypt_aes.c
-e CC crypt_md5.c
-e CC crypt_rc4.c
-e CC crypt_sha1.c
-e CC crypt_sha256.c
-e CC hash_func.c
hash_func.c: In function ‘hash_ferm64’:
hash_func.c:92:3: error: impossible register constraint in ‘asm’
hash_func.c:114:1: error: impossible register constraint in ‘asm’
hash_func.c:106:3: error: impossible register constraint in ‘asm’
hash_func.c:114:1: error: impossible register constraint in ‘asm’
make[2]: *** [hash_func.o] Error 1
make[2]: Leaving directory `/home/amey/work/installables/ulib-svn/src/base'
make[1]: *** [all] Error 2
make[1]: Leaving directory `/home/amey/work/installables/ulib-svn/src'
make: *** [all] Error 2
Original issue reported on code.google.com by [email protected]
on 6 Apr 2014 at 11:12
What steps will reproduce the problem?
1. Just use a 2-block 256-bit AES encrypted input; Vis Studio 10/11, 64-bit.
Sandybridge PC.
2. Call code like below (iv is 16 bytes):
AES_KEY aeskey;
AES_set_decrypt_key( key, 32 * 8, &aeskey );
AES_cbc_decrypt( ( const unsigned char * ) in, ( unsigned char * ) in, iv, 2, &aeskey );
"in" is allocated with malloc, which guarantees 16-byte alignment on 64-bit.
"iv" is:
uchar iv[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
What is the expected output? What do you see instead?
This decrypts all bytes in the 1st block correctly.
But the 2nd block gets garbage.
When i use a different buffer (non-overlapping) for output, it works fine.
What version of the product are you using? On what operating system?
Latest
Please provide any additional information below.
I also tried to add a couple of changes, but neither of them helped:
(1)
Looking at original code you may need this too:
#ifdef _MSC_VER
#define SWAP(x) (_lrotl(x, 8) & 0x00ff00ff | _lrotr(x, 8) & 0xff00ff00)
#define GETU32(p) SWAP(*((u32 *)(p)))
#define PUTU32(ct, st) { *((u32 *)(ct)) = SWAP((st)); }
#else
#define GETU32(pt) (((u32)(pt)[0] << 24) ^ ((u32)(pt)[1] << 16) ^ ((u32)(pt)[2]
<< 8) ^ ((u32)(pt)[3]))
#define PUTU32(ct, st) { (ct)[0] = (u8)((st) >> 24); (ct)[1] = (u8)((st) >>
16); (ct)[2] = (u8)((st) >> 8); (ct)[3] = (u8)(st); }
#endif
(2)
YTou do also need this change:
#if defined(__x86_64__) || defined(_M_X64)
#define AES_BLOCK_OP(dst, src, op) AES_BLOCK_OP64(dst, src, op)
#else
#define AES_BLOCK_OP(dst, src, op) AES_BLOCK_OP32(dst, src, op)
#endif
FYI, i also tried code built in 32-bit - same issue.
Note: VS Express version is available freely and you could also get Beta for VS
11.
Possible to fix? As the called function says it works on overlapping buffers, i
assume the cbc can do the same?
Original issue reported on code.google.com by [email protected]
on 30 Jul 2012 at 6:14
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.