Manipulation and tracking of UUIDs
|uuid.c||Manipulation and tracking of UUIDs|
|str2uuid||Parse a UUID string and optionally convert to binary UUID|
|uuid2str||generate a UUID string Return a pointer to start of string String is fixed length CID_STR_SIZE (including Nul terminator) e.g.|
|Radix search using Patricia tree||This tree uses the technique described in Sedgewick: “Algorithms” for folding the external nodes back into internal nodes - the value within the node is ignored when descending the tree (as the node is being treated as an internal one) and only the testbit is considered.|
|testbit||Return 1 if the bit from uuid defined by tstloc is set, 0 if clear.|
|_finduuid||Find the tree entry where uuid should go.|
timelow tmid Vthi Rseq node xxxxxxxx-xxxx-VVxx-RRxx-xxxxxxxxxxxx VV = version 1x => time based 2x => DCE/Posix 3x => name based w MD5 4x => random 5x => name based w SHA1 RR = variant = 10xx xxxx for UUID spec others are NCS, Microsoft proprietary etc. Char 0 1 2 3 012345678901234567890123456789012345 xxxxxxxx-xxxx-VVxx-RRxx-xxxxxxxxxxxx Octet 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 xxxxxxxx-xxxx-VVxx-RRxx-xxxxxxxxxxxx
This tree uses the technique described in Sedgewick: “Algorithms” for folding the external nodes back into internal nodes - the value within the node is ignored when descending the tree (as the node is being treated as an internal one) and only the testbit is considered. Only on detecting an external node (detected by a testbit value in the child which preceeds the current one) is the value stored within that child node considered.
Unlike Sedgewick and most common examples we descend the tree in order of increasing bit number, but we number the bits in individual bytes in reverse of normal so MSB of the first byte is bit 0. This means that UUIDs sort in numericasl order if treated as a single big-endian number.
Efficiency of inner loop is highly dependent on processor instruction set so may need to be optimized. To facilitate this We define two inline functions which are used throughout to test or calculate the necessary bit differences:
bool testbit(uint8_t *uuid, tstloc_t tstloc)
returns 1 or 0 according to whether the bit in uuid identified by tstloc is set or cleared. tstloc_t may be defined as an integer or a bitflag or a combination but must sort in increasing order when the bits are numbered as above.
tstloc_t matchloc(uuid1, uuid2)
calculates the value of tstloc corresponding to the first (lowest numbered) bits which differ between two uuids - or returns MATCHVAL if they are equal;
The implementation here is well suited to many architectures. tstloc is a combination of the byte number (in bits 11..8) and a bitmask in bits 7..0. The bit mask is the inverse if the bit to be tested (e.g. 0x7f to test bit 0 - numbered down from MSB remember). This ensures it sorts in increasing numerical order as required.
|Note: Termination||there is a dangling link special case owing to the fact that any tree has one more external links than it has nodes (work it out!) There are several possibilities for dealing with this. We use a special value for tstloc to mark the terminating node and then have to treat it as a special case in a few places. The termination value needs to have two properties: First, it needs to sort after (be greater than) any “genuine” value. Second, it gets used in tests so whilst the result of such a test does not matter, it must be a valid 0..1 value and cannot attempt access of a byte outside the uuid.|
Note: Because we need to test against UUIDs from packets we can make no guarantees about alignment of supplied UUID.
Parse a UUID string and optionally convert to binary UUID
int str2uuid( const char * uuidstr, uint8_t * uuid )
generate a UUID string Return a pointer to start of string String is fixed length CID_STR_SIZE (including Nul terminator) e.g.
char * uuid2str( const uint8_t * uuid, char * uuidstr )
static inline uuidtst_t matchuuid( const uint8_t * uuid1, const uint8_t * uuid2 )
Return 1 if the bit from uuid defined by tstloc is set, 0 if clear.
static inline int testbit( const uint8_t * uuid, uuidtst_t tstloc )
Find the tree entry where uuid should go.
static struct uuidtrk_s * _finduuid( struct uuidset_s * set, const uint8_t * uuid )