libfc4c / Blog: Recent posts

• Fixed: (BUG) dht_internal.h must include dynhsh.h when included by client app, to have dht_hshfn and dht_cmpfn pointers defined.
• Few cosmetic changes and fixes.

• Fixed: (BUG) print_snode(): useless last byte appended to stnd_t.str, what could cause compiler warning "excess elements in array initializer".

• Fixed: (BUG): fp64_g_str(), fp32_g_str(): invalid buffer size passed to csc_realloc(): memory corruption possible.
• Fixed: (BUG): fp64_int_cnv(): insufficient number of zeros injected into buffer for special value 0.0e+0.
• Fixed: (BUG::undetected): csc_printf(): va_arg "promotes" double arg to u64_t, unless passed as fp64_t, as in the test program -> undetected.
• Added: csc_xPrintP(): parametric versions of csc_xPrintf() functions, which allow to programmatically manipulate conversion parameters.
• Change: CSC: %s, %S conversions: strings are aligned to the left side of field, i.e. spaces are appended to the output string if field width is greater than the arg. length.

Full list in the change log.

• Fixed: (BUG::no_test): DBA: dba_SetBuffer() sets invalid number of m_slots.
• Fixed: (BUG::regression): CSC: fp32_int_cnv(): accidentally removed division by 10 for normal values (but tests passed). Now the test program is checking also the binary structure of float against value produced by strtof().
• Added: CSC: csc_printf() support for %lf, %le and %lg conversion specifiers: very fast double to string conversion, including sub-normals with full precision.
• Added: CSC: csc_printf() support for 'z' length modifier (aka size_t) and '%0' flag - zero-padding of numeric values
• Change: CSC: csc_printf(): %b and %B conversions are now over 2 times faster.... read more

• Fixed: (BUG): csc_printf()->fp32_g_str() is replacing target string instead of appending conversion result (mislooked)
  Archive with 6.2.0 removed

