RCPU

My dream CPU

V. Примерни програми

Част 3. Двоични дтрвета

Създаване на двоично дърво

Тази програма взима данните от масив с начало адрес 1000 и създава дървовидна структура. Root на дървовидната структура се намира на адрес 2000. Всъщност елементите на това дърво физически ще са в масив с начало адрес 2000. Всеки елемент на масива съдържа стойност, указател към ляв клон и указател към десен клон.

Init CPU

IP: 100

SP: 4095

Memory size:4k

0 0I: rA <-- #0

2 2I: rA --> M1302

4 4A: rBs1 <-- #1000

6 6A: rX1 <-- #0

8 8A: rMaxX <-- M1300

10 10 A: rBs3 <-- M1301

12 12 call #16 // call Create tree

14 14A: rIP <-- #134 // goto end

20 16 I: rA <-- M[rBs1,]0// proc Create Tree;

22 18 I: rA --> M[rBs3,]0

24 20 I: rA <-- #0

26 22 I: rA --> M[rBs3,]1

28 24 I: rA --> M[rBs3,]2

30 26A: rX1 <-- #1

34 28 A: IfMaxX rX1 > rMaxX ; #38 // Begginning loop array

36 30 I: rA <-- M[rBs1,rX1]0

38 32 call #40

40 34 A: IncX rX1 #1

42 36 A: rIP <-- # 8// End Loop

44 38 ret 0

50 40 I: push rB // proc Find_place_For_El(rA)

52 42 A: push rX1

54 44 A: push rX2

56 4 A: push rMaxX

58 48 A: rX1 <-- M1301

60 50 A: rMaxX <-- #0

62 52 I: rB <-- M[,rX1]0

64 54 I: if ( A > B ) jump #58

66 56 A: IncX rX1 #1

68 58 A: IncX rX1 #1

70 60 A: rX1 --> A:rX2

72 62 A: rX1 <-- M[,rX1]

74 64 A: IfMaxX rX1 > rMaxX ; #52

76 66 A: push rX2

78 68 I: push rA

80 70 call #82

82 72 A: pop rMaxX

84 74 A: pop rX2

86 76 A: pop rX1

88 78 I: pop rB

90 80 ret

96 82 I: push rA // proc AddEl

98 84 I: push rB

100 86A: push rX1

102 88A: push rBs3

104 90A: push rX3

106 92 I: rA <-- M1302

108 94 I: rB <-- #3

110 96 I: AplsB --> A:rX3

112 98A: rX3 --> M1302

114 100A: rSP --> A:rX1

116 102I: rA <-- M[,rX1]7

118 104A: rX2 <-- M[,rX1]8

120 106A: rBs3 <-- M1301

122 108 I: rA -->M[rBs3, rX3]0

124 110I: rA <-- #0

126 112I: rA --> M[rBs3, rX3]1

128 114I: rA --> M[rBs3, rX3]2

130 116A: rBs3 --> I:rA

132 118A: rX3 --> I:rB

134 120I: AplsB --> M[, rX2]

136 122A: pop rX3

138 124A: pop rBs3

140 126A: pop rX1

142 128I: pop rB

144 130I: pop rA

146 132ret 2 // end proc AddEl

148

150

152 134ENDPRG

Data part. Start adr: 1000

ред	адр	стойност	коментар
1	0	57
2	1	100
3	2	33
4	3	21
5	4	17
6	5	1
7	6	6
8	7	18
9	8	81
10	9	28
11	10	83
12	11	38
13	12	85
14	13	68
15	14	87
16	15	88
17	16	89
18	17	12
19	18	23
20	19	77
21	300	19	// array size
22	301	2000	// tree root
23	302	3	// offset to last tree el
24	400	15	// array size

От адрес 0 до адрес 14 е main частта на програмата. На адрес 4 се зарежда rBs1 с началото на масива в който са данните. Адрес 8 се зарежда rMaxX с размера на масива. На адрес 8 rBs3 се зарежда с адреса в който ще се постави root елемента на дървото. Всички тези състояния на регистрите са параметри на процедурата която се вика от инструкцията на адрес 12 call #16, CreateTree. Това е предаване на параметри през регистрите. Инструкцията на адрес 14 препраща към краят на програмата.

Процедурата CreateTree започва от адрес 16. От адрес 16 до адрес 26 тя взима първият елемент от масива и го поставя за първи елемент на дървото. От адрес 28 до адрес 26 има цикъл в който се четат елементи от масива, зареждат се в регистър rA и се вика процедурата FindPlaceForElement чрез call #40. Тя приема rA за параметър.

Процедурата FindPlaceForElement започва от адрес 40. Целта на тази процедура е да намери на кое място в дървото да постави стойността от rA.

Първите няколко push операции съхраняват съдържанието на регистрите в стека. Запазват се само регистрите които ще се използват от процедурата. Така накрая процедурата има и 4 pop инструкции в обратен ред за да възстанови стойностите в тези регистри след изпълнението на самата процедура.

