Git Product home page Git Product logo

ulib's Introduction

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++ 

ulib's People

Watchers

James Cloos avatar

ulib's Issues

os_spinlock.h does not compile

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

error during the test execution

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

3 tests failed

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

ulib on OSX

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:

aligned_hash

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

add gtest.h

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:

open_hash_map's operation execution time is too long sometimes

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:

Cannot build on OSX Mavericks

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

Error on make in ubuntu 13.04

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

AES_cbc_decrypt seems not working when in/out are the same (overlap)

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

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.