В программировании микроконтроллеров первая задача, которую всегда приходится решать - это определить в каком порядке производить инициализацию прошивки. Дело в том, что прошивка состоит из набора программных компонентов. Каждый компонент как правило вызывает функции из других программных компонентов. Это нормальное явление. Так происходит переиспользование кодовой базы.
При этом, чтобы код корректно работал надо начинать пользоваться программным компонентом только после того, как он будет проинициализирован. Инициализация это по сути настройка. У каждого программного компонента есть функция
bool xxx_init(void);
и надо понимать, когда эту функцию вызывать. То есть, до и после чего вызывать функцию xyz_init()?
В переводе на кухонный язык, каждое утро мы надеваем одежду, чтобы выйти на улицу. Понятное дело, что не имеет смысла надевать носки после того как надета обувь. Не имеет смысла надевать рубашку, когда надета куртка и т. п. Так же и в программировании микроконтроллеров. Нет смысла инициализировать подсистему UART, если не проинициализирован GPIO.
Проблема в том, что в каждой взрослой прошивке программных компонентов десятки. И зависимостей у каждого из них тоже много: по 5-7 штук. При этом программные компоненты пишут другие программисты, указывая только текстовый файлик с зависимостями для своего программного компонента. Одновременно с этим вам для конкретной сборки надо, по мере возможности, так выставить последовательность инициализации, чтобы всё корректно прогрузилось и по ходу не заклинило.
Основная трудность в том, что перед написанием кода инициализации не очевидна оптимальная последовательность инициализации системы.
Радость лишь в том, что эту задачу можно решить чисто формальными методами. То есть к этой проблеме можно подойти с точки зрения дискретной математики!
Постановка задачи
Есть неупорядоченное множество компонентов. Просто набор строк (токенов), разделённых запятой.
Button,FlashFs,I2S,Log,StartPause,Writer,NVIC,Clk,SysTick, Flash,Timer,GPIO,UART,Swd,ADC,I2C,SPI,CAN ,WatchDog,Pwm,DMA,Mcu,SwDac, RS485,StringReader,CLI,IsoTp, UDS,Relay,LedMono,NVS,Param,Heap,Time, SuperCycle,task,UnitTest,Nau8814
У каждого компонента есть зависимости. Как правило несколько. У каких-то тривиальных компонентов нет зависимостей.
start_pause,Clk Writer,UART Log UART Clk, Flash SysTick,Clk Timer, Clk GPIO, UART, GPIO Swd,GPIO... ADC,AdcChannels,.. I2C,GPIO UART SPI,GPIO UART CAN,GPIO I2S,GPIO DMA WatchDog, RS232,GPIO UART RS485,GPIO StringReader, CLI,RS232 Relay,GPIO Time LedMonoInit, NVS,Flash Flash_FS, NVS Flash Param, Flash_FS SuperCycle, task, SuperCycle
Получается ориентированный граф зависимостей программных компонентов. Вот, например, граф программных зависимостей для прошивки культового аппаратного менеджера паролей Pastilda
От нас требуется, не много не мало, упорядочить граф в последовательный массив компонентов так, чтобы те компоненты, у которых много зависимостей, оказались справа (>). Те, у которых мало зависимостей - слева (<). Формально надо обойти граф так, чтобы все зависимости были от следующих вершин к предыдущим. Только и всего...
В дискретной математике эту процедуру называют Топологическая Сортировка ациклического графа.
Разумеется, надо написать компьютерную программу, которая и будет делать всю эту работу за нас. Или найти и воспользоваться какой-то другой готовой широко известной утилитой для этого.
Решение. Основная идея.
Ситуация осложняется еще и тем, что граф зависимостей программных компонентов это как бы два или три отдельных графа. Обычно это даже и не дерево, а лес.
Есть специальные алгоритмы для построения этого обхода. Однако они требуют динамического выделения памяти и рекурсию. Мне, как программисту микроконтроллеров, это делать не привычно, ибо во всех прошивках для МК всегда есть два золотых MISRA запрета:
1--Запрет на динамическую память.
2--Запрет на рекурсию.
Поэтому я изложу одно из наивных решений этой задачи, оперируя даже не графами, а строчками!
Итак, танцуем от печки... Пусть у нас есть вот такой простецкий граф зависимостей.
Идея очень проста. Объясню на примере. Допустим надо проинициализировать условные программные компоненты g,n,a, t.
Фаза 1 (Вставка)
На первом шаге мы просто на место каждого элемента в строке подставляем сам компонент и его зависимости. Вот так.
Фаза 2 (Удалить повторы)
В результирующей строке следует удалить повторы. То есть w. Причем, удалять надо слева (<). Ибо компонент уже проинициализировался справа (>). Повторная инициализация не имеет смысла, а порой и вовсе приводит к заклиниванию и осечкам в прошивке.
Фаза 3 (Повтор)
Продолжая эти процедуры замены (фаза1 ) и удаления повторов слева (фаза2 ) после нескольких итераций кристаллизируется решение задачи.
Фаза 4 (Зеркальное отражение)
Инвертировать элементы в финальной последовательности. В сухом остатке остается последовательность c y k t o b a p x l w q v n j q.
Проверка показывает, что обход всегда происходит вдоль рёбер ориентации графа. Это хорошая новость. Значит, что решение корректное.
Практическая часть.
Теперь следует реализовать этот алгоритм в коде. Причем желательно на Си, ибо сами прошивки мы пишем на Си. Поэтому репозиторий уже обогащён проверенными наработками по обработке формата CSV и алгоритмам на строчках.
Я написал на Си консольную Win утилиту, которая делает всю эту обработку текстовых CSV строчек. В качестве файла с зависимостями я подал на вход описание леса
ADC,GPIO,NVIC,DMA AdcChannels Array Audio,SwDac,Math Button,GPIO,Time CAN,GPIO,NVIC,DMA CRC Cli,Log,StringReader Clk,StartPause DID DMA,NVIC,DmaChannels DmaChannels Fifo Flash,Array FlashFs,NVS,Flash GPIO,Time Heap I2C,GPIO,NVIC,DMA I2S,GPIO,SPI,NVIC,DMA Intervals IsoTp,CAN,Time LedMono,GPIO,Time,Math Limiter,Time,Flash Log,Time,Writer Math NVIC NVS,Flash,CRC,Intervals Nau8814,I2S,I2C,GPIO,Pwm,Task,Cli,Audio Param,Flash,FlashFs Pwm,GPIO,Timer RS232,UART,Fifo RS485,UART,Fifo Relay,GPIO,Time SPI,GPIO,Time,DMA StartPause, Stream,Fifo String,Array StringReader,Fifo,UART,String SuperCycle,Task,Time SwDac,Array,Math,Time,Heap Swd,GPIO SysTick,Clk,NVIC Task,Time,Flash,Limiter Time,Timer,SysTick Timer,Clk,NVIC,Math,DMA UART,GPIO,Fifo,Time,NVIC,DMA UDS,IsoTp,DID,CAN UnitTest,Cli WatchDog,Clk Writer,Stream
в ка��естве набора компонентов я подал CSV строку
StartPause,Writer,Log,NVIC,Clk,SysTick,Flash, Timer,GPIO,UART,Swd,ADC,AdcChannels,I2C,SPI, CAN,I2S,WatchDog,Pwm,DMA,DmaChannels,SwDac,RS232, RS485,StringReader,Cli,IsoTp,UDS,DID,Relay,LedMono, NVS,FlashFs,Param,Heap,Time,SuperCycle,Task,Button,UnitTest,Nau8814
В результате утилита любезнейшим образом порекомендовала мне выполнить инициализацию системы вот в такой последовательности:
Math,Heap,NVIC,,StartPause,Clk,SysTick, DmaChannels,DMA,Timer,Time,Array,SwDac,Audio,String, Fifo,GPIO,UART,StringReader,Stream,Writer,Log,Cli,Flash, Limiter,Task,Pwm,I2C,SPI,I2S,Nau8814,UnitTest,Button, SuperCycle,Intervals,CRC,NVS,FlashFs,Param,LedMono,Relay, DID,CAN,IsoTp,UDS,RS485,RS232,WatchDog,ADC,Swd,AdcChannels
Интуитивно это выглядит тоже вполне корректно. Вот мы и получили план по загрузке прошивки. Никакой импровизации, всё формально математически обосновано.
Основной Си-код с решением
#include "topo_sort.h" #include <math.h> #include <math.h> #include <stddef.h> #include <string.h> #include <stdio.h> #include "str_utils_ex.h" #include "topo_sort_diag.h" #include "log.h" #include "code_generator.h" #include "csv.h" #define RES_SIZE 5000 #define ONE_DEP_SIZE 1000 #define MAX_DEP_LIST 200 typedef struct { char name[ONE_DEP_SIZE]; bool valid; uint32_t size; uint32_t child_cnt; }DepNode_t; #define TOPO_SORT_COMMON_VARIABLES \ uint8_t num; \ char* name; \ bool valid; typedef struct { TOPO_SORT_COMMON_VARIABLES DepNode_t DepArray[MAX_DEP_LIST]; char result[RES_SIZE]; char result2[RES_SIZE]; }TopoSortHandle_t; typedef struct { TOPO_SORT_COMMON_VARIABLES }TopoSortConfig_t; COMPONENT_GET_NODE(TopoSort, topo_sort) COMPONENT_GET_CONFIG(TopoSort, topo_sort) bool topo_sort_init_custom(void) { bool res = true ; LG_level_get_set(LINE, LG_LEVEL_INFO ); LG_level_get_set(TOPO_SORT, LG_LEVEL_INFO ); return res; } static DepNode_t* TopoSortNameToDep(TopoSortHandle_t* Node, char* name){ DepNode_t* Dep = NULL; uint32_t i = 0 ; bool res = false; uint32_t cnt = MAX_DEP_LIST; for(i=0;i<cnt;i++) { if(Node->DepArray[i].valid) { char node_name[100]={0}; res = csv_parse_text(Node->DepArray[i].name, ',', 0, node_name, sizeof(node_name)); if(res) { int ret = 0; ret=strcmp(name,node_name); if(0==ret){ Dep=&Node->DepArray[i]; } } } } return Dep; } bool csv_delete_duplicat_left(char * csv_text){ bool res = false ; if(csv_text){ uint32_t node_cnt=0; node_cnt = csv_cnt(csv_text, ','); LG_PARN(TOPO_SORT, "SwCnt:[%u]", node_cnt); uint32_t i = 0; for(i=0; i<node_cnt; i++) { LG_PARN(TOPO_SORT, "%u:Text[%s]",i, csv_text); char node_name[100] = {0}; res = csv_parse_text(csv_text, ',', i, node_name, sizeof(node_name)); if(res) { int ret = 0 ; ret = strcmp("",node_name); if(0!=ret) { uint32_t dup_cnt = csv_count_node(csv_text, ',' ,node_name); if(1 < dup_cnt) { LG_DEBUG(TOPO_SORT, "%u:Duplicant:[%s][%u]",i, node_name,dup_cnt); uint32_t d=0; for(d=0 ; d<(dup_cnt-1); d++){ char temp[200] = {0}; snprintf(temp,sizeof(temp),",%s,",node_name); LG_DEBUG(TOPO_SORT, "TryDel[%s]",temp); //str_del_substr_inplace_firts(csv_text, temp); //res = replace_substring_first( csv_text, temp, ",") ; replaceFirstOccurrence( csv_text, temp, ",") ; i=0; } } } } else { LG_ERROR(TOPO_SORT, "%u:NoNode",i); } node_cnt = csv_cnt(csv_text, ','); LG_PARN(TOPO_SORT, "SwCnt:[%u]", node_cnt); } } return res; } bool topo_sort_proc_ll(TopoSortHandle_t* Node){ bool res = false ; if(Node) { LG_DEBUG(TOPO_SORT, "Proc:"); memset(Node->result2,0,sizeof(Node->result2)); uint32_t node_cnt = csv_cnt(Node->result, ','); LG_DEBUG(TOPO_SORT, "SwCnt:[%u]", node_cnt); uint32_t i = 0; for(i=0;i<node_cnt;i++) { char node_name[200] = {0}; res = csv_parse_text(Node->result, ',', i, node_name, sizeof(node_name)); if(res) { DepNode_t* DepNode=TopoSortNameToDep(Node, node_name); if(DepNode) { LG_DEBUG(TOPO_SORT, "i:%u,+Deps[%s]", i,DepNode->name); if(0<i) { sprintf(Node->result2,"%s,%s",Node->result2,DepNode->name); } else { sprintf(Node->result2,"%s",DepNode->name); } LG_PARN(TOPO_SORT, "%u,Raw[%s]",i, Node->result2); }else{ LG_ERROR(TOPO_SORT, "NoDeps:i:%u,[%s]", i,node_name); } }else{ LG_ERROR(TOPO_SORT, "Err:i:%u", i); } } LG_DEBUG(TOPO_SORT, "Raw[%s]", Node->result2); /*Delete duplicat from left*/ res =csv_delete_duplicat_left(Node->result2); LG_WARNING(TOPO_SORT, "-Dups[%s]", Node->result2); memcpy(Node->result,Node->result2,sizeof(Node->result2)); } return res; } bool topo_sort_load_dep(uint8_t num, char* const sw_dep){ bool res = false ; LG_WARNING(TOPO_SORT, "LoadDep:[%s]", sw_dep); TopoSortHandle_t* Node=TopoSortGetNode(num); if(Node){ strcpy(Node->result, ""); strcpy(Node->result2, ""); FILE* FilePrt = NULL; char str_line[1000] = {0}; FilePrt = fopen(sw_dep, "r"); uint32_t cnt=0; if(FilePrt) { strcpy(str_line, ""); LG_INFO(TOPO_SORT, "File [%s] OpenOk", sw_dep); while(NULL != fgets(str_line, sizeof(str_line), FilePrt)) { size_t len=strlen(str_line); if(len){ uint32_t node_cnt = csv_cnt(str_line, ','); LG_INFO(TOPO_SORT, "+L:%u,[%s]%u],DepCnt:[%u]",cnt,str_line,len, node_cnt); str_del_char_inplace(str_line, '\n'); str_del_char_inplace(str_line, '\r'); memset(Node->DepArray[cnt].name,0,sizeof(Node->DepArray[cnt].name)); memcpy(Node->DepArray[cnt].name,str_line,len-1); Node->DepArray[cnt].size = len-1; Node->DepArray[cnt].valid = true; Node->DepArray[cnt].child_cnt=node_cnt-1; char node_name[100]={0}; res = csv_parse_text(str_line, ',', 0, node_name, sizeof(node_name)); if(res){ LG_INFO(TOPO_SORT, "%u,SwCom:[%s]Child:%u",cnt, node_name,node_cnt-1); res = true; }else{ res = false; LG_ERROR(TOPO_SORT, "GetErr:%u",cnt); } } strcpy(str_line, ""); cnt++; } fclose(FilePrt); }else{ LG_ERROR(TOPO_SORT, "FileOpenErr"); } } return res; } bool topo_sort_run(uint8_t num, char* const sw_comps, char* const sw_dep){ bool res = false ; TopoSortHandle_t* Node=TopoSortGetNode(num); if(Node) { strcpy(Node->result, ""); LG_WARNING(TOPO_SORT, "GenerateInit:[%s]Dep:[%s]", sw_comps,sw_dep); res = topo_sort_load_dep(num, sw_dep); FILE* FilePrt = NULL; char csv_line[1000] = {0}; FilePrt = fopen(sw_comps, "r"); uint32_t cnt = 1; if(FilePrt) { LG_INFO(TOPO_SORT, "File [%s] OpenOk", sw_comps); strcpy(csv_line, ""); while(NULL != fgets(csv_line, sizeof(csv_line), FilePrt)) { uint32_t node_cnt = csv_cnt(csv_line, ','); LG_INFO(TOPO_SORT, "Line:%u,SwComCnt:[%u]",cnt, node_cnt); uint32_t i = 0 ; for(i=0;i<node_cnt;i++){ char node_name[100] = {0}; res = csv_parse_text(csv_line, ',', i, node_name, sizeof(node_name)); if (res) { LG_DEBUG(TOPO_SORT, "%u,SwCom:[%s]",i, node_name); if(0<cnt){ snprintf(Node->result,RES_SIZE,"%s,%s",Node->result,node_name); }else{ snprintf(Node->result,RES_SIZE,"%s",node_name); } uint32_t cnt = csv_cnt(Node->result, ','); LG_DEBUG(TOPO_SORT, "+Set:%u:[%s]",cnt, Node->result); } else { LG_ERROR(TOPO_SORT, "GetErr:%u",i); } } res = true; strcpy(csv_line, ""); cnt++; } fclose(FilePrt); }else{ LG_ERROR(TOPO_SORT, "FileOpenErr"); } uint32_t i=0 ; for(i=0;i<10;i++) { LG_NOTICE(TOPO_SORT, "Set:[%s]",Node->result); topo_sort_proc_ll(Node); } } return res; } bool topo_sort_init_one(uint8_t num) { LG_WARNING(TOPO_SORT, "INIT:%u", num); bool res = false; const TopoSortConfig_t* Config = TopoSortGetConfig(num); if(Config) { LG_WARNING(TOPO_SORT, "%s", TopoSortConfigToStr(Config)); TopoSortHandle_t* Node = TopoSortGetNode(num); if(Node) { Node->num = Config->num; Node->valid = true; memset(Node->result2,0,sizeof(Node->result2)); memset(Node->result,0,sizeof(Node->result)); strcpy(Node->result2,""); strcpy(Node->result,""); LG_level_get_set(TOPO_SORT, LG_LEVEL_INFO ); LG_level_get_set(LINE, LG_LEVEL_INFO ); res = true; } } return res; } COMPONENT_INIT_PATTERT(TOPO_SORT, TOPO_SORT, topo_sort)
Второй вариант
На самом деле чтобы решить эту продуктовую задачу даже не нужно писать никакого нового своего кода! Можно просто воспользоваться старой доброй всеядной культовой утилитой Стюарта Фельдмана make 1976 года. У этой утилиты так много профессий, что и перечислять устанешь. В частности эта утилита умеет обходить ориентированный граф зависимостей.
Сейчас объясню как... Вот тут в файле MakeTopoSort мы просто декларативно перечисляем с какими программными компонентами хотим работать.
INIT_ORDER += SW_COMP += UnitTest SW_COMP += StartPause SW_COMP += AdcChannels SW_COMP += Writer SW_COMP += CAN SW_COMP += Log SW_COMP += Clk SW_COMP += SysTick SW_COMP += Flash SW_COMP += Timer SW_COMP += Button SW_COMP += LedMono SW_COMP += FlashFs SW_COMP += GPIO SW_COMP += RS485 SW_COMP += Nau8814 SW_COMP += NVS SW_COMP += SPI SW_COMP += WatchDog SW_COMP += Cli SW_COMP += Pwm SW_COMP += DmaChannels SW_COMP += SwDac SW_COMP += RS232 SW_COMP += StringReader SW_COMP += DMA SW_COMP += IsoTp SW_COMP += I2C SW_COMP += UDS SW_COMP += DID SW_COMP += Relay SW_COMP += I2S SW_COMP += Heap SW_COMP += Swd SW_COMP += Param SW_COMP += UART SW_COMP += Time SW_COMP += SuperCycle SW_COMP += Task SW_COMP += NVIC SW_COMP += ADC include sw_comp_dep.mk init: $(SW_COMP) @echo $@ @echo $(info ORDER:[$(INIT_ORDER)]) @echo $(info SET:[$(SW_COMP)])
Указываем зависимости в другом файлике sw_comp_dep.mk
ADC: GPIO NVIC DMA AdcChannels @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt AdcChannels : @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Array : @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Audio :SwDac Math @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Button :GPIO Time @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt CAN :GPIO NVIC DMA @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt CRC : @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Cli :Log StringReader @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Clk :StartPause @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt DID : @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt DMA :NVIC DmaChannels @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt DmaChannels : @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Fifo : @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Flash :Array @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt FlashFs :NVS Flash @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt GPIO :Time @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Heap : @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt I2C :GPIO NVIC DMA @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt I2S :GPIO SPI NVIC DMA @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Intervals : @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt IsoTp :CAN Time @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt LedMono : GPIO Time Math @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Limiter :Time Flash @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Log :Time Writer @echo $@ @echo $@ >> init.txt $(eval INIT_ORDER += $@) Math : @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt NVIC : @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt NVS :Flash CRC Intervals @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Nau8814 :I2S I2C GPIO Pwm Task Cli Audio @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Param :Flash FlashFs @echo $(info $@ ) $(eval INIT_ORDER += $@) @echo $@ >> init.txt Pwm :GPIO Timer @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt RS232 :UART Fifo @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt RS485 :UART Fifo @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Relay :GPIO Time @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt SPI :GPIO Time DMA @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt StartPause : @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Stream :Fifo @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt String :Array @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt StringReader :Fifo UART String @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt SuperCycle :Task Time @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt SwDac :Array Math Time Heap @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Swd :GPIO @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt SysTick :Clk NVIC @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Task :Time Flash Limiter @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Time :Timer SysTick @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Timer :Clk NVIC Math DMA @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt UART :GPIO Fifo Time NVIC DMA @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt UDS :IsoTp DID CAN @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt UnitTest :Cli UDS Param @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt WatchDog :Clk @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt Writer :Stream @echo $@ $(eval INIT_ORDER += $@) @echo $@ >> init.txt
и запускаем *.bat скрипт
cls echo off set batdir=%~dp0 echo batdir=%batdir% cd %batdir% echo > init.txt make.exe --always-make --file=MakeTopoSort -i -k init
Получаем результат
В этой же папке кристаллизируется файл init.txt, который и содержит правильную последовательность инициализации. Вот она на вашем экране:
StartPause,Clk,NVIC,Math,DmaChannels,DMA,Timer,SysTick, Time,Fifo,Stream,Writer,Log,GPIO,UART,Array,String,StringReader, Cli,CAN,IsoTp,DID,UDS,Flash,CRC,Intervals,NVS,FlashFs,Param, UnitTest,AdcChannels,Button,LedMono,RS485,SPI,I2S,I2C,Pwm,Limiter, Task,Heap,SwDac,Audio,Nau8814,WatchDog,RS232,Relay,Swd,SuperCycle,ADC,
Успех!
Развитие задачи
I) Топологическая сортировка текстовых токенов может быть также весьма полезна при монтаже электронных плат PCB.
На то есть две причины:
1--Дело в том, что существуют такие электронные компоненты, что припаяв один элемент, не влезет очередной элемент расположенный рядом.
2--Бывает так, что плату проверяют уже во время построения. Например, нет смысла припаивать микроконтроллер, если не собраны каскады питания и кварцевый генератор не выдает нужную частоту. Иначе вы просто соберёте бракованное изделие. История была такая уже не один раз.
По сути, эту же консольную утилиту make можно использовать для планирования работ по пайке электронных компонентов на PCB.
Так можно автоматически составлять инструкции для сборки абсолютно чего угодно, не только PCB, начиная от двигателя внутреннего сгорания заканчивая авиалайнером.
II) Также топологическая сортировка может пригодится менеджерам для составления плана работ по воплощению какого-либо проекта. Той же разработки ПО или аппаратуру. Можно сформировать учебный план для института. Да всё что угодно, где так или иначе есть то, что должно быть сделано в первую очередь.
Итоги
Удалось разработать методику выработки корректной последовательности инициализации программных компонентов в прошивке для микроконтроллеров.
Удалось составить консольную Cи утилиту, которая находит топологическую сортировку для графа на основе списка смежности. Также удалось научиться делать топологическую сортировку утилитой make.
Это открывает дорогу для автоматической генерации массива инициализации на основе графа зависимостей между программными компонентами.
Надеюсь этот текст будет полезен программистам, схемотехникам и менеджерам для выполнения топологической сортировки по разным причинам.
Links
№ | Название | URL |
1 | Генерация зависимостей внутри программы | |
2 | Топологическая сортировка графа | |
4 | Топологическая сортировка | |
5 | Магия makefile на простых примерах | https://microsin.net/programming/arm/learning-makefile-with-simple-examples.html |
6 | Change Makefile variable value inside the target body | https://stackoverflow.com/questions/2711963/change-makefile-variable-value-inside-the-target-body |
