Паттерны для создания рекурсивных функций.

Читая An Introduction to Programming in Emacs Lisp, наткнулся на описание простых рекурсивных паттернов и решил сделать их описание.

Паттерн every.

В данном паттерне действие выполняется над каждым элементом списка. Алгоритм паттерна следующий:

• 
  Если список пустой, то возвращаем nil.
  
• 
  В противном случае работаем над началом списка(операция car). После чего делаем рекурсивный вызов с использованием cdr или комбинируем результат функции с помощью cons.
  

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

(defun square-each (numbers-list)
"Square each of a NUMBERS LIST, recursively."
    (if (not numbers-list)
        nil
        (cons (* (car numbers-list) (car numbers-list)) 
            (square-each (cdr numbers-list)))))

(square-each ’(1 2 3))
⇒ (1 4 9)

В данном примере каждый элемент списка возводится в квадрат.
Еще один пример:

(defun print-elements-recursively (list)
"Print each element of LIST on a line of its own. Uses recursion."
    (when list
        (print (car list))
        (print-elements-recursively (cdr list))))

В приведенном примере функция рекурсивно выводит каждый элемент.

Паттерн accumulate.

В этом паттерне действие производится над каждым элементом списка и результат
этого действия аккамулируется с результатом последующих элементов. Алгоритм имеет вид:

• 
  Если список пуст, то возвращается нуль или любая другая константа.
  
• 
  Иначе берется первый элемент списка и объеденяется с последующими элементами
  рекурсивного вызова с помощью функции + или подобными ей комбинирующими функциями.
  

Пример:

(defun add-elements (numbers-list)
"Add the elements of NUMBERS-LIST together."
      (if (not numbers-list)
         0
         (+ (car numbers-list) (add-elements (cdr numbers-list)))))

(add-elements ’(1 2 3 4))
⇒ 10

Таким образом функция выводит сумму всех элементов списка.

Паттерн keep.

В данном паттерне каждый элемент списка проходит проверку. Если он удовлетворяет условию, то результат действия сохраняется.
Алгоримт имеет вид:

• Если список пуст, то возвращаем nil.
• Если начальный элемент списка проходит проверку, то комбинируем его с помощью cons и делаем рекурсивный вызов с хвостом списка(cdr).
• В противном случае если первый элемент не удовлетворяет условию, то действие над данным элементом пропускается и с помощью рекурсивного вызова переходим на следующий элемент.

Пример:

(defun keep-three-letter-words (word-list)
"Keep three letter words in WORD-LIST."
     (cond ((not word-list) nil)
           ((eq 3 (length (symbol-name (car word-list))))
               (cons (car word-list) (keep-three-letter-words (cdr word-list))))
           (t (keep-three-letter-words (cdr word-list)))))

(keep-three-letter-words ’(one two three four five six))
⇒ (one two six)

В выше приведенном примере выделяется список символов, длина которого равна 3.

Создание документации и доступ к ней - emacs-docs.

Возникла необходимость в работе с документацией по исходному коду. Конечно есть много готовых инструментов, но хотелось бы что-нибудь интегрированное к emacs. Поэтому решил сделать модуль для него на основе org-mode. В начале упор будет сделан на язык С. Исходный код проекта находится на github.

Перевел cl-event-callback на bordeaux-threads.

Заменил sb-thread на bordeaux-threads. Алгоритмы работы модуля остались без изменений. Теперь необходимо добавить потоко-безопасность.

git. Создание (удаление) удаленной ветки.

Постоянно забываю команды git для создания новой удаленной ветки. Решил отметить это тут:

git push origin origin:refs/heads/new_branch
git checkout --track -b new_branch origin/new_branch

Чтобы удалить удаленную ветку:

git push origin :heads/new_branch

Вывести список удаленных веток можно командой:

git branch -r

Использование netlink для определения изменения маршрутов ipv6 в Linux.

   Протокол ipv6 позволяет конфигурировать сеть без учатия пользователя с помощью icmpv6, если узел работает в качестве клиента(forwarding установлен в 0).
Поэтому возникает задача: как отследить эти изменения. Как оказывается, это достаточно просто, если использовать протокол netlink. Описание данного протокола можно найти здесь (eng) и здесь(рус.).
   Для вывода информации об измененных маршрутах я создал функцию show_route. Вот ее исходный код:

