Repositories » libk0
Clone URL:  
Pushed to one repository · View In Graph Contained in tip

Non-recursive lookup and insert (nrtlookup, nrinsert) for the BST were
incorrect. They were rewritten.

Changeset 801015b4c7b1

Parent c42fe6b97290

by Rup Palchowdhury

Changes to 3 files · Browse files at 801015b4c7b1 Showing diff from parent c42fe6b97290 Diff from another changeset...

Change 1 of 2 Show Entire File ktree.c Stacked
 
38
39
40
41
 
 
 
42
43
 
44
45
46
47
48
49
50
51
52
53
54
55
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
56
57
58
 
 
59
60
61
 
72
73
74
75
 
76
77
78
79
 
 
 
 
80
81
 
82
83
 
84
85
 
86
87
88
 
38
39
40
 
41
42
43
44
 
45
46
 
 
 
 
 
 
 
 
 
 
 
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
 
63
64
65
66
67
 
78
79
80
 
81
82
83
 
 
84
85
86
87
88
 
89
90
 
91
92
 
93
94
95
96
@@ -38,24 +38,30 @@
  return p;  }   -TNode *nrinsert(TNode *p, TNode *n, int (*tnodecmp)(void*, void*)) +TNode *nrinsert(TNode *treep, TNode *newp, + int (*tnodecmp)(void*, void*), + int (*match_handler)(void*, void*))  { - TNode *i; + TNode *r, **p;   int cmp; - if (p == NULL) - return n; - i = p; - while (i != NULL) { - cmp = (*tnodecmp)(n->data, p->data); - if (cmp == 0) - /* ignore duplicates */; - else if (cmp < 0) - i = i->l; - else - i = i->r; + if (treep == NULL) + return newp; + r = treep; + p = &treep; + while (*p != NULL) { + cmp = (*tnodecmp)(newp->data, (*p)->data); + if (cmp == 0) { + if (match_handler != NULL) + (*match_handler)((*p)->data, newp->data); + return r; + } + else if (cmp < 0) + p = &((*p)->l); + else + p = &((*p)->r);   } - i = n; - return p; + *p = newp; + return r;  }    TNode *tlookup(TNode *p, TNode *n, int (*tnodecmp)(void*, void*)) @@ -72,17 +78,19 @@
  return tlookup(p->r, n, tnodecmp);  }   -TNode *nrtlookup(TNode *p, TNode *n, int (*tnodecmp)(void*, void*)) +TNode *nrtlookup(TNode *treep, TNode *newp, int (*tnodecmp)(void*, void*))  {   int cmp; - while (p != NULL) { - cmp = (*tnodecmp)(n->data, p->data); + TNode **p; + p = &treep; + while (*p != NULL) { + cmp = (*tnodecmp)(newp->data, (*p)->data);   if (cmp == 0) - return p; + return *p;   else if (cmp < 0) - p = p->l; + p = &((*p)->l);   else - p = p->r; + p = &((*p)->r);   }   return NULL;  }
Change 1 of 1 Show Entire File ktree.h Stacked
 
11
12
13
14
 
 
 
15
16
17
 
11
12
13
 
14
15
16
17
18
19
@@ -11,7 +11,9 @@
 TNode *insert(TNode*, TNode*,   int (*tnodecmp)(void*, void*),   int (*match_handler)(void*, void*)); -TNode *nrinsert(TNode*, TNode*, int (*tnodecmp)(void*, void*)); +TNode *nrinsert(TNode*, TNode*, + int (*tnodecmp)(void*, void*), + int (*match_handler)(void*, void*));  TNode *tlookup(TNode*, TNode*, int (*tnodecmp)(void*, void*));  TNode *nrtlookup(TNode*, TNode*, int (*tnodecmp)(void*, void*));  void applyinorder(TNode*, void (*fn)(void*, void*), void*);
Change 1 of 1 Show Entire File test.c Stacked
 
38
39
40
41
 
42
43
44
 
45
 
 
 
 
 
 
 
46
47
48
49
50
51
 
 
52
53
54
 
38
39
40
 
41
42
43
 
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
58
59
60
61
62
@@ -38,17 +38,25 @@
  */     /* tree test */ - + TNode *found;   t = NULL;   for (i = 0; i < NUMNODES; i++) - t = insert(t, newtnode((void *)newpost(s[i], 1)), + t = nrinsert(t, newtnode(newpost(s[i], 1)),   postcmp, post_match_handler); + found = tlookup(t, newtnode(newpost("h", 1)), postcmp); + if (found != NULL) + printpost(found->data, "tlookup: %s %d\n"); + found = nrtlookup(t, newtnode(newpost("h", 1)), postcmp); + if (found != NULL) + printpost(found->data, "nrtlookup: %s %d\n"); + /*   printf("inorder:\n");   applyinorder(t, printpost, "%s %d\n");   printf("\n");   printf("postorder:\n");   applypostorder(t, printpost, "%s %d\n"); - + */ +   /* list test */     /* n = newnode((void *)newpost(s[1], 1)); */