A binary tree is an efficient way of storing data in memory (in a tree!) The C run time library has a set of functions that allow you to create and manage data in a binary tree, but it is not that easy to set up.

Core concepts

Each element, or node, in the tree has two children and a pointer to the record. Each child can be null, or the address of another child. The left child contains elements which are less than the parent, the right node contains elements which are greater than the parent node. To find an element in the tree, you start at the top, or the root node, and compare the value of the nodes value, with the element you are looking for and work down the tree until you find a matching record or you hit the bottom of the tree. You provide a compare function takes two records and returns:

• -1 if the first record is greater than the second record
• 0 if the two records are the same item
• 1 if the first record is less than the second record.

The comparison could be a simple string compare, or comparing data in a structure for example

typedef struct {
 char pString[5];  // to the message text
 int count ;
 int date;
} MyNode;

int Node_compare(const void *MyNode1, const void *MyNode2) {
  MyNode * p1, *p2;
  int rc;
 // check the dates
  rc = p1-> date - p2 -> date;
  if (rc == 0 ) 
 // check the string
  rc = strcmp(p1->pString, p2->pString);
  // return the result
  return rc;

}

You need a root for the tree

void *ROOT = NULL;

Some C I do not understand

In some of the routines you need code like

char * buffer = * (char **) in;
//char * buffer = (char *) in;

With my knowledge of C, these two statements look the same. Only the first one works.

I have code

