uuid.c

Manipulation and tracking of UUIDs

Summary
uuid.cManipulation and tracking of UUIDs
UUID structure
str2uuidParse a UUID string and optionally convert to binary UUID
uuid2strgenerate a UUID string Return a pointer to start of string String is fixed length CID_STR_SIZE (including Nul terminator) e.g.
UUID search
Radix search using Patricia treeThis 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.
Functions
matchuuid
testbitReturn 1 if the bit from uuid defined by tstloc is set, 0 if clear.
_finduuidFind the tree entry where uuid should go.

UUID structure

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
Summary
str2uuidParse a UUID string and optionally convert to binary UUID
uuid2strgenerate a UUID string Return a pointer to start of string String is fixed length CID_STR_SIZE (including Nul terminator) e.g.
UUID search

str2uuid

int str2uuid(const char *uuidstr,
uint8_t *uuid)

Parse a UUID string and optionally convert to binary UUID

If argument uuid is NULL there is no output but the string is still fully parsed.

return

0 on success or -1 on error

uuid2str

char * uuid2str(const uint8_t *uuid,
char *uuidstr)

generate a UUID string Return a pointer to start of string String is fixed length CID_STR_SIZE (including Nul terminator) e.g. a834b30c-6298-46b3-ac59-c5a0286bb599 19e50ed0-a4f3-11e2-a1cb-0017316c497d

UUID search

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.  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: Terminationthere 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.

Summary
Functions
matchuuid
testbitReturn 1 if the bit from uuid defined by tstloc is set, 0 if clear.
_finduuidFind the tree entry where uuid should go.

Functions

matchuuid

static inline uuidtst_t matchuuid(const uint8_t *uuid1,
const uint8_t *uuid2)
Test for exact matchdon’t use uuidsEq() because if we fail we want to record the point of difference.

testbit

static inline int testbit(const uint8_t *uuid,
uuidtst_t tstloc)

Return 1 if the bit from uuid defined by tstloc is set, 0 if clear.

_finduuid

static struct uuidtrk_s * _finduuid(struct uuidset_s *set,
const uint8_t *uuid)

Find the tree entry where uuid should go.  This is the nearest value to uuid but not necessarily equal to it.

int str2uuid(const char *uuidstr,
uint8_t *uuid)
Parse a UUID string and optionally convert to binary UUID
char * uuid2str(const uint8_t *uuid,
char *uuidstr)
generate a UUID string Return a pointer to start of string String is fixed length CID_STR_SIZE (including Nul terminator) e.g.
static inline uuidtst_t matchuuid(const uint8_t *uuid1,
const uint8_t *uuid2)
static inline int testbit(const uint8_t *uuid,
uuidtst_t tstloc)
Return 1 if the bit from uuid defined by tstloc is set, 0 if clear.
static struct uuidtrk_s * _finduuid(struct uuidset_s *set,
const uint8_t *uuid)
Find the tree entry where uuid should go.
Close