Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chapter 6 Data Types – part 2 (Pointers (Pointers in C and C++…
Chapter 6
Data Types – part 2
Record Types
定義 : 由各種不同type的資料組成，透過name來辨識各個元素 ( e.g C, C++, C# : struct )
設計議題
欄位參考的句法形式為何?
是否允許elliptical(省略) references?
與array的不同
參考方式
Array : 透過index
Record (fileds) : 透過identifier(names) e.g.apple.weight
欄位參考方式
方向
由外而內 : Others(.)
由內而外 : COBOL(OF)
寫法
完全資格參考 : 需include所有record name
省略參考 : 可以省略某些record name，只要不會ambigous就好
Operations
指派、比較、初始化
評估( 與Array比較 )
Record通常用於data value為
異質
時
存取array元素的速度 < record欄位 。(因為field name是靜態，而subscripts是動態 -> array記憶體位置需要計算)
dynamic subscripts
可以
被用於record filed的存取，但這樣就沒有型別檢查，速度也較慢。
實作(:fire::fire::fire:p.6-11圖)
fields儲存在相鄰的記憶體位置
Record, Field1{Name, Type, Offset}, ..., FieldN{...}
Field的存取，靠的就是這些
offset address
Unions Types
定義 : 在不同的時間，儲存不同型態的value
設計議題
是否需要型別檢查?
Unions是否被嵌入在record中
緣由
因早期記憶體空間不足，在變數不會同時使用時可共用記憶體
Free Unions (:fire::fire::fire:p.6-18圖)
定義 : Fortran, C, and C++提供union construct，但
不支援型別檢查
，此類稱之。
Discriminated(判別) Unions
定義 : union的型別檢查須包含型別指示符，稱為
discriminant
or
tag
( e.g.Ada )
評估
在某些語言中可能unsafe(沒有型別檢查)
Java、C#不支援union(可見對安全性的考量↑)
實作 (:fire::fire::fire:p.6-22圖)
Pointers
指標變數的範圍值 : 由memeory address、nil所組組成
用途 : 間接定址(常用於組合語言)、動態記憶體管理(
heap
)
設計議題
指標變數的
scope
與
lifetime
?
語言是否支援pointer types or reference types? 或兩者皆是?
指標被用於動態儲存管理or間接定址? 或兩者皆是?
pointer是否只能指向同一種型態的值?
heap-dynamic variable的lifetime?
基本Operations (2種)
Assignment
: 將指標指向
記憶體位址
Dereferencing
(反參考) : 根據指標指的位置，取出其值(可分為explict與implict)
當指標指向Records
(*p).age = p->age
指標的問題 (:fire::fire::fire:圖 p.6-32)
Dangling pointers
(懸浮指標)
定義 : 指標指向一個
已被刪除
的heap-dynamic variable
危害
該位置可能已經被分配給一個新的變數了
新變數的值可能會被摧毀
該位置可能已暫時被儲存管理系統所占用
Lost heap-dynamic variable
定義 : 已配置記憶體的heap-dynamic variable再也無法被user program存取(稱為
garbage
)
Memory leakage
(記憶體流失) : 遺失heap-dynamic variable的過程，稱之。
解決方式
Ada
Dangling pointers
暗示型 de-allocation ↑ : 變數在其指標型態的scope結束後自動de-allcote
明示型 de-allocation ↓ :明示型 de-allocation為懸浮指標的主要來源
Lost heap-dynamic variable
沒有解決
Pointers in C and C++
非常方便，但須小心使用
指標除了可指向heap，也可指向function
用於動態儲存管理與定址
指標也可以進行算數(p6-36範例)
明示型反參考、傳址運算子(&)
型態不須固定(e.g.
void *
: 可指向任何型態，型別檢查OK，但不能反參照)
Function Pointer
說明 : 用來指向function的指標 (:fire::fire::fire:例子 p.6-35 )
指標 in 各語言
C and C++
陣列名稱
就像一個constant pointer
Fortran 95
可指向heap與non-heap的變數
暗示型反參照
C++ Reference Types
Pointer : 可以指過來指過去
Reference : 從一而終都是指向一個東西 (暗示型反參考)
具有pass-by-reference and passby-value兩者的優點
評估
指標像是
goto
，使得memory cell可被變數存取的範圍變寬
指標或參考都需要動態的資料結構(設計語言時不能缺少)
指標的表示方法(:fire::fire::fire:p.43圖)
大型電腦 : 使用single value
intel微處理器 : 使用
segment
(起始位置)與
offset
(目前存取位置)
懸浮指標的解決方法
Tombstone
(:fire::fire::fire:p.44圖)
作法
tombstone : 使用額外的heap cell指向heap-dynamic variable
將實際的指標變數指向tombstone
當heap-dynamic variable被de-alloceated時，tombstone保留但將之設為nil
缺點 : 耗時與耗空間 (tombstone永遠不會被deallocated)
Locks-and-keys
(:fire::fire::fire:p.45圖)
Pointer values表示成(key, address)
Heap-dynamic變數表示成 : lock cell + 變數
當allocate一個heap-dynamic variable時，將一個lock value同時放到 lock cell 與 key cell中
Type Checking
名詞
Compatible type
對operator來說是合法的
可以被
編譯器暗示convert
，形成合法型別 ( 稱為
coercion
)
Type error : 使用了錯誤型態的operator (e.g 在應放float的function中放數int參數)
Type Checking : 確認operator的operand型別是否兼容
type checking是 static/dynamic ?
取決於 type binding的方式
Strongly typed
(強型別)
定義 : 可以偵測到所有的type error (C、C++ : X , Java、C# : O)
強制轉換會使strong程度↓
Ada > Java, C# > C, C++，更接近strongly typed
Type Compatibility(型別相容性)
如何判定是否相容?
預定義標量型別 : 易於判定
結構化、使用者定義型別 : 需使用
型別等價規則
(無強制轉換)
Type equivalence rules(型別等價規則)
Name type equivalence
( 名稱類型等價 )
定義 : 同時宣告的，或宣告時type name相同
評估 : 實作簡單，但限制性高 (e.g interger與Indextype其實一樣都是整數)
Structure type equivalence
( 結構類型等價 )
定義 : 若有相同架構則算等價
評估 : 較彈性，但實作困難
議題
(1) 架構相同， 但欄位名稱不同
(2) 相同的陣列，但index範圍不同
(3) 枚舉架構相同，僅元件拼寫不同
(4) 在結構型態相容下，無法區分不同的單位 ( e.g 速度: 公尺/腳步，都是float)
Heap Management
說明 : 一種非常複雜的run-time process，負責回收memory、掌握目前有多少可用空間
分類
Single-size cells
方法
參考計數器
方法
每個cell都有一個計數器，來計算目前有多少指標指向它
if (counter = 0) -> 該cell為garbage，並丟進可用空間串列
缺點
占空間 - 若有很多個cell，則需要許多空間
花時間 - 只要有指標值改變就要再做一次
複雜化 - 當memory cell 連成cycle時，每一個cell的參考計數器之值 >= 1
(:fire::fire::fire:圖p.6-62 ) 問題 : 連結斷裂時，若存在cycle，依然無法被回收(互指counter !=0)
說明 : (急切)漸進式回收
垃圾收集
說明 : (懶散)空間不足時才開始回收
方法
cell間dis-connected時，不主動做回收(垃圾累積)
空間不足時，執行
mark-sweep process
(標記掃描處理)
步驟(:fire::fire::fire:圖p.6-64 )
把所有cell都標記成垃圾
標記階段 : 把所heap內的指標掃過一次，有被掃到的cell就標為
非
垃圾
掃描階段 : 把所有的垃圾歸還給可用空間
缺點 : 效率差(必須把memory跑過一次)
variable-size cells
比Single-size cells難
若使用垃圾收集
標記複雜 : 沒有預設的指標位置，每個cell都得添加內部指標
維護可用空間列表成本高 : 相鄰的小區塊能被需要被摺疊成大區塊
初始化難 : 不知道每個cell的大小
大多數語言都需要