|
Packit |
992a25 |
/***********************************************************************
|
|
Packit |
992a25 |
* *
|
|
Packit |
992a25 |
* This software is part of the ast package *
|
|
Packit |
992a25 |
* Copyright (c) 1985-2011 AT&T Intellectual Property *
|
|
Packit |
992a25 |
* and is licensed under the *
|
|
Packit |
992a25 |
* Eclipse Public License, Version 1.0 *
|
|
Packit |
992a25 |
* by AT&T Intellectual Property *
|
|
Packit |
992a25 |
* *
|
|
Packit |
992a25 |
* A copy of the License is available at *
|
|
Packit |
992a25 |
* http://www.eclipse.org/org/documents/epl-v10.html *
|
|
Packit |
992a25 |
* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
|
|
Packit |
992a25 |
* *
|
|
Packit |
992a25 |
* Information and Software Systems Research *
|
|
Packit |
992a25 |
* AT&T Research *
|
|
Packit |
992a25 |
* Florham Park NJ *
|
|
Packit |
992a25 |
* *
|
|
Packit |
992a25 |
* Glenn Fowler <gsf@research.att.com> *
|
|
Packit |
992a25 |
* David Korn <dgk@research.att.com> *
|
|
Packit |
992a25 |
* Phong Vo <kpv@research.att.com> *
|
|
Packit |
992a25 |
* *
|
|
Packit |
992a25 |
***********************************************************************/
|
|
Packit |
992a25 |
/*
|
|
Packit |
992a25 |
* tsearch() for systems that have <search.h> but no tsearch()
|
|
Packit |
992a25 |
* why would such a system provide the interface but not the
|
|
Packit |
992a25 |
* implementation? that's what happens when one slimes their
|
|
Packit |
992a25 |
* way through standards compliance
|
|
Packit |
992a25 |
*
|
|
Packit |
992a25 |
* NOTE: please excuse the crude feature test
|
|
Packit |
992a25 |
*/
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
#if !_UWIN
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
void _STUB_tsearch(){}
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
#else
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
#if _PACKAGE_ast
|
|
Packit |
992a25 |
#include <ast.h>
|
|
Packit |
992a25 |
#endif
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
#define tdelete ______tdelete
|
|
Packit |
992a25 |
#define tfind ______tfind
|
|
Packit |
992a25 |
#define tsearch ______tsearch
|
|
Packit |
992a25 |
#define twalk ______twalk
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
#include <search.h>
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
#undef tdelete
|
|
Packit |
992a25 |
#undef tfind
|
|
Packit |
992a25 |
#undef tsearch
|
|
Packit |
992a25 |
#undef twalk
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
#include "dthdr.h"
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
extern Void_t* dtfinger(Dt_t*);
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
/* POSIX tsearch library based on libcdt
|
|
Packit |
992a25 |
** Written by Kiem-Phong Vo (AT&T Research, 07/19/95)
|
|
Packit |
992a25 |
*/
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
typedef struct _tree_s
|
|
Packit |
992a25 |
{ Dtlink_t link;
|
|
Packit |
992a25 |
Void_t* key;
|
|
Packit |
992a25 |
} Tree_t;
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
typedef struct _treedisc_s
|
|
Packit |
992a25 |
{ Dtdisc_t disc;
|
|
Packit |
992a25 |
int(* comparf)_ARG_((const Void_t*, const Void_t*));
|
|
Packit |
992a25 |
} Treedisc_t;
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
#if defined(__EXPORT__)
|
|
Packit |
992a25 |
#define extern __EXPORT__
|
|
Packit |
992a25 |
#endif
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
/* compare function */
|
|
Packit |
992a25 |
#if __STD_C
|
|
Packit |
992a25 |
static int treecompare(Dt_t* dt, char* one, char* two, Dtdisc_t* disc)
|
|
Packit |
992a25 |
#else
|
|
Packit |
992a25 |
static int treecompare(dt, one, two, disc)
|
|
Packit |
992a25 |
Dt_t* dt;
|
|
Packit |
992a25 |
char* one;
|
|
Packit |
992a25 |
char* two;
|
|
Packit |
992a25 |
Dtdisc_t* disc;
|
|
Packit |
992a25 |
#endif
|
|
Packit |
992a25 |
{
|
|
Packit |
992a25 |
return (*((Treedisc_t*)disc)->comparf)((Void_t*)one,(Void_t*)two);
|
|
Packit |
992a25 |
}
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
static Treedisc_t Treedisc =
|
|
Packit |
992a25 |
{ { sizeof(Dtlink_t), -1, /* object is key */
|
|
Packit |
992a25 |
0,
|
|
Packit |
992a25 |
NIL(Dtmake_f), NIL(Dtfree_f),
|
|
Packit |
992a25 |
treecompare,
|
|
Packit |
992a25 |
NIL(Dthash_f),
|
|
Packit |
992a25 |
NIL(Dtmemory_f),
|
|
Packit |
992a25 |
NIL(Dtevent_f)
|
|
Packit |
992a25 |
},
|
|
Packit |
992a25 |
0
|
|
Packit |
992a25 |
};
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
extern
|
|
Packit |
992a25 |
#if __STD_C
|
|
Packit |
992a25 |
Void_t* tsearch(const Void_t* key, Void_t** rootp,
|
|
Packit |
992a25 |
int(*comparf)(const Void_t*,const Void_t*) )
|
|
Packit |
992a25 |
#else
|
|
Packit |
992a25 |
Void_t* tsearch(key, rootp, comparf)
|
|
Packit |
992a25 |
Void_t* key;
|
|
Packit |
992a25 |
Void_t** rootp;
|
|
Packit |
992a25 |
int(* comparf)();
|
|
Packit |
992a25 |
#endif
|
|
Packit |
992a25 |
{
|
|
Packit |
992a25 |
reg Dt_t* dt;
|
|
Packit |
992a25 |
reg Tree_t* o;
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
if(!rootp ||
|
|
Packit |
992a25 |
(!(dt = *((Dt_t**)rootp)) && !(dt = dtopen((Dtdisc_t*)(&Treedisc),Dtoset))) )
|
|
Packit |
992a25 |
return NIL(Void_t*);
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
/* dangerous to set comparf on each call but that's tsearch */
|
|
Packit |
992a25 |
Treedisc.comparf = comparf;
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
if(!(o = (Tree_t*)dtmatch(dt,key)) )
|
|
Packit |
992a25 |
{ if(!(o = (Tree_t*)malloc(sizeof(Tree_t))) )
|
|
Packit |
992a25 |
return NIL(Void_t*);
|
|
Packit |
992a25 |
o->key = (Void_t*)key;
|
|
Packit |
992a25 |
dtinsert(dt,o);
|
|
Packit |
992a25 |
}
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
if(o)
|
|
Packit |
992a25 |
*rootp = (Void_t*)dt;
|
|
Packit |
992a25 |
else if(*rootp == NIL(Void_t*) )
|
|
Packit |
992a25 |
dtclose(dt);
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
return (Void_t*)(&o->key);
|
|
Packit |
992a25 |
}
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
extern
|
|
Packit |
992a25 |
#if __STD_C
|
|
Packit |
992a25 |
Void_t* tfind(const Void_t* key, Void_t*const* rootp,
|
|
Packit |
992a25 |
int(*comparf)(const Void_t*, const Void_t*) )
|
|
Packit |
992a25 |
#else
|
|
Packit |
992a25 |
Void_t* tfind(key, rootp, comparf)
|
|
Packit |
992a25 |
Void_t* key;
|
|
Packit |
992a25 |
Void_t** rootp;
|
|
Packit |
992a25 |
int(* comparf)();
|
|
Packit |
992a25 |
#endif
|
|
Packit |
992a25 |
{
|
|
Packit |
992a25 |
reg Dt_t* dt;
|
|
Packit |
992a25 |
reg Tree_t* o;
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
if(!rootp || !(dt = *((Dt_t**)rootp)) )
|
|
Packit |
992a25 |
return NIL(Void_t*);
|
|
Packit |
992a25 |
Treedisc.comparf = comparf;
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
return (o = (Tree_t*)dtmatch(dt,key)) ? (Void_t*)(&o->key) : NIL(Void_t*);
|
|
Packit |
992a25 |
}
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
/* the original tdelete() specifies that it will return the parent pointer
|
|
Packit |
992a25 |
** in the tree if there is one. Since we are using a splay tree, a deleted
|
|
Packit |
992a25 |
** node is always rotated to the root first. So this implementation always
|
|
Packit |
992a25 |
** returns the key of the new root.
|
|
Packit |
992a25 |
*/
|
|
Packit |
992a25 |
extern
|
|
Packit |
992a25 |
#if __STD_C
|
|
Packit |
992a25 |
Void_t* tdelete(const Void_t* key, Void_t** rootp,
|
|
Packit |
992a25 |
int(*comparf)(const Void_t*, const Void_t*) )
|
|
Packit |
992a25 |
#else
|
|
Packit |
992a25 |
Void_t* tdelete(key, rootp, comparf)
|
|
Packit |
992a25 |
Void_t* key;
|
|
Packit |
992a25 |
Void_t** rootp;
|
|
Packit |
992a25 |
int(* comparf)();
|
|
Packit |
992a25 |
#endif
|
|
Packit |
992a25 |
{
|
|
Packit |
992a25 |
reg Dt_t* dt;
|
|
Packit |
992a25 |
reg Tree_t* o;
|
|
Packit |
992a25 |
Tree_t obj;
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
if(!rootp || !(dt = *((Dt_t**)rootp)) )
|
|
Packit |
992a25 |
return NIL(Void_t*);
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
Treedisc.comparf = comparf;
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
obj.key = (Void_t*)key;
|
|
Packit |
992a25 |
dtdelete(dt,&obj);
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
if(!(o = dtfinger(dt)) )
|
|
Packit |
992a25 |
{ dtclose(dt);
|
|
Packit |
992a25 |
*rootp = NIL(Void_t*);
|
|
Packit |
992a25 |
}
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
return o ? (Void_t*)(&o->key) : NIL(Void_t*);
|
|
Packit |
992a25 |
}
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
/* the below routine assumes a particular layout of Dtlink_t.
|
|
Packit |
992a25 |
** If this ever gets changed, this routine should be redone.
|
|
Packit |
992a25 |
*/
|
|
Packit |
992a25 |
#define lchild link.lh.__left
|
|
Packit |
992a25 |
#define rchild link.rh.__rght
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
#if __STD_C
|
|
Packit |
992a25 |
static void _twalk(Tree_t* obj, void(*action)(const Void_t*,VISIT,int), int level)
|
|
Packit |
992a25 |
#else
|
|
Packit |
992a25 |
static void _twalk(obj,action,level)
|
|
Packit |
992a25 |
Tree_t* obj;
|
|
Packit |
992a25 |
void(* action)();
|
|
Packit |
992a25 |
int level;
|
|
Packit |
992a25 |
#endif
|
|
Packit |
992a25 |
{ if(!obj->lchild && !obj->rchild)
|
|
Packit |
992a25 |
(*action)((Void_t*)obj,leaf,level);
|
|
Packit |
992a25 |
else
|
|
Packit |
992a25 |
{ (*action)((Void_t*)obj,preorder,level);
|
|
Packit |
992a25 |
if(obj->lchild)
|
|
Packit |
992a25 |
_twalk((Tree_t*)obj->lchild,action,level+1);
|
|
Packit |
992a25 |
(*action)((Void_t*)obj,postorder,level);
|
|
Packit |
992a25 |
if(obj->rchild)
|
|
Packit |
992a25 |
_twalk((Tree_t*)obj->rchild,action,level+1);
|
|
Packit |
992a25 |
(*action)((Void_t*)obj,endorder,level);
|
|
Packit |
992a25 |
}
|
|
Packit |
992a25 |
}
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
/* the original twalk allows specifying arbitrary node to start traversal.
|
|
Packit |
992a25 |
** Since our root is a dictionary structure, the search here will start
|
|
Packit |
992a25 |
** at whichever node happens to be current root.
|
|
Packit |
992a25 |
*/
|
|
Packit |
992a25 |
extern
|
|
Packit |
992a25 |
#if __STD_C
|
|
Packit |
992a25 |
void twalk(const Void_t* root, void(*action)(const Void_t*,VISIT,int) )
|
|
Packit |
992a25 |
#else
|
|
Packit |
992a25 |
void twalk(root, action)
|
|
Packit |
992a25 |
Void_t* root;
|
|
Packit |
992a25 |
void(* action)();
|
|
Packit |
992a25 |
#endif
|
|
Packit |
992a25 |
{
|
|
Packit |
992a25 |
reg Tree_t* o;
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
if(root && (o = (Tree_t*)dtfinger((Dt_t*)root)) )
|
|
Packit |
992a25 |
_twalk(o,action,0);
|
|
Packit |
992a25 |
}
|
|
Packit |
992a25 |
|
|
Packit |
992a25 |
#endif
|