Поиск в глубину на С

Следующим идет поиск в глубину или обход дерева в глубину или же DFS, реализация на Си. Реализация будет не рекурсивная, с использованием очереди из предыдущего поста.

Немного информации из вики:

Поиск в глубину

Поиск в глубину (англ.Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.

 

Определим структуру данных для нашего дерева:

typedef struct tree_node {
    /* указатель на левую вершину */
    struct tree_node * left;
    /* указатель на правую вершину */
    struct tree_node * rigth;
    /* указатель на хранимые в вершине данные */
    void *data;
    /* необходимая при обходе пометка */
    int mark;
} tree_node_t;

Так же нужно определить указатель на функцию которая быдет вызывается для обработки данных находящихся в обрабатываемой вершине.

typedef void (*visit_node_f)(tree_node_t *node, void *visit_data);

Т.е. нам нужно определить функцию которая будет проводить некоторые манипуляции с данными хранимыми в вершине tree_node_t *node, а void * data будет расшариваться между всеми вызовами, например в нем можно сохранить счетчик или еще что-нибудь что может пригодиться при обработке данных.

Теперь собственно сам алгоритм, в функцию передается корень дерева, указатель на функцию обработчик данных и общие для всех обработчиков данные:

void dfs(tree_node_t * root, visit_node_f node_function, void *visit_data)
{
    list_t *st = create_list();

    list_push(st, root);

    while(st->size != 0) {
        tree_node_t * node = st->head->data;
        /* посетить вершину, если это не сделали раньше */
        if(node->mark != 1){
            (*node_function)(node, visit_data);
            node->mark = 1;
        }

        if(node->left != NULL && !node->left->mark) {
            list_push(st, node->left);
            continue;
        }

        if(node->rigth != NULL && !node->rigth->mark) {
            list_push(st, node->rigth);
            continue;
        }
        /* Извлекаем обработанную вершину из стека */
        tree_node_t * rel_node = (tree_node_t *)list_pop(st);
    }

    free(st);
}

Односвязный список на Си

При подготовке к сертификации я решил заготовить «бомбы» какие-то стандартные  не сложные вещи, которые скорей всего пригодятся мне во время решения теста и на которые не хотелось бы тратить время. И первое с чего я бы хотел начать это односвязный список. Односвязный список будет очень полезен для реализации обхода дерева как в глубину, так и в ширину, точней он необходима для итеративной реализации, потому что на нем можно реализовать как стек, так и очередь.

Немного информации из википедии:

single_linked_list

Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1]Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера[2], а порядок обхода списка всегда явно задаётся его внутренними связями.

 

 

/* Определяем элемент списка */
typedef struct list_node {
    struct list_node *next;
    void *data;
} list_node_t;

/* Определяем сам список */
typedef struct list {
    /* 
     * Размер списка хранить не обязательно, 
     * он нужен для упрощения работы 
     */
    int size;
    /* начало списка */
    list_node_t *head;
    /* конец списка */
    list_node_t *tail;
} list_t;

/* Инициализация массива */
list_t * create_list(void)
{
    list_t *lt = malloc(sizeof(list_t));

    lt->size = 0;
    lt->head = NULL;
    lt->tail = lt->head;

    return lt;
}

/* Добавляем элемент в начало списка */
void list_push(list_t *lt, void * data)
{
    list_node_t * node = malloc(sizeof(list_node_t));
    node->data = data;
    node->next = lt->head;

    lt->head = node;
    lt->size += 1;
}

/* Извлекаем элемент из начала списка */
void * list_pop(list_t *lt)
{
    if(lt->size == 0){
        /* Список пуст */
        return NULL;
    }

    list_node_t *node = lt->head;
    void * ret_val = node->data;

    lt->size -= 1;
    lt->head = node->next;

    free(node);

    if(lt->size == 0){
        /* Это был последний элемент */
        lt->head = NULL;
        lt->tail = NULL;
    }

    return ret_val;
}

