00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014 #include <sys/cdefs.h>
00015 #define _SEARCH_PRIVATE
00016 #include <tsearch.h>
00017 #include <stdlib.h>
00018
00019
00020 void *
00021 tsearch(vkey, vrootp, compar)
00022 const void *vkey;
00023 void **vrootp;
00024 int (*compar)(const void *, const void *);
00025 {
00026 node_t *q;
00027 node_t **rootp = (node_t **)vrootp;
00028
00029 if (rootp == NULL)
00030 return NULL;
00031
00032 while (*rootp != NULL) {
00033 int r;
00034
00035 if ((r = (*compar)(vkey, (*rootp)->key)) == 0)
00036 return *rootp;
00037
00038 rootp = (r < 0) ?
00039 &(*rootp)->llink :
00040 &(*rootp)->rlink;
00041 }
00042
00043 q = malloc(sizeof(node_t));
00044 if (q != 0) {
00045 *rootp = q;
00046
00047 q->key = (void *)vkey;
00048 q->llink = q->rlink = NULL;
00049 }
00050 return q;
00051 }
00052
00053
00054 void *
00055 tfind(vkey, vrootp, compar)
00056 const void *vkey;
00057 void * const *vrootp;
00058 int (*compar)(const void *, const void *);
00059 {
00060 node_t **rootp = (node_t **)vrootp;
00061
00062 if (rootp == NULL)
00063 return NULL;
00064
00065 while (*rootp != NULL) {
00066 int r;
00067
00068 if ((r = (*compar)(vkey, (*rootp)->key)) == 0)
00069 return *rootp;
00070 rootp = (r < 0) ?
00071 &(*rootp)->llink :
00072 &(*rootp)->rlink;
00073 }
00074 return NULL;
00075 }
00076
00077
00078
00079
00080
00081
00082
00083
00084 void *
00085 tdelete(const void * __restrict vkey, void ** __restrict vrootp,
00086 int (*compar)(const void *, const void *))
00087 {
00088 node_t **rootp = (node_t **)vrootp;
00089 node_t *p, *q, *r;
00090 int cmp;
00091
00092 if (rootp == NULL || (p = *rootp) == NULL)
00093 return NULL;
00094
00095 while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
00096 p = *rootp;
00097 rootp = (cmp < 0) ?
00098 &(*rootp)->llink :
00099 &(*rootp)->rlink;
00100 if (*rootp == NULL)
00101 return NULL;
00102 }
00103 r = (*rootp)->rlink;
00104 if ((q = (*rootp)->llink) == NULL)
00105 q = r;
00106 else if (r != NULL) {
00107 if (r->llink == NULL) {
00108 r->llink = q;
00109 q = r;
00110 } else {
00111 for (q = r->llink; q->llink != NULL; q = r->llink)
00112 r = q;
00113 r->llink = q->rlink;
00114 q->llink = (*rootp)->llink;
00115 q->rlink = (*rootp)->rlink;
00116 }
00117 }
00118 free(*rootp);
00119 *rootp = q;
00120 return p;
00121 }
00122
00123