void print_Node(const void *ptr, ...) {
 ...
 MyNode p = *(MyNode**) ptr;

There may be a smarter way of referencing the passed data, but the definition of “MyNode p” and using “* (Mynode **)” on the passed in pointer, works.

Referencing structures

It took me a while to work out the correct type definitions to get it to work. For example

int Node_compare(const void *, const void *);
MyNode * pMyNode;
void * p;
p = (void *) pMyNode;
MyNode * q;
/* see if it is in the tree already */
q = *(MyNode **) tsearch(p, (void **) &ROOT, Node_Compare);

The various functions expect pointer defined with type (void *).

Find an element

To look for for an element you use the tfind (tree find) function. The parameters are

• a pointer to the record (or string) partially initialised with the values used by the compare function.
• the root of the tree
• the compare function, described above.

It returns the record, or a null.

To use this function you have to create a record containing the values the compare function can use it. This record can be in automatic storage, or you can use malloc() to allocate storage for it.

typedef struct {
 char pString[5];  // to the message text
 int count ;
 int date;
} MyNode;
MyNode tempNode;
memcpy(&tempNode.String("WXYZ"),sizeof("WXYZ");
tempNode.date = ....

You do not need to initialise tempNode.count, as this is not used in the comparison.

Adding an element

There is no tadd() function as such, there is a tsearch which provides “look for this node, and add it if it was not found“.

The parameters are

• a pointer to the record. 
• the root of the tree
• the compare function, described above.

it returns the address of a record. If it is the one you passed in – then it was added. It it returns a different node – an existing record was returned.

See below for a more detailed description.

Deleting a node

You pass the standard three parameters in.

Walking the tree.

I’ve typically used a binary tree to store lots of information, such as a list of error messages and the count of occurrences, then, at the end of the job, print them all out in sequence. This is called walking the tree.

You use

twalk(root, print_function);

This calls the print_function for every element in the tree.

Planning for the tree

If you plan to walk the tree and print the elements in order, then the compare function needs to be written so the data is in the right order.

For example, I want to report the number of error messages, and the count of the messages, by day.

With my structure

typedef struct {
 char pString[5];  // to the message text
 int count ;
 int date;
} MyNode;

If I use

int Node_compare(const void *MyNode1, const void *MyNode2) {
  MyNode * p1, *p2;
  int rc;
 // check the dates
  rc = p1-> date - p2 -> date;
  if (rc == 0 ) 
 // check the string
  rc = strcmp(p1->pString, p2->pString);
  return rc;

}

then the data will be sorted by date, then message within date order

If I use

int Node_compare(const void *MyNode1, const void *MyNode2) {
  MyNode * p1, *p2;
  int rc;
 // check the string
  rc = strcmp(p1->pString, p2->pString);
  if (rc == 0 ) 

  // check the dates
  rc = p1-> date - p2 -> date;
  
  return rc;

}

it will report in message sequence, then by date within message.

Adding nodes to the tree.

You need to malloc storage for each node you intend to add, because the node may be stored within the tree.

MyNode  * pTode;
/* allocate our Node - we cant use automatic storage as it may */
/* be added to the tree - so must not be deleted                */
pNode = (MyNode *) malloc(sizeof(MyNode));
if (pNode == 0) 
{
      perror("Malloc for Node failed ");
     return 8;
}

/* initialise it  */
strcpy(&pNode->pString[0],"ABCD") ;
pNode -> date = date();
pNode->count = 1;

void * p;
p = (void *) pNode;

MyNode * qreturned;
/* see if it is in the tree already                     */
qreturned = *(MyNode **) tsearch(p, (void **) &ROOT,Node_compare);

if (qreturned == p) 
{ 
     /* it didnt exist before - thus it was added */
     /* possibly do something   */
     initialise the remained of the record
}

else /* it did exist before so we need to update the count field  */
{
     qreturned->count += 1; Update the values
    /* release the storage we dont need */
      free(pNode);
}

All data must be self contained within the node, or to permanently allocate storage (with malloc()). If it references something in automatic storage, then when the automatic storage is reused, your pointer will point to invalid data.

Print the tree

twalk(ROOT, print_Node); // ROOT not &ROOT because of no updates, and pass the function
//
// which invokes
//
void print_Node(const void *ptr, VISIT order, int level) {
  if (order == leaf || order == postorder) {
   MyNode p = *(MyNode**) ptr;
   printf("Msg %4.4s date %d count %d\n", 
        p->pString, p->date,p-> count);
  // level is how far down the tree the node is. Root = 0
  }				
}

Putting it together

I wanted to collect information from RACF records and be able to refer back to the records. I treated the records as char *

The essence of the code is

Compare

#define LRECORD 294
int compare207(const void *MyNode1, const void *MyNode2) { 
   int rc = memcmp( ((char * ) Mynode1) + 1 
             ((char * ) Mynode2) + 1,261) 
 return rc; 
} 

Add a record

void add207(char * pRACF) 
{ 
   void * p    = malloc(LRECORD); 
 ...
  memcpy(p   ,pRACF,294); 
  qreturned = *(char   **) tsearch(p, (void **) &ROOT207, 
    compare207);
 if (qreturned == p) 
 { 
    // it was added
 } 
 else /* it did exist before so we need to update the count field  */ 
 { 
  //it existed - so update the fields); 
  // qreturned -> ....
 }  

Find a record

char * find207(char * pIn) 
{ 
  char * * pOut; 
  pOut =*(char **) tfind( (const void *) pIn, 
                 (void **)&ROOT207, 
                 compare207); 
  return pOut; 
} 

Walk the tree and print a record

void tree207print(const void *in    , VISIT order, int level) { 
   char * pBuffer = * (char **) in; 

 if (order == leaf || order == postorder) 
 { 
  printf("Data %s\n",pBbuffer -> .... );
 }
}

void twalk207() 
{ 
   twalk(ROOT207, tree207print); 
} 

I needed to see if a certificate is due to expire within “n” days. How do I find this date? It turns out to be pretty easy using standard C functions.

                                                                          
#include <stdio.h> 
#include <time.h> 
int main( int argc, char *argv??(??)) 
{ 
....
    char expireDate[11]; 
    time_t t1, t3; 
    struct tm *t2; 
    t1 = time(NULL); 
    t2 = localtime(&t1); 
    t2 -> tm_mday += 40 ; // 40 days from now 
    t3 = mktime(t2); 
    int s; 
    s=  strftime( expireDate, 11, "%Y/%m/%d", t2  ); 
    printf("====size  %d================\n",s); 
    printf(".%10.10s\n",expireDate); 

This successfully printed out the date 40 days, from now. The only little problem I had, was with strftime. The size of the output is 10 bytes. The “11” specifies the maximum number of characters that can be copied into the array. If this was 10… the size of the data I was expecting, The output was wrong “. 2023/06/1” ; off by one character in the buffer and a leading blank.!

With the technique of changing the value within a tm structure you can get the date-time n seconds / m minutes / d days/ from now either in the future – or in the past.

Clever stuff !

I have a program which takes as input a hex string, and this needed to be converted to an internal format, specifically a DER encoded format ( also known as a TLV, Tag, Length, Value);

This took me a good couple of hours to get right, and I thought the solution would be worth passing on.

The problem is: I have a C program and I pass in a parameter -serial abcd123456. I want to create a hex string 0x02llabcd123456 where ll is 5 – the length of the data.

Read the parameter

for (iArg = 1;iArg< argc; iArg ++   ) 
{ 
   if (strcmp(argv[iArg],"-serial") == 0 
      && iArg +1 < argc) // we have a value 
   { 
      iArg ++; 
      char * pData = argv[iArg]; 
      int iLen = strlen(pDataz); 
      if ( iLen > 16 ) 
      { 
         printf("Serial is too long(%d) %s.\n",iLen,pData); 
         return 8; 
      } 
    ... process it.
}

The

if (strcmp(argv[iArg],"-serial") == 0 
      && iArg +1 < argc) // we have a value 

checks to see if -serial was specified, and there is a parameter following. It handles the case of passing “-serial” and no following parameter.

Convert it from hex string to internal hex

I looked at various ways of converting the character string to hex, and decided the internal C run time sscanf function was best. This is the opposite of printf. It takes a formatting string and converts from printable to internal format.

For example

sscanf(pData,”%ix”,&i);

Would processes the characters in the data pointed to by pData and covert them, treating hen as hex data, to an integer &i. The processing continues until a non valid hex character is met, or the integer value is full.

If the parameter was –serial AC, the output value would be 0x000000AC.

I initially tried this, but then I had to go along and ignore any leading zeros.

You can use

sscanf(pData,”%6hh”,&bs[0]);

To read up to 6 characters into the byte string bs. If the parameter was –serial AC, the output value would be 0xAC….

This is almost what I want – I want a left justified byte string. But I have a variable length, and cannot pass a length as part of the string.

I managed this using a combindation of sprintf and sscanf.

The final-ish solution

 
int len = strlen(pData); // get the length of passed value
char sscan[20];   // used for sscanf string 
// we need to covert an ebcdic string to hex, so 
//  "1" needs length of 1, 
//  "12" needs length of 1 
//  "123" needs length of 2 etc 
int lHex = (len + 1) /2; 
                                                       
// convert to %4ddx 
// create a string for the sscan with the length 
// as it needs a hard coded length 
sprintf(&sscan[0],"%%%dhhx\0", len);
// if len = 4 this creates "%4hhx"
char tempOutput[16];
// Now use it 
sscanf(pData,&sscan[0],&tempOutput[0]); 

and I have &tempOutput containing my data – of length lHex.

This worked until it didn’t work

This worked fine until a couple of hours later. If the hex value was 7F… or smaller it worked. If it was 80… or larger it did not work.

This is because of the way the DER format handles signed numbers.

The value 0x02036789ab says

• 02 this is an integer field
• 03 of length 03
• with value 6789ab.

The value 0x0203Abcdef says

• 02 this is an integer field
• 03 of length 03
• with negative value Abcdef – negative because the top bit of the number is a 1.

Special casing for negative numbers

I had to allows for this negative number effect.

For negative numbers, the output needs to be 0x020400abcdef which says

• 02 this is an integer field
• 04 of length 04
• with value 00abcdef – positive because the top bit is zero.

pBuffer points to the output byte field.

 if (tempOutput[0] < 0x80) 
 { 
   memcpy(pBuffer+1,&temp[0],lHex); // move the data
   *pBuffer = lHex; // char value of the length 
 } 
 else // we need to insert extra so we do not get -ve 
 { 
   *(pBuffer+1) = 0x00; // insert extra null 
   memcpy(pBuffer+2,&temp[0],lHex); // and the rest 
   *pBuffer = lHex +1 ; // char value of the length 
 } 

The solution is easy with hindsight.