/* Добавляем элемент в конец списка */
void list_push_back(list_t *lt, void * data)
{
    list_node_t * node = malloc(sizeof(list_node_t));
    node->data = data;
    if(lt->tail != NULL)
        lt->tail->next = node;
    else {
        lt->head = node;
    }

    lt->tail = node;
    lt->size += 1;
}

Теперь можно использовать этот список и как очередь и как стек.

Пример использования как стек:

list_t *st = create_list();
int data = 0, *ptr;

/* Добавляем в начало списка */
list_push(st, &data);
/* Извлекаем из начала списка*/
ptr = (int *)list_pop(st);

А вот пример использования как очереди:

list_t *queue = create_list();
int data = 0, *ptr;

/* Добавляем в конец списка */
list_push_back(queue, &data);
/* Извлекаем из начала списка*/
ptr = (int *)list_pop(queue);

Немного о линковки статических библиотек

Базовые понятия, кратко

Совершенно неожиданное открытие сделал недавно. Оказывается порядок появления файлов на входе линковщика важен, если мы говорим о линковки статических библиотек. Для того что бы понять почему так происходит, нужно понимать принцип работы линковщика. Объектные файлы как предоставляют(экспортируют) символы(имена функций, переменных), так и ожидают(импортируют) их. Рассмотрим небольшой пример:

int imported(int);

static int internal(int x) {
return x * 2;
}

int exported(int x) {
return imported(x) * internal(x);
}

Теперь скомпилируем этот файл:

gcc -c test.c
nm test.o

000000000000000e T exported
                 U imported
0000000000000000 t internal

Название функций говорит само за себя. Теперь, библиотека — это всего лишь набор объектных файлов хранящихся вместе(собранных в один архив утилитой ar), сейчас я рассматриваю только статически скомпилированные библиотеки.

 

Процесс линковки

Вызовите ли вы его или же линкер будет вызван компилятором, так или иначе на вход линковщику будут поданы объектные файлы и/или библиотеки. Порядок появления файлов на входе линковщика и есть порядок линковки. Вот что делает линковщик:

  • Линковщик поддерживает таблицу символов. Эта таблица помимо всего содержит два списка
    • Список символов экспортируемых всеми объектными файлами и библиотеками, обработанными на данный момент.
    • Список не определенных символов, которые обработанные на данный момент объектные файлы и библиотеки запросили. Имеются ввиду те символы что еще не были найдены.
  • Когда линковщик обрабатывает новый объектный файл, он смотрит на:
    • Экспортируемые символы — они добавляются в список экспортируемых символов. Если какой-то из них находился в списке не определенных символов, то он оттуда убирается. Если какой-то из символов уже находится в списке экспортируемых символов, то мы получаем ошибку: множественное объявление(multiple definition).
    • Импортируемые символы — эти добавляются в список не определенных символов, если их не удалось найти в списке экспортируемых.
  • Когда линковщик обрабатывает новую библиотеку, то все становиться несколько интересней. Линковщик проходится по всем объектным файлам внутри библиотеки и для каждой он смотрит в первую очередь экспортируемые символы:
    • Если какой-то из экспортируемых символов находится в списке не определенных, тогда объектный файл добавляется к линкуемым. В ином случае следующий шаг пропускается.
    • Если объектный файл был добавлен, то он обрабатывается как обычный — экспортируемые и импортируемые символы добавляются в соотвествующие таблицы.
    • Наконец,  если какой-либо  из объектных файлов библиотеки был добавлен, то библиотека сканируется заново — возможно что какие-то из импортируемых символов могут быть найдены в других объектных файлах в этой библиотеки.

Когда линковщик заканчивает, он смотрит таблицы символов. Если таблица не определенных символов не пуста линковщик выкинет исключение «undefined reference«.