Инструкцията на адрес 52 чете елемент от дървото и го поставя в rB, на адрес 54 той се сравнява с rA на когото търсим място в масива. И от това дали е по-малък или по-голям се взима съответно левият или десният указател на текущият елемент от дървото. Инструкцията на адрес 64 проверява новият указател за null ( 0 ). Ако не е null препраща в началото на цикъла на адрес 52. Ако е 0, се поставят параметрите в стека чрез push операции. Push rX2 поставя в стека адресът, който ще сочи към новият елемент. До сега тази клетка е била със съдържание 0. Като се заеме място за новият елемент, тази клетка ще съдържа адресът и. Push rA поставя в стека стойността за която ще се създаде нов възел в дървото. На адрес 70 се прави call #82 което извиква процедура AddElInTree.

Както споменах по-горе процедурата завършва с няколко pop операции за да възстанови регистрите и инструкцията ret, връщане от процедура. Тя взима от стека адресът на инструкцията, след мястото от което е извикана процедурата. Този адрес се поставя в стека от инструкцията call и се взима от ret за да продължи изпълнението на програмата след извиканата процедура.

Процедурата AddEl взима от адрес 1302 отместването до последният елемент на дървото. Увеличава го с 3, защото толкова е размерът на елемент от дървото и го записва обратно. Изважда параметрите от стека и ги записва на новоизчисленият адрес. Инструкцията на адрес 120 записва този адрес в елементът родител на текущият.

Двоично дърво и обхождане на елементите

Тази примерна програма е базирана на предишната. Разликата е че елементите на дървото съдържат указател и към елементът техен родител. Дървото се обхожда, като при обхождането стойностите от елементите на дървото се записват върху масивът от който са взети за да се създаде дървото. Като краен резултат елементите в масива са сортирани.

Използват се и етикети които силно облекчават писането на програми на асемблер. Без етикетите, добавянето или премахването на ред от програмата прави всички инструкции с преход грешни.

Листинг на програмата:

IP:		100
SP:		4095
Memory	size:	4k

0		0	I: rA <-- #0
2		2	I: rA --> M
4		4	A: rBs1 <-- #arrBeginning
6		6	A: rX1 <-- #0
8		8	A: rMaxX <-- MarraySize
10		10	A: rBs3 <-- MtreeRoot
12		12	call #CreateTree
14		14	call #Sort
16		16	A: rIP <-- #end
18
20
22	CreateTree	18	I: rA <-- M[rBs1, ]0
24		20	I: rA --> M[rBs3, ]0
26		22	I: rA <-- #0
28		24	I: rA --> M[rBs3, ]1
30		26	I: rA --> M[rBs3, ]2	Clear left pointer
32		28	I: rA --> M[rBs3, ]3	Clear rigth pointer
34		30	A: rX1 <-- #1
36
38	loopArray	32	A: IfMaxX rX1 > rMaxX ; #endCreateTree
40		34	I: rA <-- M[rBs1, rX1]0
42		36	call #FindPlaceForEl
44		38	A: IncX rX1 #1
46		40	A: rIP <-- #loopArray
48	endCreateTree	42	ret 0
50
52
54	FindPlaceForEl	44	I: push rB
56		46	A: push rX1
58		48	A: push rX2
60		50	A: push rX3
62		52	A: push rMaxX
64		54	A: rX1 <-- M treeRoot
66		56	A: rMaxX <-- #0
68	nextEl	58	A: rX1 --> A: rX30
70		60	I: rB <-- M[, rX1]0
72		62	I: if ( A > B ) jump #lrPointer
74		64	A: IncX rX1 #1
76	lrPointer	66	A: IncX rX1 #2
78		68	A: rX1 --> A: rX20
80		70	A: rX1 <-- M[, rX1]0
82		72	A: IfMaxX rX1 < rMaxX ; #nextEl
84		74	A: push rX3
86		76	A: push rX2
88		78	I: push rA
90		80	call #AddEl
92		82	A: pop rMaxX
94		84	A: pop rX3
96		86	A: pop rX2
98		88	A: pop rX1
100		90	I: pop rB
102		92	ret
104
106
108	AddEl	94	I: push rA
110		96	I: push rB
112		98	A: push rX1
114		100	A: push rBs3
116		102	A: push rX3
118
120		104	I: rA <-- MofsLastTreeEl
122		106	I: rB <-- #4
124		108	I: AplsB --< A: rX3
126		110	A: rX3 --< M ofsLastTreeEl
128		112	A: rSP --< A: rX1
130		114	I: rA <-- M[, rX1]7
132		116	A: rX2 <-- M[, rX1]8
134		118	I: rB <-- M[, rX1]9
136		120	A: rBs3 <-- M treeRoot
138		122	I: rA --< M[rBs3, rX3]0
140		124	I: rB --< M[rBs3, rX3]1
142		126	I: rA <-- #0
144		128	I: rA --< M[rBs3, rX3]2
146		130	I: rA --< M[rBs3, rX3]3
148		132	A: rBs3 --< I: rA
150		134	A: rX3 --< I: rB
152		136	I: AplsB --< M[, rX2]
154
156		138	A: pop rX30
158		140	A: pop rBs30
160		142	A: pop rX10
162		144	I: pop rB0
164		146	I: pop rA0
166		148	ret 3
168
170
172	Sort	150	A: push rX10
174
176		152	A: rX1 <-- M treeRoot
178		154	A: push rX1
180		156	call #VisitNode
182
184		158	A: pop rX1
186		160	ret 0
188
190
192	VisitNode	162	A: push rX1
194		164	A: push rX2
196		166	A: push rMaxX
198
200		168	A: rMaxX <-- #0
202		170	A: rSP --> A: rX1
204		172	A: rX1 <-- M[, rX1]5
206		174	A: IfMaxX rX1 == rMaxX ; #endVisitNode
208		176	A: rX2 <-- M[, rX1]2
210		178	A: push rX2
212		180	call #VisitNode
214		182	A: push rX1
216		184	call #SaveElInArray
218		186	A: rX2 <-- M[, rX1]3
220		188	A: push rX2
222		190	call #VisitNode
224
226	endVisitNode	192	A: pop rMaxX
228		194	A: pop rX2
230		196	A: pop rX1
232		198	ret 1
234
236
238	SaveElInArray	200	I: push rA
240		202	A: push rMaxX
242		204	A: push rX1
244		206	A: push rX3
246		208	A: push rBs3
248
250		210	A: rBs3 <-- #arrBeginning
252		212	A: rX3 <-- M posInArray
254		214	A: rSP --> A: rX1
256		216	A: rX1 <-- M[, rX1]7
258		218	A:IfMaxXrX1==rMaxX;#endSaveElInArray
260		220	I: rA <-- M[, rX1]0
262		222	I: rA --> M[rBs3, rX3]0
264		224	A: IncX rX3 #1
266		226	A: rX3 --> M posInArray
268
270	endSaveElInArray	228	A: pop rBs3
272		230	A: pop rX3
274		232	A: pop rX1
276		234	A: pop rMaxX
278		236	I: pop rA
280		238	ret 1
282
284
286	end	240	ENDPRG

