970224: Porting UDunits to PC

Arlindo,

> To: address@hidden
> cc: address@hidden
> From: Arlindo da Silva <address@hidden>
> Subject: Porting UDunits to PC
> Organization: NASA/GSFC
> Keywords: 199702221703.KAA06697

In the above message, you wrote:

>    I am trying to come up with a port of GrADS NetCDF I/O layer for
> the PC (16-bits for now). Unfortunately, Don Hooper's interface
> also relies on UDUNITS which is known to be a tough nut to crack.
> 
>    Do you know of any PC port? I couldn't find anything, it is not
> listed as "supported" in your table. I going ahead and giving it a
> try. Don stripped out the fortran stuff we don't need, I am basically
> concentrating on
> 
> udalloc.c       utlib.c         utparse.c       utscan.c
> 
> Most things compile fine with MS C/C++ v7. The main glitch right now
> is that utlib.c relies on tsearch(3) for searching trees. This is
> POSIX allright, but not available with MS compiler. I got the routine
> below from gcc's libc (see below), but it is way above my head,
> specially the compiler assumptions.

If you got it from GNU, then it's probably all right.  I wouldn't worry
about the compiler assumptions.

> Do you know of any vanilla
> tsearch(3) implementation? Freeware, of course.

I've enclosed one that I have.  It comprises four files: tdelete.c,
tfind.c, tsearch.c, and twalk.c.

--------
Steve Emmerson   <address@hidden>

------Begin tdelete.c
/*
 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
 * the AT&T man page says.
 *
 * The node_t structure is for internal use only, lint doesn't grok it.
 *
 * Written by reading the System V Interface Definition, not the code.
 *
 * Totally public domain.
 */
/*LINTLIBRARY*/

#include <search.h>
#include "search-node.h"

void *tdelete(key, rp, compar)
/* delete node with given key */
const void      *key;                   /* key to be deleted */
void **rp;      /* address of the root of tree */
int     (*compar)();            /* comparison function */
{
    node *p;
    register node *q;
    register node *r;
    int cmp;
    register node       **rootp = (node**)rp;   /* address of the root of tree 
*/

    if (rootp == (struct node_t **)0 || (p = *rootp) == (struct node_t *)0)
        return ((struct node_t *)0);
    while ((cmp = (*compar)(key, (*rootp)->key)) != 0)
    {
        p = *rootp;
        rootp = (cmp < 0) ?
            &(*rootp)->left :           /* follow left branch */
            &(*rootp)->right;           /* follow right branch */
        if (*rootp == (struct node_t *)0)
            return ((struct node_t *)0);        /* key not found */
    }
    r = (*rootp)->right;                        /* D1: */
    if ((q = (*rootp)->left) == (struct node_t *)0)     /* Left (struct node_t 
*)0? */
        q = r;
    else if (r != (struct node_t *)0)           /* Right link is null? */
    {
        if (r->left == (struct node_t *)0)      /* D2: Find successor */
        {
            r->left = q;
            q = r;
        }
        else
        {                       /* D3: Find (struct node_t *)0 link */
            for (q = r->left; q->left != (struct node_t *)0; q = r->left)
                r = q;
            r->left = q->right;
            q->left = (*rootp)->left;
            q->right = (*rootp)->right;
        }
    }
    free((struct node_t *) *rootp);     /* D4: Free node */
    *rootp = q;                         /* link parent to new node */
    return(p);
}
------End tdelete.c

------Begin tfind.c
/*
 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
 * the AT&T man page says.
 *
 * The node_t structure is for internal use only, lint doesn't grok it.
 *
 * Written by reading the System V Interface Definition, not the code.
 *
 * Totally public domain.
 */
/*LINTLIBRARY*/

#include <search.h>
#include "search-node.h"

/* find datum in search tree */
void*
tfind(key, rp, compar)
    const void  *key;           /* key to be located */
    void        *const*rp;      /* address of tree root */
    int         (*compar)();    /* ordering function */
{
    register node *q;
    register node **rootp = (node**)rp;         /* address of tree root */

    if (rootp == (struct node_t **)0)
        return 0;
    while (*rootp != (struct node_t *)0)        /* Knuth's T1: */
    {
        int r;

        if ((r = (*compar)(key, (*rootp)->key)) == 0)   /* T2: */
            return &(*rootp)->key;              /* we found it! */
        rootp = (r < 0) ?
            &(*rootp)->left :                   /* T3: follow left branch */
            &(*rootp)->right;                   /* T4: follow right branch */
    }
    return 0;
}
------End tfind.c

------Begin tsearch.c
/*
 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
 * the AT&T man page says.
 *
 * The node_t structure is for internal use only, lint doesn't grok it.
 *
 * Written by reading the System V Interface Definition, not the code.
 *
 * Totally public domain.
 */
/*LINTLIBRARY*/

#include <search.h>
#include "search-node.h"

void *tsearch(key, rp, compar)
/* find or insert datum into search tree */
const void      *key;           /* key to be located */
void    **rp;                   /* address of tree root */
int     (*compar)();            /* ordering function */
{
    register node *q;
    register node       **rootp = (node**)rp;   /* address of tree root */

    if (rootp == (struct node_t **)0)
        return 0;
    while (*rootp != (struct node_t *)0)        /* Knuth's T1: */
    {
        int r;

        if ((r = (*compar)(key, (*rootp)->key)) == 0)   /* T2: */
            return &(*rootp)->key;              /* we found it! */
        rootp = (r < 0) ?
            &(*rootp)->left :                   /* T3: follow left branch */
            &(*rootp)->right;                   /* T4: follow right branch */
    }
    q = (node *) malloc(sizeof(node));          /* T5: key not found */
    if (q != (struct node_t *)0)                /* make new node */
    {
        *rootp = q;                             /* link new node to old */
        q->key = key;                           /* initialize new node */
        q->left = q->right = (struct node_t *)0;
    }
    return &q->key;
}
------End tsearch.c

------Begin twalk.c
/*
 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
 * the AT&T man page says.
 *
 * The node_t structure is for internal use only, lint doesn't grok it.
 *
 * Written by reading the System V Interface Definition, not the code.
 *
 * Totally public domain.
 */
/*LINTLIBRARY*/

#include <search.h>
#include "search-node.h"

static void trecurse(root, action, level)
/* Walk the nodes of a tree */
register const node     *root;          /* Root of the tree to be walked */
register void   (*action)();    /* Function to be called at each node */
register int    level;
{
    if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0)
        (*action)(&root->key, leaf, level);
    else
    {
        (*action)(&root->key, preorder, level);
        if (root->left != (struct node_t *)0)
            trecurse(root->left, action, level + 1);
        (*action)(&root->key, postorder, level);
        if (root->right != (struct node_t *)0)
            trecurse(root->right, action, level + 1);
        (*action)(&root->key, endorder, level);
    }
}

void twalk(rt, action)          /* Walk the nodes of a tree */
const void      *rt;            /* Root of the tree to be walked */
void    (*action)();            /* Function to be called at each node */
{
    const node  *root = (const node*)rt;/* Root of the tree to be walked */

    if (root != (node *)0 && action != (void(*)())0)
        trecurse(root, action, 0);
}
------End twalk.c