Стоит заметить что после того как библиотека будет просканирована, линковщик к ней уже возвращаться не будет. Даже если она экспортирует символы которые понадобятся библиотекам которые будут просканированы  позже нее. Единственный случай при котором линковщик пересканирует библиотеку был описан выше — когда какой-либо из объектных файлов этой библиотеки был слинкован, тогда библиотека сканируется заново. Поведение линковщика можно изменить флагами линковки(см. —start-group —end-group в руководстве ld).

Так же стоит заметить что линковщик добавляет не все объектные файлы библиотеки, а только те что содержат необходимые экспортируемые символы(те что есть в списке неопределенных символов). Это очень важная особенность линковки статических библиотек, которая часто применяется, допустим библиотека C(libc) сформирована так что объектный файл содержит только одну функцию. Например, если ваша программа использует только strlen, то только этот объектный файл будет слинкован с вашим приложением/библиотекой(а так же те объектные файлы что потребуются strlen), что позволит уменьшить конечный размер приложения/библиотеки.

Давайте разберем на простом примере, есть файл simplefunc.c:

int func(int i) {
    return i + 21;
}

и файл simplemain.c:

int func(int);

int main(int argc, const char* argv[])
{
    return func(argc);
}

Скомпилируем эти 2 файла в приложение:

$ gcc -c simplefunc.c
$ gcc -c simplemain.c
$ gcc simplefunc.o simplemain.o
$ ./a.out ; echo $?

Все работает как и задумывалось.

Но что если simplefunc мы преобразуем в статическую библиотеку?! И попробуем собрать:

$ ar r libsimplefunc.a simplefunc.o
$ ranlib libsimplefunc.a
$ gcc  simplemain.o -L. -lsimplefunc
$ ./a.out ; echo $?
22

Все работает, но что будет если изменить порядок линковки:

$ gcc  -L. -lsimplefunc  simplemain.o
simplemain.o: In function 'main':
simplemain.c:(.text+0x15): undefined reference to 'func'
collect2: ld returned 1 exit status

Вот все и сломалось. Понимание алгоритмов линковки помогает понять почему этот пример не линкуется. На момент обработки libsimplefunc.a линковщик еще не «видел» simplemain.o и потому func еще не в списке неопределенных символов. Когда линковщик обрабатывает библиотеку, он видит экспортируемый символ func, но он не «нужен» и потому объектный файл не линкуется. Когда же он доходит до simplemain.o, то он находит импортируемый символ func, который добавляется в список неопределенных символов, правда на вход линковщика больше не поступают файлы и потому func остается не определенным.

А в предыдущем случае, где библиотека и объектный файл поступали в другом порядке этого не произошло. Отсюда следует что если объектный файл или библиотека AAA нуждается в символе из библиотеки BBB, то AAA должна появится перед BBB на входе линковщика. Все это относиться к линковки статических библиотек.
Статья является частичным переводом статьи Eli Bendersky.

TI Launchpad G2 с лицензией на Code Composer Studio

Сегодня увидел в блоге посвященном MSP430 микроконтроллерам интересное предложение. TI предлагает набор MSP430 Launchpad G2 за 9.99$ в комплекте с лицензией на Code Composer Studio. Сама по себе студия обычно очень дорогая, порядка 500$ за лицензию. А тут такое щедрое предложение, отладочную плату за такие деньги не всегда возьмешь. Кстати у меня уже давно лежит платка MSG Launchpad, которую я заказывал несколько лет назад за 5$ и даже делал на ней несколько домашних проектов.

code_composer_studio_free

Установка MongoDB в Ubuntu 16.04

MongoDBЯ уже писал про mongodb данных в одной из предыдущей своих статей, но для установки базы на Ubuntu 16.04 требуется слегка изменить процесс. В основном это связано с переходом Ubuntu на systemd.

Итак, первоначально добавляем публичный ключ в систему управления пакетами:

sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv EA312927

 

После этого добавляем репозиторий в список репозиториев:

