da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/***********************************************************************
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* This software is part of the ast package *
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner* Copyright (c) 1985-2010 AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* and is licensed under the *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Common Public License, Version 1.0 *
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin* by AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* A copy of the License is available at *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Information and Software Systems Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* AT&T Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Florham Park NJ *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Glenn Fowler <gsf@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* David Korn <dgk@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Phong Vo <kpv@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin***********************************************************************/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * tsearch() for systems that have <search.h> but no tsearch()
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * why would such a system provide the interface but not the
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * implementation? that's what happens when one slimes their
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * way through standards compliance
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * NOTE: please excuse the crude feature test
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* POSIX tsearch library based on libcdt
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** Written by Kiem-Phong Vo (AT&T Research, 07/19/95)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define extern __EXPORT__
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* compare function */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic int treecompare(Dt_t* dt, char* one, char* two, Dtdisc_t* disc)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return (*((Treedisc_t*)disc)->comparf)((Void_t*)one,(Void_t*)two);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin (!(dt = *((Dt_t**)rootp)) && !(dt = dtopen((Dtdisc_t*)(&Treedisc),Dtorder))) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin /* dangerous to set comparf on each call but that's tsearch */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return (o = (Tree_t*)dtmatch(dt,key)) ? (Void_t*)(&o->key) : NIL(Void_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* the original tdelete() specifies that it will return the parent pointer
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** in the tree if there is one. Since we are using a splay tree, a deleted
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** node is always rotated to the root first. So this implementation always
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** returns the key of the new root.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* the below routine assumes a particular layout of Dtlink_t.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** If this ever gets changed, this routine should be redone.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic void _twalk(Tree_t* obj, void(*action)(const Void_t*,VISIT,int), int level)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* the original twalk allows specifying arbitrary node to start traversal.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** Since our root is a dictionary structure, the search here will start
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** at whichever node happens to be current root.