В программировании микроконтроллеров первая задача, которую всегда приходится решать - это определить в каком порядке производить инициализацию прошивки. Дело в том, что прошивка состоит из набора программных компонентов. Каждый компонент как правило вызывает функции из других программных компонентов. Это нормальное явление. Так происходит переиспользование кодовой базы.
При этом, чтобы код корректно работал надо начинать пользоваться программным компонентом только после того, как он будет проинициализирован. Инициализация это по сути настройка. У каждого программного компонента есть функция
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 |
Комментарии (49)
randomsimplenumber
04.06.2024 04:13+6Чтобы не выполнять приседания с кодированием зависимостей, рекурсией и прочими ограничениями, порядок инициализации нужно определять на этапе сборки прошивки. Утилита make умеет в топологическую сортировку ;)
Все что можно сделать в compile time - нужно делать в compile time.
redf1sh
04.06.2024 04:13+1А если нужно динамически изменять необходимые в данный момент компоненты прошивки? Не собирать же прошивки со всеми возможными комбинациями.
aabzel Автор
04.06.2024 04:13Утилита make умеет в топологическую сортировку ;)
Гениально! Спасибо за идею!
aabzel Автор
04.06.2024 04:13+1Утилита make умеет в топологическую сортировку ;)
Да. Хотя бы вот так
ADC: GPIO NVIC DMA AdcChannels @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 INIT_ORDER += SW_COMP += UnitTest SW_COMP += StartPause SW_COMP += AdcChannels .... 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)])запускаем
make.exe --always-make -i -k init
и готово
MiyuHogosha
04.06.2024 04:13Мне помнится как-то можно было вытащить имена целей из файла, записать в виде правил скриптом и проинклюдить. Копипастить не надо. Тогда и дополнительные флаги можно заменить правилом phony
rukhi7
04.06.2024 04:13+1Удалось составить консольную Cи утилиту, которая находит топологическую сортировку для графа на основе списка смежности.
интересная тема, осталось только выяснить откуда берутся списки смежности. Как вы определяете от чего эта библиотека/компонента/кусок кода зависит? в какой форме хранятся у вас зависимости в компонентах? или вы какую то отдельную базу данных зависимостей поддерживаете, тогда как к этой базе из прошивки обращаться?
aabzel Автор
04.06.2024 04:13+3осталось только выяснить откуда берутся списки смежности. Как вы определяете от чего эта библиотека/компонента/кусок кода зависит?
Автор программного компонента создает graphviz файл, где указывает от чего зависит его программный компонент.
Про это есть отдельный текст
Генерация зависимостей внутри программы
https://habr.com/ru/articles/765424/rukhi7
04.06.2024 04:13+1надо же разработка софта для микроконтроллеров доросла до компонентного подхода! У меня к сожалению нет доступа к енвайронменту с такими возможностями (правилами, правила создают возможности, как ни странно). Но я таким пользовался в мире других компонент не связаных с ембедед разработкой еще 20 лет назад.
Интересно!
wataru
04.06.2024 04:13То есть надо обойти граф в порядке увеличения количества зависимостей. В дискретной математике эту процедуру называют Топологическая Сортировка графа.
Неверная формулировка. Тут надо обойти граф так, чтобы все зависимости были от следующих вершин к предыдущим. Количество зависимостей тут не важно.
Есть специальные алгоритмы для построения этого обхода. Однако они требуют динамического выделения памяти и рекурсию. Мне, как программисту микроконтроллеров,
Но при этом вы пишите консольную утилиту! Да, у вас привычки, но это всего-лишь привычка, а не ограничения для задачи. Можно скопировать тот же код из википедии.
А так, рекурсию всегда можно реализовать через ручной стек. При этом вы заранее знаете его максимальный размер, поэтому вам не надо будет даже никакого динамического выделения памяти. Нужен лишь один массив для стека + один массив, где для каждой вершины будет храниться, сколько ее соседей уже обработано. При доставании из стека, если у вершины не все еще обработано, кладете ее назад в стек, увеличиваете счетчик для вершины и кладете в стек очередную зависимость. Если все обработано, то выводите вершину в ответ.
Потом, есть другой подход, основанный на обходе в ширину. Сначала запустите обход в ширину со всех ваших целевых вершин. Пометьте все вершины, которые вы обойдете. Это будут вершины, которые в итоге придется проинициализировать (а вообще незадетые компоненты не обойдутся). Подсчитайте для каждой компоненты, от скольки она зависит. Так же постройте обратный граф - где записаны не зависимости, а кто зависит от каждой вершины.
Потом поместите в очередь те нужные компоненты, у которых 0 зависимостей. При доставании из очереди выводите вершину в ответ и уменьшайте счетчик зависимостей для всех вершин, которые от текущей зависят. Если там получился 0 (и вершина "нужная"), то добавляйте ту вершину в очередь.
Первый обход в ширину можно опустить, если у вас все компоненты так или иначе используются.
В обоих случаях удобно сначала преобразовать граф к числам. Составьте массив строк и каждую строку замените на ее номер в массиве.
Эти оба алгоритма работают гарантированно за O(V+E). Правда, могут быть проблемы с заменой произвольных строк на числа, если не использовать Trie. Но у вас там все идентификаторы - символы. Когда как ваш алгоритм, похоже, работает за O(V^3).
Для избавления от динамической памяти можно хранить граф в виде матрицы смежности, или в виде списков в массиве, для экономии памяти:
int beg[kMaxEdges]; // начало ребра int en[kMaxEdges]; // конец ребра int next[kMaxEdges]; // следующее ребро в списке для начала ребра int rnext[kMaxEdges]; // следующее ребро в обратном графе для конца ребра int first[kMaxNodes]; // первое ребро в списке для вершины в графе int rfirst[kMaxNodes]; // первое ребро в списке для вершины в обратном графе // инициализация int num_edges = 0; memeset(first, -1, sizeof(first)); memeset(rfirst, -1, sizeof(first)); void AddEdge(int b, int e) { beg[num_edges] = b; en[num_edges] = e; next[num_edges] = first[b]; first[b] = num_edges; rnext[num_edges] = rfirst[e] rfirst[e] = num_edges; ++num_edges; } // обойти все вершины, от которых зависит v for (int e = first[v]; e != -1; e = next[e]) { int u = en[e]; } // обойти все вершины, котрые зависят от v for (int e = rfirst[v]; e != -1; e = rnext[e]) { int u = beg[e]; }
Indemsys
04.06.2024 04:13Ничего, скоро таких статей в интернете сильно поубавится.
ChatGPT Code Copilot гораздо понятней объясняет алгоритмы и пишет код
Вот пример сортировки (DAG - Directed Acyclic Graphs)
Топологическая сортировка графа выполняется только для ацикличных направленных графов (DAG - Directed Acyclic Graphs). Этот алгоритм упорядочивает вершины так, что для каждого ребра uv, вершина u предшествует вершине v в отсортированном порядке. #include <stdio.h> #define MAX_VERTICES 100 typedef struct { int V; int E; int adj[MAX_VERTICES][MAX_VERTICES]; int indegree[MAX_VERTICES]; } Graph; void createGraph(Graph* graph, int V, int E) { graph->V = V; graph->E = E; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { graph->adj[i][j] = 0; } graph->indegree[i] = 0; } } void addEdge(Graph* graph, int src, int dest) { graph->adj[src][dest] = 1; graph->indegree[dest]++; } void topologicalSort(Graph* graph) { int V = graph->V; int queue[MAX_VERTICES]; int front = 0, rear = 0; int topOrder[MAX_VERTICES]; int index = 0; for (int i = 0; i < V; i++) { if (graph->indegree[i] == 0) { queue[rear++] = i; } } while (front < rear) { int u = queue[front++]; topOrder[index++] = u; for (int v = 0; v < V; v++) { if (graph->adj[u][v] == 1) { if (--graph->indegree[v] == 0) { queue[rear++] = v; } } } } if (index != V) { printf("Граф содержит цикл\n"); } else { printf("Топологический порядок: "); for (int i = 0; i < index; i++) { printf("%d ", topOrder[i]); } printf("\n"); } } int main() { Graph graph; int V = 6, E = 6; createGraph(&graph, V, E); addEdge(&graph, 5, 2); addEdge(&graph, 5, 0); addEdge(&graph, 4, 0); addEdge(&graph, 4, 1); addEdge(&graph, 2, 3); addEdge(&graph, 3, 1); topologicalSort(&graph); return 0; }Хотя автор не показал, что он действительно имеет дело с DAG.
И выбрал довольно сомнительный вариант применения сортировки графов.wataru
04.06.2024 04:13У этого решения 3 проблемы: он не работает со списком начальных вершин, как в статье, он обходит весь граф, а не только достижимые вершины (инициализирует вообще все, а не только нужное), тут граф храниться в виде матрицы смежности, что может быть слишком много.
Ну и, тут ничего не объяснено. А так, GPT почти воспроизвел мое предложение с методом на основе обхода в ширину. Правда, тут ребра развернуты.
Ну и главное, если гпт тут где-то что-то нагаллюционировал, то вы этого даже не заметите.
Indemsys
04.06.2024 04:13Сегодня ChatGPT лагает, поэтому выложил первый же его ответ.
И там все объяснено, просто я выложил не весь ответ. Полный ответ от ChatGPT потянет на хорошую статью.
А так там можно тюнингировать код под любые хотелки.
Человек так не сможет.wataru
04.06.2024 04:13Никогда не пологайтесь на ответ от GPT нейросеток по теме, в которой вы не эксперт. Как удобный инструмент для экономии времени в поиске или написании каких-то простых вещей - оно отлично работает. Пока вы можете полностью понять весь ответ и сразу распознать галлюцинации. Но как источник знаний - нет, из-за сильно ненулевого количество ложных и очень прадоподобных ответов (ведь сетка натренерована давать правдоподобные ответы).
Indemsys
04.06.2024 04:13Это и есть простая вещь. Только граница простых вещей у AI сдвигается вверх каждый день.
ChatGPT напишет и проверочный код если надо и исправит ошибки если надо.
А так приведенный код достаточно примитивен. Быть "экспертом" в этом алгоритме это в все равно что быть экспертом по арифмертике.Я сейчас с помощью ChatGPT уже успешно осваиваю SDK от Infineon. Еще месяц назад такое трудно было представить.
wataru
04.06.2024 04:13Это и есть простая вещь
Простая вещь = вы понимаете каждое слово и строчку в коде. В конкретном случае, вы должны знать про обход в ширину и понимать, почему он работает, чтобы понять, что GPT предложил вам его модификацию.
ChatGPT напишет и проверочный код
Иногда может допустить одну и ту же ошибку и в проверочном коде. Например, я как-то спрашивал его написать класс, чтобы он принимал числа и выдавал максимальное среди K последних пришедших. GPT уверено писал код, который искал k-ое максимальное с конца каждый раз. И тесты под этот код сделал правильные. А в комментариях копировал мой вопрос и даже название функции дал, вроде MaxOfLastK().
Быть "экспертом" в этом алгоритме это в все равно что быть экспертом по арифмертике.
Ну не совсем. Это простой алгоритм да, но доказательство, что он, например, проинициализирует все, в случае если это возможно - чуть сложнее, чем 2+2. Тут нужна математическая индукция.
Я сейчас с помощью ChatGPT уже успешно осваиваю SDK от Infineon.
Вот как раз обучение - это тот самый кейс с ускорением поиска. Если он вам выдает несуществующий метод из документации, вы это сразу заметите.
Indemsys
04.06.2024 04:13Вы свой код привели без проверочных тестов и без тестовых данных и без понятного описания.
И именно поэтому я обратился к ChatGPT. От человека не добиться такого подробного, структурированного и ясного описания.
Вы свой код зачем выложили? Наверно чтобы немного просвятить автора. (я отметаю другие эгоистичные мотивы). Ну так ChatGPT это делает лучше. Вот и все. И не важно как ChatGPT устроен и для чего он нужен по чьему-то мнению.
wataru
04.06.2024 04:13Ну так ChatGPT это делает лучше.
Вот как раз нет, часто наоборот.
Люди тоже иногда ошибаются, но чаще потому что что-то забыли или не заметили что-то, а не галлюционируют вообще не имеющие отношения к реальности утверждения (шизофреников игнорируем - их пренебрежимо мало). Потом, с людьми можно вступить в конструктивный диалог, когда как GPT будет бесконечно говорить "да, вы абсолютно правы, вот новая версия с новыми галлюцинациями".
Вы свой код привели без проверочных тестов и без тестовых данных и без понятного описания.
Код там - это лишь структура данных с исчерпывающими примерами, как ее использовать.
И толку от этих тестов, если они тоже нагаллюционированы бывают?
От человека не добиться такого подробного, структурированного и ясного описания
Это да. Но надо помнить, что он может подробно, ясно и структурированно объяснять галлюцинации. Поэтому связка GPT+человек, разбирающийся в теме - это очень продуктивный подход. Копипастить ответы GPT по интернету - в основном засорение интернета.
Если бы вы спросили у него, узнали про такой алгоритм, поняли его и сказали "Вот такой вот алгоритм на основе BFS есть. Вот код от chatgpt (я проверил)", то я бы к вам не придирался.
Кстати, возвращаясь к вашему комментарию:
Ничего, скоро таких статей в интернете сильно поубавится.
Скорее наоборот. Скоро в интернете будет экспоненциально расти мусор собранный из копипасты выхлопа от ботов без какого-либо осмысления и проверки.
И еще, а зачем копипастить ответ от GPT, если автор сам может у него все спросить?
Indemsys
04.06.2024 04:13+1Но пока вы не нашли галюцинацию в приведенном мной коде.
И кто тогда тут галюцинирует по поводу галюцинаций?wataru
04.06.2024 04:13Ниже ответил более основательно и не конкретно на этот вопрос.
А конкретно по галлюцинациям - вы отрицаете их существование? Ну вот тут вам повезло. А могло и не повезти же. Ведь могло же?
wataru
04.06.2024 04:13Давайте я вам расскажу, почему меня ваш комментарий просто бесит. Я тоже могу скормить загловок статьи и пару пожеланий ChatGPT и скопировать сюда его ответ. И вы можете. И вообще все пользователи хабра. И мы все можем так сделать вообще в любой теме на хабре и вообще на любом сайте! Поскольку ответы случайны - с 100 разных вариаций на каждую тему наберется легко. В том числе взаимнопротиворечащих. Из них, правда, с десяток или с два будут правдоподобным бредом. И это не потребует никаких знаний или множества действий. Ctrl-C, Ctrl-V + одна фараза от себя. Мозг не задет, как говорится.
Но если так сделают все, то интернет кончится. Это только повышает энтропию и засоряет инфосферу. Редко несет пользу. И очень часто - вред. В политических темах уже давно бот на боте ботом погоняет. Через chatGPT вы на тот же уровень опускаете инженерные темы.
На всяких stackoverflow и qna.habr.com это уже проблема. Каждый второй любитель GPT просто копипастит ответы оттуда. Очень часто невпопад и неправльные. За это уже давно сразу банят. И хорошо, если они еще ленятся и просто копипастят. А ведь некоторые гады еще и просят ответ краткий выдать или редактируют его, и тогда даже по стилю не сразу видно, что это GPT.
В конкретном случае он выдал вам правильный алгоритм. Но вам надо помнить, что это вам тут повезло. Это вероятностый инструмент.
Вам нравится им пользоваться - на здоровье. Используете его как источник знаний для себя, а потом уже свои знания, проверенные и переработанные постите где хотите, как свои знания, мысли и идеи. Будьте готовы их аргументировать, о них спорить и отвечать за них. А тут вы просто что-то скопировали, мол "мопед не мой, я просто разместил объяву". Иначе, ну зачем нам тут посол от GPT. Кому надо, может и сам спросить у него. Опять же, представьте, что так делают все. Думаете, будут комментарии на хабре все еще так же интересны?
Indemsys
04.06.2024 04:13Согласен с вашим возмущением. Неприятно когда постят непроверенный код.
Но знаете, интернет давно уже выработал рефлекс не верить никакому коду если нет сторонних источников доверия. Нет веры и авторам, даже если они клянуться, что всё проверили.
С ChatGPT у меня очень счастливая история. А получаю от него просто класные безошибочные скрипты на Python, да и на C простые функции он отлично выдает.
Генерил функции с API OpenSSL, тоже отлично. Да, там встречались опечатки в именах функций API, но такие очевидные, что грех жаловаться.А вот так просто получить нужный код от ChatGPT не выйдет. Нужно точно и тонко задать вопрос или даже цепочку вопросов. В этом и проявляется компетенция.
Автор не спросил и не спросит у ChatGPT. Потому что тот ему не ответит нужным образом. А знаете почему? Потому что сама тема галюциногенная (какой-то раздутый граф инициализации периферии, рисуемый вручную). Такой проблемы, как в статье просто не существует в малых встраиваемых системах, если там сознательно её не культивировать.
slonopotamus
04.06.2024 04:13Чота я не смог понять суть задачи. Есть у вас компонент А и компонент B, который зависит от A. Ну и делаем:
A* a = init_a(); B* b = init_b(a);Всё, мы красавчики. Куда тут прилеплять ваш алгоритм? Вы конечно можете попытаться сказать что функция
init_bне принимает на вход никаких аргументов. Но простите, откуда она тогда возьмёт зависимостьa?aabzel Автор
04.06.2024 04:13Тут под зависимостью подразумевается то, что компонент B вызывает API из компонента A.
slonopotamus
04.06.2024 04:13+1Какой апи? Статические функции без состояния? Так в них ничего инитить не надо. А если там структурки с данными, то возвращаемся к вопросу - откуда зависящий компонент собрался взять ссылку на экземпляр зависимого компонента?
Вы пишете что описываете текстовыми файликами что от чего зависит. Зачем? Зависимость и так уже выражена кодом. Нельзя дернуть init_b раньше чем init_a, потому что иначе вам нечего передавать в init_b.
aabzel Автор
04.06.2024 04:13API это функции. Вот например драйвер кнопок для своей работы вызывает функции из GPIO и Time.
Значит у программного компонента Button две зависимости GPIO и Time
aabzel Автор
04.06.2024 04:13откуда зависящий компонент собрался взять ссылку на экземпляр зависимого компонента?
У зависящего компонента в конфиге есть натуральное число на номер экземпяра зависимого компонента.
У каждого программного компонента есть функция, которая по номеру экземпляра выдает структуру.DmaChannelHandle_t* DmaChannelGetNode(uint8_t num); const DmaChannelConfig_t* DmaChannelGetConfig(uint8_t num); DmaChannelInfo_t * DmaChannelGetInfo(uint8_t num, DmaChannel_t channel); DmaChannelHandle_t * DmaChannelGetNodeItem(uint8_t dma_num, DmaChannel_t channel);slonopotamus
04.06.2024 04:13DmaChannelHandle_t* DmaChannelGetNode(uint8_t num);
Как это работает? Откуда возникает
DmaChannelHandle_t*? Там внутри статическая мутабельная переменная условного видаDmaChannelHandle_t handles[NUM_HANDLES]? Если да - ну штош, вы сами себе создали проблему, потому что к этой переменной действительно можно обратиться до её инициализации чем-то содержательным. Не делайте так :) Делайте dependency injection, когда не компонент лазит по всей памяти, доставая свои зависимости, а они явным образом передаются в него.aabzel Автор
04.06.2024 04:13У меня и используется Dependency injection. Код PWM3 по натуральному числу 20 получает структуру TIMER20.
aabzel Автор
04.06.2024 04:13Там внутри статическая мутабельная переменная условного вида
DmaChannelHandle_t handles[NUM_HANDLES]На каждый канал DMA (их там 12) есть своя структура
DmaChannelHandle_t
aabzel Автор
04.06.2024 04:13Если да - ну штош, вы сами себе создали проблему, потому что к этой переменной действительно можно обратиться до её инициализации чем-то содержательным. Не делайте так :)
Никакой проблемы нет. Структура хранит флаг is_init. Getter выдаст NULL если false=is_init
Refridgerator
Алгоритм выглядит интересно, обязательно проверю его на досуге. В своё время делал его через раскрашивание рёбер, и не для просто инициализации, а в целом для потока вычислений. Вопрос: на зацикленных вариантах проверяли? типа a->b->a.
randomsimplenumber
Вот кстати да. Что должна делать прошивка с циклической зависимостью? Зависать? Падать?
wataru
Если есть цикл, то тупо невозможно проинициализировать это все в порядке, не нарушая зависимости. Это будет продетектировано любым из стандартных алгоритмов, когда как алгоритм автора, похоже, повиснет.
randomsimplenumber
Один из ночных кошмаров - программа для микроконтроллера компилируется но залипает где то на инициализации.
wataru
Ну нет, тут же консольная утилита, которая выдаст порядок вызова функций, которые надо будет вставить в исходник.
aabzel Автор
Или прошивка зависает где-то между 80й и 90й минутой up-time
aabzel Автор
Тогда всегда можно выполнить топологическую сортировку утилитой make
wataru
make тоже заметит циклическую зависимость и даже цикл выведет, насколько я помню. Но вообще, там рекурсия, если вам важно.
А так да, make отлично эту задачу решает. Правда, это весьма остроумно додуматься его тут применять.
randomsimplenumber
Кстати о рекурсии, с которой автор боролся. Я почему-то решил, что нужно экономить байты, потому что алгоритм должен работать на микроконтроллере. А если на компе.. Блин, у вас никогда не будет столько периферии, чтобы вышел такой огромный граф, чтобы ему не хватило стека на компе. Даже если постараться и реализовать комбо из рекурсии и О(N^3).
wataru
Рекурсия O(N) всего будет.
randomsimplenumber
никто не запрещает вместе с рекурсией использовать вложенные циклы ;)
Ембедщики не любят рекурсию, потому что мало памяти, и переполнение стека получить проще простого.
MiyuHogosha
phony целями?
wataru
Вот автор разобрался и сделал так: https://habr.com/ru/articles/818917/comments/#comment_26897515
Наверняка, есть более красивые и/или кошерные варианты.
MiyuHogosha
Мне вдруг захотелось изучить язык PL. В нем это решается двумя строчками
wataru
Задачи на графы? Или топологическая сортировка?
aabzel Автор
Да прошивка-то про графы ничего знать не знает.
Ей только готовый массив указателей на функции скармливают.
Это PC для прошивки хороший init подбирает (кодогенерация) и пытается распетлять ситуацию.