echo "deb http://repo.mongodb.org/apt/ubuntu xenial/mongodb-org/3.2 multiverse" | sudo tee /etc/apt/sources.list.d/mongodb-org-3.2.list

 

Обновляем базу пакетов:

sudo apt-get update

Теперь можно установить сам пакет:

sudo apt-get install -y mongodb-org

Стоит сразу заметить что добавлять этот файл в ручную стоит только если вы устанавливаете версию младше 3.2.7, в версия старше этот баг уже пофикшен.

Собственно, а теперь главное изменение. Создадим сервисный фал systemd /etc/systemd/system/mongodb.service с таким содержанием:

[Unit]
Description=High-performance, schema-free document-oriented database
After=network.target

[Service]
User=mongodb
ExecStart=/usr/bin/mongod --quiet --config /etc/mongod.conf

[Install]
WantedBy=multi-user.target

Теперь можно спокойно запускать mongo, а если заменить <start> на <enable> то база будет стартовать автоматически при каждом запуске системы:

sudo systemctl start mongodb

Ошибка вида:

Failed to start mongodb.service: Unit mongodb.service is masked.

решается выполнением команды:

sudo systemctl unmask mongodb

Sublime Text 3 для Сишника

Sublime_Text_Logo

 

 

Мне нравиться sublime text и я использую его для программирования, решил я освоить его по лучше, заодно написать небольшую шпаргалку по тем плагинам что уже использую.

 

 

Начнем с самого главного:

Package Control

Менеджер пакетов, позволяет устанавливать плагины из единого источника и управлять ими. Невероятно удобный инструмент работы с плагинами. Для установки, следуйте инструкциям на сайте. Все последующие пакеты будут устанавливаться через него. Командой <Ctrl + Shift + P> — Package Control: Install Package

 

C Improved

Более приятная подсветка синтаксиса.

 

CMake

Подсветка синтаксиса СMake. Для новых проектов предпочитаю использовать cmake. Тем более что проекты CMake можно открывать как CLion, так и в Qt Creator.

 

Cscope

Позволяет искать определения, объявления функций, переменных и т.п. Для работы требует что бы была создана база cscope.out которую можно создать этими двумя командами:

find . -name "*" -print > cscope.files

cscope -b -q

Если имеешь дело с ядром или чем-нибудь еще не использующим libc(u-boot например) то стоит добавить ключ -k

 

Shell Exec

Этот плагин позволяет запускать shell команды прямо из Sublime Text при помощи хоткея:

  • Linux: ctrl + shift + c
  • Mac: shift + super + c
  • Windows: ctrl + shift + c

В пользовательские настройки добавляю вот это:

«shell_exec_executable_option»: «—login»,
«shell_exec_output»: «panel»

 

Git

Тут  все понятно, в работе и дома использую гит. Позволяет работать с гитом прямо из редактора.

Пишем собственный init на С

Потребовалось мне как-то написать свой init, для ускорения загрузки. Особенность, в том что он должен быть статически слинкован и не должен завершаться, кроме этого во время работы инита могут быть не доступны stdin и stdout.

#include <stdio.h>
#include <sys/mount.h>