Data part; Start address 1000

ред	етикет	адр	стойност	коментар
1	arrBeginning	0	57
2		1	100
3		2	33
4		3	21
5		4	17
6		5	1
7		6	6
8		7	18
9		8	81
10		9	28
11		10	83
12		11	38
13		12	85
14		13	68
15		14	87
16		15	88
17		16	89
18		17	12
19		18	23
20		19	77
21	arraySize	300	19	// array size
22	treeRoot	301	2000	// tree root
23	ofsLastTreeEl	302	0	// offset to last tree el
24	posInArray	303	0	// position in array

Main частта на програмата е от адрес 0 до адрес 16. Тя е същата единствено е добавен ред call # Sort, след call #CreateTree.

След като е изпълнена процедурата CreateTree дървото е създадено и се вика call #Sort. Процедурата Sort взима адреса на root елемента на дървото поставя го в стека и вика процедурата VisitNode.

VisitNode е процедура в която има рекурсия ( викане на функция от самата себе си ). Тя прочита подаденият и параметър през стека и го проверява за null. Ако е null това означава, че е достигнат елемент който няма наследник. Ако не е null тя прочита указателят му към левият наследник, поставя го в стека и вика себе си. По този начин стига до следващ елемент който е отляво. След като се върне от рекурсията ще извика call #SaveElInArray която ще запише елемента в масива. След това ще вземе десният указател, ще го постави в стека и пак ще повика себе си.

Тази процедура викайки себе си стига до най-левият си елемент. Като се върне от него първо го записва в масива и след това посещава десният му елемент. Като се върне от него отива едно ниво нагоре в дървото и посещава десният клон на горният възел, като преди това записва стойността на левият възел. Така се обхожда цялото дърво. Елементът с най-малка стойност е в най-левият елемент. Елементът с най-голяма стойност е в най-десният елемент. При обхождането елементите се обхождат по големина.

За да сортираме в обратна посока има 2 варианта.

Първият е да обърнем дървото, тоест най-големият елемент да е отляво, а най-малкият отдясно. Тук е достатъчно да се обърне посоката за сравнение в адрес
62 I: if ( A > B ) jump #lrPointer

Вторият начин е просто да запълваме масива отдолу нагоре.

Процедурата SaveElInArray е съвсем проста. Тя взима подаденият и като параметър адрес на елемент от дървото. Прочита от posInArray индекса на последният записан елемент. Проверява указателят за null, ако не е null го записва . Мястото на което ще го запише се изчислява от началото на масива плюс индекс posInArray. PosInArray е адрес ( етикет ) на клетка от паметта. След запис го инкрементира с 1.

Вижте още веднъж процедурата VisitNode. Като изключим няколкото push/pop инструкции само за 12 реда код на асемблер правим обхождане на дърво. При това се ползват само регистри от адресният модул. А ако компресираме инструкциите ?