C++

Forum

 
Conditional Jump

TheInterface1 (16)
Hi I'm working on this tree based map implementation and I'm getting a conditional jump error in my find() method. I know this means I'm accessing uninitialized values but as far as I can tell everything is initialized in the insert method. Maybe I missed something?

Insert method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
template <typename KEY, typename T>
bool Map<KEY,T>::insert(KEY k, T v){
	if( _root->left == _root ){
		_root->left = new Elem;
		_root->left->key = k;
		_root->left->data = v;
		_root->left->left = nullptr;
		_root->left->right = _root;
		_root->left->rightThread = true;
		_size++;
		return true;
	}
		return insert( _root->left, k , v, _root );
}

template <typename KEY, typename T>
bool Map<KEY,T>::insert(Elem *& root, const KEY &key, const T &data, Elem *lastLeft){
	if( !root ){
		root = new Elem;
    root->left = nullptr;
    root->right = lastLeft;
    root->key = key;
    root->data = data;
		root->rightThread = true;
    _size++;
    return true;
	}
	else if( root->key == key )
		return false;
	else if( key > root->key && root->rightThread ){
		root->right = nullptr;
		root->rightThread = false;
		return insert( root->right, key, data, lastLeft );
	}
	else if( key > root->key ){
		return insert( root->right, key, data, lastLeft );
	}
	else if( key < root->key ){
		return insert( root->left, key, data, root );
	}
	return false;
}

template <typename KEY, typename T>
bool Map<KEY,T>::erase(KEY k ){
	if( _size == 0 )
		return false;
	if( _size == 1 ){
		delete _root->left;
		_root->left = _root;
		_size = 0;
		return true;
	}
//		cout << "erase" << endl;
	if( find(k) == end() )
		return false;
	Elem* par = _root;
	Elem* cur = _root->left;
	while( cur->key != k ){
		if( k < cur->key ){
			par = cur;
			cur = cur->left;
		}
		if( k > cur->key){
			par = cur;
			cur = cur->right;
		}
	}

//-------------no children-----------------------------------------------
	if( !cur->left && cur->rightThread ){
		if( par->right == cur ){
			par->right = cur->right;
			par->rightThread = true;
		}
		if( par->left == cur ){
			par->left = nullptr;
		}
		_size--;
		delete cur;
		return true;
	}
//-------------------------left only---------------------------------------
	if( cur->left && cur->rightThread ){
		if( par->left == cur ){
			par->left = cur->left;
			Elem* rethread = cur->left;
			while( !rethread->rightThread)
				rethread = rethread->right;
			rethread->right = par;
		}
		if( par->right == cur ){
			par->right = cur->left;
			Elem* rethread = cur->left;
			while( !rethread->rightThread)
				rethread = rethread->right;
			rethread->right = cur->right;
		}
		_size--;
		delete cur;
		return true;
	}
	//-------------------------right only-----------------------------------
		if( !cur->left && !cur->rightThread ){
			if( cur == par->left ){
				par->left = cur->right;
			}
			if( cur == par->right ){
				par->right = cur->right;
				par->rightThread = cur->rightThread;
			}
			_size--;
			delete cur;
			return true;
		}
	//-------------------------two children------------------------------
	Elem* sux = cur->right;
	while( sux->left ){
		sux = sux->left;
	}
	KEY kk = sux->key;
	T tt = sux->data;
	erase( kk );
	if( _size == 0 ){
		_root->left = _root;
	}
	cur->key = kk;
	cur->data = tt;
	return true;
}


find method
1
2
3
4
5
6
7
8
9
10
11
 
template <typename KEY, typename T>
typename Map<KEY, T>::Iterator Map<KEY, T>::find(KEY k) const{
	Map<KEY, T>::Iterator it = begin();
	while( it != end() ){
		if( it->key && it->key == k ){
			return it;
		}
		it++;
	}
	return end();
}
Last edited on
tpb (1495)
@TheInterface1,

How exactly are you getting this error?
Just running the program normally?
Or running it in something like valgrind?
You should copy/paste the entire error message.

I don't see anything obvious.
You need to post a runnable version of your program (or a link to a zip file).
TheInterface1 (16)
tpb (1495)
I assume by your reticence that I am to make the supplied test and run it normally. I did so and it seems to run fine.

How exactly are you running it? Just normally? And are you sure you're running maptest6.cpp?

Copy/paste the exact text of the error message.
TheInterface1 (16)
It's a valgrind check. I get a bunch of errors like this

1
2
3
4
5
6
7
8
9
10
11
12
 
==13287== Conditional jump or move depends on uninitialised value(s)
==13287==    at 0x40220F: Map<int, int>::erase(int) (in /home/csu/jkf1008/cs515/9P/maptest)
==13287==    by 0x401A3E: main (in /home/csu/jkf1008/cs515/9P/maptest)
==13287==
==13287== Conditional jump or move depends on uninitialised value(s)
==13287==    at 0x401A99: main (in /home/csu/jkf1008/cs515/9P/maptest)
==13287==
4 6 21 29 42 45
==13287== Conditional jump or move depends on uninitialised value(s)
==13287==    at 0x4028D4: Map<int, int>::find(int) const (in /home/csu/jkf1008/cs515/9P/maptest)
==13287==    by 0x4021F9: Map<int, int>::erase(int) (in /home/csu/jkf1008/cs515/9P/maptest)
==13287==    by 0x401AF4: main (in /home/csu/jkf1008/cs515/9P/maptest)
Last edited on
tpb (1495)
I can't see what's wrong with it, but here's a shorter main that still causes the warning.

1
2
3
4
5
6
7
8
 
#include "map.h"

int main() {
    Map<int,int> m1;
    m1.insert(40,1);
    m1.insert(12,1);  // need to add at least two
    m1.erase(30);  // same problem with 40 (an existing element)
}

tpb (1495)
You've implemented the Iterator operator== and operator!= incorrectly. You need to compare the _cur pointers, not the keys that they point to. In particular, the dummy _root node has an uninitialized key and data, so that's what valgrind is talking about.
Topic archived. No new replies allowed.