• Added: CSC: support for %f, %e and %g conversion specifiers for floats: probably the fastest possible method (and it's not Ryu ;) ),
• Added: CSC: support for field width, precision and '+' flag,
• Change: csc_printf(): re-written as a simple state machine, using computed gotos to parse format string -> much faster

• Fixed: --auto-idx, -x option takes base index as argument (missing in v6.2.0),
• Added: Injecting code for checking target platform byte order - to prevent 'surprises' when the trie data file is not generated at compile time.

• Fixed: srcgen.c: struct stnd_fsz should have aligned(4) attribute just like stnd_t.
• Fixed: --long-options not really implemented.

• Added: Project: Util/libfc4c_tri_codegen-6.1.0.tar.gz package: tri_codegen utility takes user-provided text data file as input, creates a Trie container based on the content of the file, and then generates source code with structures describing the Trie. The sources generated by tri_codegen can be compiled into programs which need a static Trie structures, and which otherwise would have to be generated each time the the program is started.
• Change: csc_Printf() the 'l' length modifier is ignored for %p and %P conversion specifiers - pointer type size depends on __WORDSIZE.
• Change: tri_internal.h: the header is now installed, to allow writing extensions to the trie container.
• Change: dht_t is now opaque type, but can be accessed by including dht_internal.h. Functions related to hmap_t are also moved to dht_internal.h.
• Fixed: Symbols do_hash_data(), read(), write() should not be exported.

• Added: DBA: dba_ShiftRight(), dba_ShiftLeft(): shifting array bits right/left starting at given bit index,
• Added: DBA: dba_InsertBitF(), dba_InsertLongBitF(), dba_DeleteBitF(): inserting and removing bitfields from array,
• Added: DBA: dba_PushMask(), dba_PopMask(): push/pop 1..32 bits to/from the array,
• Added: DBA: dba_PushLongMask(), dba_PopLongMask(): push/pop bit masks of arbitrary size,
• Added: DBA: dba_Copy(): copy data between bit arrays,
• Added: CSC: csc_sPrintf(), csc_aPrintf(): printing to CSC string replacing or appending the text,
• Added: CSC: csc_dPrintf(): printing to file descriptor, using CSC as a temp buffer,
• Added: CSC: csc_printf() support for non-standard conversion specifier "%S": CSC string,
• Added: CSC: csc_printf() support for non-standard conversion specifier "%B": DBA array,
• Added: CSC: csc_printf() support for 'l' length modifier, which assures consistent behaviour on both 32bit and 64bit platforms: without 'l' all conversions are 32bit, and 64bit otherwise,
• Added: DAR: dar_PopObjCopy(): returns the object "by value" - i.e. a copy,
• Change: TRI: tri_Save() now takes 'flags' argument, currently used for TRI_REBUILD only - rebuild the trie before saving.
• Change: new versioning method for saved containers, similar to libtool's system - allows to precisely define supported versions range, by using "age" value,
• Fixed few BUGS.

• Fixed: (BUG::LEAK) tri_AddObjectKey(), tri_DeleteKey(): a trivial BUG: using malloc() instead of realloc() for trip->ndstk.tmp_buf.
• Fixed: (BUG::old): csc_Printf() invalid result for signed 64bit integers if the value is above 32bit range.
• Change: csc_Append_cstr(): added support for self-appending of the CSC buffer.
• Change: csc_Printf(): dynamically extends target CSC size if needed.
• Added: csc_Printf(): support for "%o" (octal) conversion specifier and "%%" - percent sign.
• Fixed: TEST::DRB: missing support for "--vrb" option.... read more

• Fixed: (BUG::regression) max configurable snode length should be 122 bytes (244 4bit words), limited by stnd_t.pos/epos,
• Fixed: (BUG) dar_Clone(), dar_Copy(): handle cases when source DAR is empty,
• Fixed: dar_Clone(), dar_Copy(): added checking for buffer overflow on 32bit platform,
• Fixed: DBA: 32bit mask operations: offset verification should be performed against dba_t.u_slots, not dba_t.m_slots.
• Fixed: TEST::DHT: missing support for "--vrb" option.
• Update: rcode v3.3

Most important changes:

• Fixed: (BUG::TRI) in some special cases tri_FindObject() could return RCD_TRUE for partial match
• Added: TRI: support for MT-safe parallel search operations,
• Added: TRI: configurable string node size: 6..250 bytes,
• Added: DBA: bitwise operations on masks of arbitrary size,
• Change: CSC can be statically allocated, removed 32-bit padding,
• Added: support for Large Files (with size over 2GiB)... read more

Fixed: (BUG::undetected_in_TEST_program) tri_GetKey() could return wrong object key in some special cases.

• Fixed: _gen_suffix_ar(), tri_AddObjectKey(), tri_DeleteKey(), tri_ObjectKeyDiag_Write(): unaligned key r/w opertions are now handled in a portable way.
• Fixed: tri_ExtractObjects(obj_sz != 0) returns error if target object size is greater than obj_sz (smaller size is allowed).

Few BUGs fixed, added tri_ExtractObjects() - a function for extracting objects encoded in the Trie.

• Added: tri_ObjectDiag_Write(), tri_ObjectKeyDiag_Write(): prints list of nodes used to encode object (with key) in the Trie.
• Update: rcode v3.2

Full list in the change log.

• Fixed: (BUG::regression) dar_Pop(): return NULL if the array is empty.
• Added: tri_Clone(): Create copy of the Trie container.
• Added: tri_Shrink(): free unused Trie resources.
• Change: configure: added "--with-test" option: build the test program along with the library.
• Change: TEST: merged test for fc4c_hash32() with main test program.
• Added: TEST: test_key_aliasing(): extraction of keys which are sub-strings of another string, extremely rare case.
• Change: TEST: individual tests can be selected from cmd line.... read more

Added: general purpose Trie container.

The trie implementation is based on:
- reduced alphabet size (4 bit),
- direct node indexing.
- stacked nodes (2 different stacks are used for sub-tree and string nodes),
- offset-linked lists of deleted nodes,
- single-bit terminal nodes.

Storing trie nodes on stacks has huge impact on the trie properties:
- dynamic heap allocations are almost completely eliminated;
- sub-tree node size is reduced, by using node offsets instead of pointers;
- allocation and deletion of nodes is very fast, especially when the
operations are interleaved;
- saving, loading and archiving operations are trivial, cause nodes are
stored in a continuous memory block;

• Change: csc_SetBuffer() and dar_SetBuffer() are now inlined functions.
• Change: Removed deprecated fc4c_hash32_1_x().
• Update: rcode v3.0: ABI changed!

• Fixed: (BUG::regression::typo): dynarr.c: missing semicolon in declaration of dar_read() for non-libarchive mode: build fails if libarchive is not available.
• Fixed: (BUG) missing checking if builtin_umul_overflow() is really available.

• Fixed: (BUG::old) csc_cnv_s(): internal buffer too small to print 64bit value in base 2.
• Added: csc_Printf(): added support for %X and %P conversion specifiers.
• Added: csc_SetBuffer(): initialize the container using custom buffer.
• Added: dar_GetItem_NC(): just like dar_GetItem(), no checks are performed.
• Added: drb_GetItem_NC(): fast inlined version without bounds checking.

• Fixed: (BUG::old) fc4c_hash32(): unaligned bytes at the end of hashed area were not used for hash value computation. Container header version changed from 1.4 to 2.0, old saved containers are automatically converted to new version. Unfortunately, this breaks saved hash tables which were generated using old version of fc4c_hash32(), so the old version is now exported as fc4c_hash32_1_x().
• Fixed: (BUG) drb_Push(DRB_DYNAMIC): could fail due to optimized insertion at the end of buffer.
• Change: dar_Alloc(): do not sum requested number of items with prefetch value: always use prefetch, unless the requested number is higher.
• Change: drb_GetItem() returns newly added items only, that is items which were not de-queued with drb_Get()
• Added: drb_GetLastItem(): equivalent to drb_GetItem(drb_t*, drb_GetCount()-1).
• Added: drb_IsEmpty() returns true if there are no items left for drb_Get()

• Fixed: (BUG): drb_Empty(): missing reset of drb state.
• Fixed: (BUG): FC4C_DRB_INITIALIZER not updated to current drb_t structure.
• Fixed: (BUG::old): FC4C_CSC_INITIALIZER not updated to current csc_t structure, harmless.
• Change: all initializer macros: using designated initializers for better readability.

• Update: rcd_autogen v2.9: Fixed: misuse of VMSG TLS pointer, race possible.