int main()
{
    fprintf(stderr, "Hello World Init!\n");

    /* mount /proc for example */
    if(mount("none", "/proc", "proc", 0, NULL) < 0) {
        perror("proc");
    }
    
    while(1);
{

Собираем файл: gcc -static -O0 init.c -o init

 

Стоит заметить что у меня инит запускался и динамически слинкованный, но в процессе его эксплуатации, он начинал вести себя не стабильно.

На stackoverflow нашел как можно решить проблему с недоступными stdin и stdout

int onefd = open("/dev/console", O_RDONLY, 0);
dup2(onefd, 0); // stdin
int twofd = open("/dev/console", O_RDWR, 0);
dup2(twofd, 1); // stdout
dup2(twofd, 2); // stderr

if (onefd > 2) close(onefd);
if (twofd > 2) close(twofd);

libuv — библиотека для асинхронного I/O

libuvПроцессе изучения Javascript и Node я как системный программист не мог не поинтересоваться его внутренним устройством. Одной из интересных находок стала библиотека libuv.

libuv

libuv — кроссплатформенная библиотека асинхронного ввода-вывода(I/O), разрабатываемая для Node.JS. Библиотека «навязывает» асинхронный, событийно-ориентированный стиль программирования(Node же). Эта библиотека как и libevent2 использует наиболее эффективный из доступных в системе способов асинхронной работы с сокетами(epoll, kqueue, event ports,  IOCP), но в отличии от libevent, которая использует буферизированный ввод-вывод для операций с файловой системой, libuv для работы с файловой системой применяет синхронные вызовы в пуле потоков. Помимо этого библиотека предоставляет кроссплатформенные примитивы для работы с потоками(threads).

 

Обработчики и запросы(Handles and requests).

Вместе с циклом обработки событий(event-loop) libuv предоставляет 2 абстракции для работы: обработчики и запросы.

Обработчики представляют собой долгоживущие объекты способные выполнять определенные операции пока активны. Например: обработчик соединения TCP-сервера, который вызывается каждый раз когда появляется новое соединение.

Запросы представляют собой краткосрочные(как правило) операции. Эти операции могут быть выполнены над обработчиком, например, запрос на запись используется для того что бы записать данные в обработчике.

Continue reading

Javascript promise — промисификация кода

promiseИспользование promise для улучшения читаемости кода и избавления от callback-hell’a.

Я разрабатывал своего бота в процессе изучения Javascript и не сильно запаривался о виде кода и о хороших практиках и наваратил там такой лапши из callback’ов, что сам уже не мог им дать ладу и когда сайт донор немного поменял верстку бот перестал нормлаьно работать, при попытке его починить все стало только хуже, ибо я больше и больше запутывался в своем же коде.

Собственно это и стало триггером моего решения переписать бота, да так что б код был читаемым и не было этой лапши из callback’ов. Мне посоветовали посмотреть JS promise’ы.

Promise — являются альтернативой использования callback-функций при работе с асинхронным кодом. Promise – это специальный объект, который содержит своё состояние. Вначале pending(«ожидание»), затем – одно из: fulfilled («выполнено успешно») или rejected («выполнено с ошибкой»).

Continue reading

Организация ротации логов в PM2 — pm2-logrotate

организация ротации логовСначала я пробовал использовать библиотеку для логгирования работы бота, потом думал писать свое приложении для организации ротации логов, но потом наткнулся на этот модуль расширения для PM2, который логгирует всю информация, которую ваше приложение пишет в консоль и организует ротацию логов по дням, по размеру лог файла. Так же очень важной особенностью этого расширения является то, что он удаляет старые логи, ведь однажды после 3 месяцев работы на сервере кончилось место на диске, как я потом выяснил, оно было забито логами.

 

Устанавливается он так:

pm2 install pm2-logrotate

Модуль имеет несколько настраиваемых параметров:

  • max_size (по умолчанию 10MB): Когда размер файла превысит max_size, модуль его разделит. Можно использовать: 10G, 10M, 10K
  • interval (по умолчанию 1):
  • interval_unit (по умолчанию ‘DD’): interval и interval_unit работают вместе, это значит что если у вас interval_unit=’DD’, а interval=3, то значит что логи будут разбиваться каждые 3 дня.
  • retain (по умолчанию all): Это число логов находящихся в ротации, это значит, что если retain = 7, то будет хранится до 7 логов и текущий.

Самым важным для нас является параметр retain, именно он не позволит забить ваш диск логами. Параметр устанавливается так:

pm2 set pm2-logrotate:retain 10

 

Дополнительную информацию можно почерпнуть на странице проекта в github: pm2-logrotate