標籤: Data Structure

Tables Lib v.0.1

No Comments

由 c string 組成的字串群,由字串群 strings 組成的陣列表格 table,由表格群雙向鏈結組成的 tables。
此函式庫使可便於在這些表格群中存取任一張表格,支援常用的一些資料結構行為之操作。
這些表格鏈結起來後,第一張表格所在位置為 level 0,第二張為 level 1,以此類推。另也有相對位置的操作;現下的物件為 level 0,下一個為 level 1 以此類推。
另外,表格中的最後一個元素必須是 “”,如下所示。原生表格長的樣子如下。
簡單講,此函式庫之應用,立基在表格群中相鄰兩張表格具有前後順序之關係時並且存取上具時間區域性/temporal locality of access。

mytable voc_tbl0={
    "xiao jie",
    "dai ma ce shi",
    "ce shi wan bi",
    ""
};

mytable voc_tbl1={
    "bei jing",
    "shang hai",
    "kai deng",
    "guan deng",
    ""
};

mytable voc_tbl2={
    "guang zhou",
    "shen zhen",
    "xiang zuo zhuan",
    "xiang you zhuan",
    ""
};

mytable voc_tbl3={
    "da kai kong tiao",
    "guan bi kong tiao",
    "hou tui",
    ""
};

應用考量 - LoadishTables Lib

剛完成此 Tables.Lib,就踢到鐵板了;並非是此 lib 沒什麼實用性或有什麼問題或短板,而是筆者沒注意到眼前有一張硬錚錚的鐵板。
廢話不多說,前面提到 string/table 會在程式啟動時由 bootloader 載入到記憶體,更衍申地說,此型別的 data 是可以不用載入到記憶體的(字串通常都是 read only 的,故僅存於 flash 即可),一旦用到時直接從 flash 去取即可,如同對待當執行每一行程式碼本身,是 CPU 直接去 flash 取出來的/fetch code。但此 bootloader 的實作,選擇將(所有)其載入到記憶體,以加速存取,這是美意,也規避掉了一些先天上的問題/flash alignment issue。不過若是有大量 tables 要用,那就是災難了;程式都還沒開始跑,嵌入式系統的受限記憶體,就將被浪費殆盡。因此,要運用大量 tables 我們就要反其道而行,使其不會被載入到記憶體,要用時才去取才恰當。
嵌入式系統通常是 UMA 架構,且也包含了 mapped io。簡化講也就是所有資源都與記憶體位址有一對一的對應;存取資源等同存取記憶體;以存取記憶體的方式存取之等同存取資源/不過也有些限制或需額外的處置如才剛提到的 flash alignment 問題。
因此一旦解決掉上述問題/不載入記憶體,我們便需要一些特別的 libc 函式去作載入等動作。
而全載入嗎?那豈不是白搭?故,
看來就要再包一支函式庫了,LoadishTables.Lib,以解決前述幾個問題。將再新開一篇文章。預計,此函式庫會 maintain,新函式庫會繼承此函式庫。
我們將從本篇的函式庫及底下的程式片斷作出發。底下的程式碼是分別定義了指定只存於並只由使用者取於 flash 的字串及字串表;字串表其實就是字串位址群所構成的陣列而同樣地耗空間的。
而將要實作的概念上是,此時,字串群(宇集),及由不同的子集的字串群(位址)組成的不同的陣列即不同的表格,全都存在 flash 上且早在編譯時期就已由使用者定義出來了。
那麼首先,使用者的程式碼本身必記錄下一步將要取用的某表格的位址(A on flash)。

存取該表格內容,表示必須先將位於該位址上的陣列(A on flash)從 flash 作載入至 RAM B。載入後,我們得到每條字串的位址其排列於此陣列(B on RAM)中。
接著,i 巡訪該陣列(B),將每條字串(on flash)作載入到 RAM,C[i][j],其中尾 j,代表該字串長度。而 C[i] 則代表該字串新的位址,我們需要把此新的位址回寫到此陣列(B),而此陣列位址 B 即是位於 RAM 中的表格位址。
問題是若我們使用二維方陣 C[i][j],則因字串有長有短將取最長者為邊,故乃需針對個別字串作配置才恰當。
至此好像就把 LoadishTables 說完了。不過是該再提醒一下魔鬼細節。
字串群,已由 FSTR 群所全定義完。
表格群,是由 FTBL 群所全定義完。
套用 LoadishTables{Tables.Lib}.Lib,我們將是存取這些 FTBLs 的位址,儘管還是位於 flash 但至此還未違反 Tables.Lib 的預期行為。
更確立地說,我們將會把 FTBLs 一一加入 Tables.Lib。因 LoadishTables.Lib 會設定載入記憶體,筆數的上界;例如 3。那麼,每加入一筆 FTBL 便會自動載入記憶體,加入第 4 筆 FTBL 或以上,都將不會載入記憶體。
接著,pointer 在 linked-tables 中游移,將會保持以此 pointer 為首的接續 2 筆都有載入記憶體,原先佔用的都將被釋放。slide window 的概念。
不過這細節太魔鬼,slide window 的性質還有待盤算,說不定一一載入即可/即筆數上界為 1。又或延遲釋放即可(即 FIFO/應是選它吧/精確地說應該是有上界地緩增緩刪就像遊戲走地圖一樣)。
還有更變態的。字串的載入是效率上最大的瓶頸。與其實作上述的 slide window,不如實現字串群的 LRU/MRU/FIFO 等之機制;但其很大相依於應用本身。
以上說得很簡單,看的人應該十個有八個會罷寫吧。。。

typedef const char _F_STR[];    // a const chars array.

#define FSTR(x, y) _F_STR x PROGMEM=(y) // this const chars array is in the flash. so we can use FSTR(var_name, "the string");

typedef const char *const _F_TBL[]; // const pointers/addresses of const chars arrays in the const array.

#define FTBL(x, ...) _F_TBL x PROGMEM={ __VA_ARGS__ } // the table in the flash. FTBL(var_name, "the"F, "strings"F, "in flash"F);

Categories: Arduino

Tags: ,

PHP Code Snippets Powered By : XYZScripts.com