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

16

18

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

32

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

46

48

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

92

94

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

редадрстойносткоментар
1057
21100
3233
4321
5417
651
766
8718
9881
10928
111083
121138
131285
141368
151487
161588
171689
181712
191823
201977
2130019// array size
223012000// tree root
233023// offset to last tree el
2440015// 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
Memorysize:4k
 
00I: rA <-- #0
22I: rA --> M
44A: rBs1 <-- #arrBeginning
66A: rX1 <-- #0
88A: rMaxX <-- MarraySize
1010A: rBs3 <-- MtreeRoot
1212call #CreateTree
1414call #Sort
1616A: rIP <-- #end
18
20
22CreateTree18I: rA <-- M[rBs1, ]0
2420I: rA --> M[rBs3, ]0
2622I: rA <-- #0
2824I: rA --> M[rBs3, ]1
3026I: rA --> M[rBs3, ]2Clear left pointer
3228I: rA --> M[rBs3, ]3Clear rigth pointer
3430A: rX1 <-- #1
36
38loopArray32A: IfMaxX rX1 > rMaxX ; #endCreateTree
4034I: rA <-- M[rBs1, rX1]0
4236call #FindPlaceForEl
4438A: IncX rX1 #1
4640A: rIP <-- #loopArray
48endCreateTree42ret 0
50
52
54FindPlaceForEl44I: push rB
5646A: push rX1
5848A: push rX2
6050A: push rX3
6252A: push rMaxX
6454A: rX1 <-- M treeRoot
6656A: rMaxX <-- #0
68nextEl58A: rX1 --> A: rX30
7060I: rB <-- M[, rX1]0
7262I: if ( A > B ) jump #lrPointer
7464A: IncX rX1 #1
76lrPointer66A: IncX rX1 #2
7868A: rX1 --> A: rX20
8070A: rX1 <-- M[, rX1]0
8272A: IfMaxX rX1 < rMaxX ; #nextEl
8474A: push rX3
8676A: push rX2
8878I: push rA
9080call #AddEl
9282A: pop rMaxX
9484A: pop rX3
9686A: pop rX2
9888A: pop rX1
10090I: pop rB
10292ret
104
106
108AddEl94I: push rA
11096I: push rB
11298A: push rX1
114100A: push rBs3
116102A: push rX3
118
120104I: rA <-- MofsLastTreeEl
122106I: rB <-- #4
124108I: AplsB --< A: rX3
126110A: rX3 --< M ofsLastTreeEl
128112A: rSP --< A: rX1
130114I: rA <-- M[, rX1]7
132116A: rX2 <-- M[, rX1]8
134118I: rB <-- M[, rX1]9
136120A: rBs3 <-- M treeRoot
138122I: rA --< M[rBs3, rX3]0
140124I: rB --< M[rBs3, rX3]1
142126I: rA <-- #0
144128I: rA --< M[rBs3, rX3]2
146130I: rA --< M[rBs3, rX3]3
148132A: rBs3 --< I: rA
150134A: rX3 --< I: rB
152136I: AplsB --< M[, rX2]
154
156138A: pop rX30
158140A: pop rBs30
160142A: pop rX10
162144I: pop rB0
164146I: pop rA0
166148ret 3
168
170
172 Sort150A: push rX10
174
176152A: rX1 <-- M treeRoot
178154A: push rX1
180156call #VisitNode
182
184158A: pop rX1
186160ret 0
188
190
192 VisitNode162A: push rX1
194164A: push rX2
196166A: push rMaxX
198
200168A: rMaxX <-- #0
202170A: rSP --> A: rX1
204172A: rX1 <-- M[, rX1]5
206174A: IfMaxX rX1 == rMaxX ; #endVisitNode
208176A: rX2 <-- M[, rX1]2
210178A: push rX2
212180call #VisitNode
214182A: push rX1
216184call #SaveElInArray
218186A: rX2 <-- M[, rX1]3
220188A: push rX2
222190call #VisitNode
224
226endVisitNode192A: pop rMaxX
228194A: pop rX2
230196A: pop rX1
232198ret 1
234
236
238SaveElInArray200I: push rA
240202A: push rMaxX
242204A: push rX1
244206A: push rX3
246208A: push rBs3
248
250210A: rBs3 <-- #arrBeginning
252212A: rX3 <-- M posInArray
254214A: rSP --> A: rX1
256216A: rX1 <-- M[, rX1]7
258218A:IfMaxXrX1==rMaxX;#endSaveElInArray
260220I: rA <-- M[, rX1]0
262222I: rA --> M[rBs3, rX3]0
264224A: IncX rX3 #1
266226A: rX3 --> M posInArray
268
270 endSaveElInArray228A: pop rBs3
272230A: pop rX3
274232A: pop rX1
276234A: pop rMaxX
278236I: pop rA
280238ret 1
282
284
286end240ENDPRG


Data part; Start address 1000

редетикетадрстойносткоментар
1arrBeginning057
21100
3233
4321
5417
651
766
8718
9881
10928
111083
121138
131285
141368
151487
161588
171689
181712
191823
201977
21 arraySize30019// array size
22 treeRoot3012000// tree root
23 ofsLastTreeEl3020// offset to last tree el
24 posInArray3030// 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 реда код на асемблер правим обхождане на дърво. При това се ползват само регистри от адресният модул. А ако компресираме инструкциите ?