/*
buffer - хранит полученные сообщения от netlink
size - размер полученных данных
*/
void show_route(char *buffer, int size)
{
   /*
   nlmp - указатель на структуру заголовка netlink
   routemsg - полезная нагрузка
   tb[RTA_MAX+1] - атрибуты маршрута
   */
   struct nlmsghdr *nlmp;
   struct rtmsg       *routemsg;
   struct rtattr * tb[RTA_MAX+1];

   /*
   Данные в буфере имеют следующий вид:
   |nlmsghdr|data|nlmsghdr|data|....|nlmsghdr|data|
   |-------------------size-----------------------|
   */

   for(nlmp = (struct nlmsghdr *)buffer; size > sizeof(*nlmp);){  

      int len;
      int req_len;
      /*Проверяем целостность netlink сообщения*/
      if (!NLMSG_OK(nlmp, size)) {
         perror("NLMSG not OK\n");
         return;
      }
      /*Это размер сообщения netlink*/
      int len = nlmp->nlmsg_len;
      /*Получаем размер полезной нагрузки*/
      int req_len = len - sizeof(*nlmp);
      /*Проверяем тип сообщения*/
      /*Если он не относится к маршрутам, то переходим на следующее сообщение*/
      switch(nlmp->nlmsg_type){
      case RTM_DELROUTE:
         printf("A route was deleted\n");
         break;
      case RTM_NEWROUTE:
         printf("A route was added\n");
         break;
      default:
         size -= NLMSG_ALIGN(len);
         nlmp = (struct nlmsghdr*)((char*)nlmp + NLMSG_ALIGN(len));
         continue;
     }
     /*Получаем указатель на полезную нагрузку и , после чего, выделяем атрибуты маршрута*/
     routemsg = (struct rtmsg *)NLMSG_DATA(nlmp);
     /*Данная функция описана ниже.*/
     parseRtattr(tb, RTA_MAX, RTM_RTA(routemsg), len);

     /*Код ниже выводит атрибуты маршрута*/
     if(tb[RTA_IIF]){
        int iface;
        iface = *(int*)RTA_DATA(tb[RTA_IIF]);
        printf("An input iface is %d\n", iface);

     }
     if(tb[RTA_OIF]){
        int iface;
        iface = *(int*)RTA_DATA(tb[RTA_OIF]);
        printf("An output iface is %d\n", iface);
     }
     if(tb[RTA_DST]){
        char routeAddr[128];
        inet_ntop(AF_INET6, RTA_DATA(tb[RTA_DST]), routeAddr, sizeof(routeAddr));
        printf("Destination route is %s\n", routeAddr);
     }else if (routemsg->rtm_dst_len) {
        printf( "0/%d \n", routemsg->rtm_dst_len);
     } else {
        printf("Destination route is default\n");
     }

     if(tb[RTA_SRC]){
        char routeAddr[128];
        inet_ntop(AF_INET6, RTA_DATA(tb[RTA_SRC]), routeAddr, sizeof(routeAddr));
        printf("Source route is %s\n", routeAddr);
     }
     if(tb[RTA_GATEWAY]){
        char routeAddr[128];
        inet_ntop(AF_INET6, RTA_DATA(tb[RTA_GATEWAY]), routeAddr, sizeof(routeAddr));
        printf("Gateway is %s\n", routeAddr);
     }
    if(tb[RTA_PRIORITY]){
        int metric ;
        metric = *(int*)RTA_DATA(tb[RTA_PRIORITY]);
        printf("Mertic is %d\n", metric);
     }
     /*Переходим на следующее сообщение*/
     size -= NLMSG_ALIGN(len);
     nlmp = (struct nlmsghdr*)((char*)nlmp + NLMSG_ALIGN(len));
  }//for(nlmp = (struct nlmsghdr *)buffer; size > sizeof(*nlmp);){
}

Полезная нагрузка в данном случае состоит из заголовка и атрибутов
маршрута. Поэтому общий вид пакета имеет следующий вид:

Таким образом, функция для выделения атрибутов:

void parseRtattr(struct rtattr *tb[], int max, struct rtattr *rta, int len)
{
       memset(tb, 0, sizeof(struct rtattr *) * (max + 1));

       while(RTA_OK(rta, len)){
             if(rta->rta_type <= max){
                   tb[rta->rta_type] = rta;
             }

             rta = RTA_NEXT(rta, len);
      }
}

Теперь можно написать main функцию:

int main(int argc, char *argv[])
{
    int nd = 0;
    struct sockaddr_nl *local;
    char buffer[16384];

    nd = socket(AF_NETLINK, SOCK_RAW, NETLINK_ROUTE);

    local = malloc(sizeof(struct sockaddr_nl ));
    memset(local, 0, sizeof(struct sockaddr_nl));

    local->nl_family = AF_NETLINK;
    /*Принимаем изменения, связанные с маршрутами ipv6*/
    local->nl_groups = RTMGRP_IPV6_ROUTE;
    local->nl_pid = getpid();

    if(bind(nd, (struct sockaddr *)local , sizeof(struct sockaddr_nl)) < 0){
         printf("Error bind\n");
         return 1;
    }

    while(1){
       /*
        Эта структура непосредственно передается через сокет.
        Она содержит в себе  указатель на блок полезных данных,количество
        данных блоков, а так же ряд дополнительных флагов и полей
      */
       struct msghdr msg;
       /*
        Эта структура служит хранилищем полезных данных,
        передаваемых через сокеты netlink. Полю iov_base присваивается указатель
        на байтовый массив. Именно в этот байтовый массив будут записаны
        данные сообщения.                   
       */
       struct iovec iov;
       int size = 0;

       iov.iov_base = buffer;
       iov.iov_len = 16000;

       msg.msg_name = &local;
       msg.msg_namelen = sizeof(*local);
       msg.msg_iov = &iov;
       msg.msg_iovlen = 1;

       size = recvmsg(nd, &msg, MSG_DONTWAIT);
       if(size  < 0){
             if(errno == EINTR || errno == EAGAIN){
                   usleep(250000);
                   continue;
            }
      }

      show_route(buffer, size);
   }
}