Senior Pimiento

fish, rat or bird

Задача:

Вычислить число перестановок всех букв английского алфавита, которые не содержат в себе подстрок fish, rat или bird.

Решение:

1.  **A** — число перестановок, содержащих **fish**. **B** — число перестановок, содержащих **rat**. **C** — число перестановок, содержащих **bird**.
2.  Всего число перестановок букв английского алфавита **26!**.
3.  Из этого числа надо вычесть число вхождений слова **fish**. Слово **fish** состоит из 4 букв, значит остаётся ещё 22 буквы алфавита. Итого, **23!**.
4.  Вычтем число вхождений слова **rat**: **24!**.
5.  Вычтем число вхождений слова **bird**: **23!**.
6.  Формула включений-исключений для нашего примера имеет вид

  |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| - |A ∩ B ∩ C|.

Но так как **fish** и **bird** содержат общий символ **i**, то

  |A ∩ C| = ⌀,

а так как **bird** и **rat** содержат общий символ **r**, то

  |B ∩ C| = ⌀,

и значит

  |A ∩ B ∩ C| = \empty.

Тогда остаётся только

  |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B|

Это число строк в которых содержится или слово **fish** , или слово **rat**, или слово **bird**, или они вместе (вместе могут быть только **fish** и **rat**). Так как нам надо вычислить количество перестановок, где эти строки не встречаются, то вычтем всё из общего числа перестановок и получим

  26! - |A| + |B| + |C| - |A ∩ B| = 26! - 23! - 24! - 23! + 21!.

Линковщики и Загрузчики

Ссылки

Линковка

Линковка это процесс компоновки различных кусков кода и данных вместе, в результате чего получается один исполняемый файл. Линковка может быть выполнена во время компиляции, во время загрузки (загрузчиком) и также во время исполнения (исполняемой программой). Раньше (конец 40-х) линковка выполнялась вручную, сейчас мы имеем программы линковщики (linkers), которые дают возможность динамической линковки разделяемых библиотек (shared libraries).

Основы

Пусть у нас есть два файла с кодом a.c и b.c. Чтобы скомпилировать эти два файла при помощи GCC, мы вызываем следующий код

gcc a.c b.c

Это вызывает следующую последовательность:

  1. Запустить препроцессор на файле a.c и сохранить результат в промежуточный файл a.i
cpp other-command-line options a.c /tmp/a.i
  1. Запустить компилятор на a.i и сгенерировать ассемблерный код в a.s
cc1 other-command-line options /tmp/a.i -o /tmp/a.s
  1. Запустить ассемблер на a.s и сгенерировать объектный файл a.o
as other-command-line options /tmp/a.s -o /tmp/a.o
  1. Повторить шаги 1-4 для файла b.c, получить объектный файл b.o
  2. Работа линковщика состоит в том, чтобы получить на вход сгенерированные объектные файлы a.o и b.o и сгенерировать из них финальный исполняемый файл a.out
ld other-command-line-options /tmp/a.o /tmp/b.o -o a.out

После этого мы можем запустить наш бинарный файл ./a.out. Оболочка командной строки вызовет функцию загрузчика, которая скопирует код и данные из исполняемого файла a.out в память, затем передаст управление в начало программы. Функция загрузчик называется execve, она загружает код и данные исполняемых объектных файлов в память, затем запускает их выполнение, прыгая на первую инструкцию.

Линковщики и Загрузчики

Линковщики (linkers) и загрузчики (loaders) выполняют концептуально разные, но в целом похожие задачи:

  • Загрузка программ. Копирование образа программы с жёсткого диска в RAM. В некоторых случаях загрузка программы (loading) также может включать выделение дисковой памяти или отображение виртульного адресного пространства на дисковое пространство.
  • Релокация (relocation). Компиляторы и ассемблеры генерируют объектный код для каждого входного модуля программы с началом адресации в нуле. Релокация — это процесс изменения адреса загрузки различных частей программы во время объединения всех секций одного типа в одну секцию. Секции кода и данных таким образом будут указывать на корректные адреса в рантайме.
  • Symbol Resolution. Программы имеют внутри себя множество подпрограмм; указание одной подпрограммы на другую подпрограмму происходит через символьные таблицы. Работа линковщика — подменять указания на символ подпрограммы на указание адреса расположения подпрограммы, изменяя объектный код.

В итоге, получается что загрузчик выполняет загрузку программ; линковщик выполняет symbol resolution; оба выполняют релокацию.

Объектные файлы

  • Перемещаемый объектный файл (relocatable object file) — содержит бинарный код и данные в форме, которая может быть скомпонована с другими перемещаемыми объектными файлами во время компиляции. В итоге получаем исполняемый объектный файл, скомпонованный из перемещаемых объектный файлов.
  • Исполняемый объектный файл (executable object file) — содержат бинарный код и данные в форме, которая может быть напрямую загружена в память и выполнена.
  • Разделяемый объектный файл (shared object file) — специальный тип перемещаемого объектного файла, который может быть загружен в память и слинкован динамически либо во время загрузки в память, либо во время выполнения.

Компиляторы и ассемблеры генерируют перемещаемые объектные файлы (а так же разделяемые объектные файлы). Линковщики компонуют эти объектные файлы вместе и генерируют исполняемые объектные файлы.

ELF

Объектные файлы разнятся в разных ОС. Первые UNIX системы использовали формат a.out. Ранние System V использовали формат COFF (common object file format). Windows NT использует разновидность формата COFF, называемую PE (portable executable); IBM использует собственный формат IBM 360. Современные UNIX системы, такие как Linux и Solaris используют формат UNIX ELF (executable and linking format).

Заголовки Elf

  • .text: the machine code of the compiled program.
  • .rodata: read-only data, such as the format strings in printf statements.
  • .data: initialized global variables
  • .bss: uninitialized global variables. BSS (начало блока данных — block storage start), эта секция обычно пустует в объектных файлах; этакая заглушка.
  • .symtab: таблица символов, содержащая информацию о функциях и глобальных переменных, определённых и адресованных в коде программы. Эта таблица не содержит записей о локальных переменных, эта информация содержится на стеке.
  • .rel.text: список мест в секции .text, которые необходимо модифицировать, когда линковщик будет компоновать этот объект с другими объектными файлами.
  • .rel.data: информация о релокации глобальных переменных, которые объявлены, но не определены в текущем модуле программы.
  • .debug: таблица отладочных символов с записями о локальных и глобальных переменных. Эта секция будет присутствовать только если компилятору был передан флаг компиляции с таблицей отладочных символов (-g для gcc).
  • .line: отображение номеров строк в исходном C-файле и машинными кодами инструкций. Эта информация необходима для отладки программ.
  • .strtab: таблица строк для таблицы символов .symtab и секции .debug

Символы и адресация символов

Каждый перемещаемый объектный файл содержит таблицу символов связанные символы. В контексте линковщика представлены следующие виды символов:

  • Глобальные символы объявленые на уровне модуля — могут быть адресованы из других модулей.Все не-статические и глобальные переменные попадают в эту категорию.
  • Глобальные символы адресованные в коде, но объевленные где-то вне. Все функции и переменные с модификатором extern попадают в эту категорию.
  • Локальные символы объявленные и адресованные исключительно во входном модуле. Все статические функции и статические переменные попадают в эту категорию.

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

Линковка статических библиотек

Статические библиотеки это коллекция конкатенированных объектных файлов схожего типа. Эти библиотеки хранятся на диске в архиве. Архив также содержит мета-информацию для ускорения поиска в нём. Каждый архив с ELF начинается с магической последовательности !\n.Статические библиотеки передаются на вход линковщику, который копирует только объектные модули, упоминаемые в программе. В процессе разрешения адресации символов при работе со статическими библиотеками линковщик сканирует перемещаемые объектные файлы и архивы справа-налево в порядке указания аргументов вызова. В процессе сканирования линковщик создаёт набор O-файлов (перемащаемых объектных файлов, которые будут включены в исполняемый файл); набор U-файлов (неразрешённых пока символов); набор D-файлов (символы, объявленные в предыдущих модулях). Изначально все три набора пустые.

  • На каждый следующий входной аргумент линковщик определяет передаётся ли объектный файл или архив. Если это перемещаемый объектный файл, то линковщик добавляет его в набор O, обновляет наборы U и D и переходит к следующему входному аргументу
  • Если входной аргумент архив, линковщик сканирует список членов модулей, входящих в архив, чтобы отыскать любые неразрешённые символы, находящиеся в наборе U. Если такие символы находятся, то они добавляются в список O и обновляется список U. Список D дополняется символами, найденными в архиве.
  • Когда все входные аргументы пройдены, но если набор U не пуст, то линковщик сообщает об ошибке линковки и завершает свою работу. Иначе, если набор U пуст, линковщик компонует и релоцирует объектные файлы из набора O и генерирует финальный исполняемый файл.

Релокация

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

  1. Релокация секций и определения символов. Линковщик объединяет все секции одного типа в новую секцию. К примеру, линковщик объединяет все секции .data всех входных перемещаемых объектов в новую секцию .data результирующего исполняемого файла. Похожий процесс происходит для секции .code. Затем линковщик указывает текущий адрес памяти для этой сгенерированной секции. Так для каждой секции и символа. После завершения этого шага каждая инструкция и глобальная переменная в прогармме будет иметь уникальный адрес в момент загрузки.
  2. Релокация адресации символов внутри секций. На этом шаге линковщик изменяет адресации на символы в коде и секциях данных так, чтобы они указывали на корректный уникальный адрес в момент загрузки.

Ассемблер при релокации создаёт секции .relo.text и .relo.data, в которых содержится информация как разрешить адресацию (адрес для обращения к символу). ELF содержит в секциях релокации следующие данные:

  • Смещение (offset). Для перемещаемых файлов значение смещения это смещение в байтах от начала секции до получившегося после релокации адреса.
  • Символ (symbol). Индекс символа в символьной таблице.
  • Тип (type). Тип релокации.

Динамическая линковка: разделяемые библиотеки

Статические библиотеки, описанные выше, имеют существенный недостаток. Например, возьмём стандартные функции printf и scanf. Они используются почти что в каждой программе. Пусть на системе запущено 50-100 процессов, каждый процесс содержит свою копию исполняемого кода printf и scanf — это существенный объём затраченной памяти. Разделяемые библиотеки в свою очередь направлены на исправление этого недостатка статических библиотек. Разделяемые библиотеки это объектные модули, которые могут быть загружены в память в момент исполнения программы и после слинкованы с программой. Разделяемые библиотеки (shared libraries) называют так же разделяемые объекты (shared objects). На большинстве систем UNIX они именуются с суффиксом .so; на системах HP-UX — с суфиксом .sl; на системах Microsoft они называются DLL.Чтобы собрать разделяемый объектный файл, компилятор надо вызывать со специальным флагом

gcc -shared -fPIC -o libfoo.so a.o b.o

Эта команда сообщает компилятору, что надо сгенерировать разделяемую библиотеку libfoo.so, собранную из объектный файлов a.o и b.o. Флаг -fPIC сообщает компилятору, что надо сгенерировать адресо-независимый код (position independent code — PIC).Теперь представим что объектный модуль bar.o зависит от a.o и b.o. В этом случае мы компилируем его так:

gcc bar.o ./libfoo.so

Эта команда создаёт исполняемый файл a.out, который будет линковаться с libfoo.so в момент загрузки. Здесь a.out не содержит в себе объектный модулей a.o и b.o, которые были бы включены в него, если бы мы использовали статическую линковку. Исполняемый файл просто содержит некоторую информацию о релокации и таблицу символов, которые позволяют адресоваться к коду и данным в libfoo.so и эта адресация будет разрешена в процессе исполнения (runtime). Таким образом, a.out это не совсем исполняемый файл, который имеет зависимость от libfoo.so. Исполняемый файл содержит секцию .interp, где содержится имя динамического линковщика (который сам является разделяемым объектом в системах Linux — ld-linux.so). Таким образом, когда исполняемый файл загружается в память, загрузчик передаёт управление динамическому линковщику. Динамический линковщик содержит некоторый код, который отображает пространство адресов динамических библиотек на пространство адресов испольняемой программы.

  1. Происходит релокация кода и данных из libfoo.so в область памяти
  2. Происходит релокация адресации в a.out на символы объявленные в libfoo.so.

В конце работы динамический линковщик передаёт контроль исполняемой программе. С этого момента местоположение разделяемого объекта зафиксировано в памяти.

Загрузка разделяемой библиотеки из приложения

Разделяемая библиотека может быть загружена из приложения в любой момент выполнения. Приложение может обратиться к динамическому линковщику с просьбой загрузить и прилинковать динамическую библиотеку. Linux, Solaris и другие системы поддерживают различниые функции, которые могут быть использованы для динамической загрузки разделяемых объектов. В Linux это системные вызовы dlopen, dlsym, dlclose, используемые для загрузки разделяемого объекта, поиска символа в разделяемом объекте и для закрытия разделяемого объекта.

Утилиты для работы с объектными файлами

  • ar: создаёт статические библиотеки.
  • objdump: может быть использована для показа всей информации о бинарном объектном файле.
  • strings: показывает все строковые данные в бинарном файле, содержащие печатные символы.
  • nm: перечислить символы, определённые в символьной таблице объектного файла.
  • ldd: перечислить динамические библиотеки, от которых зависит объектный файл.
  • strip: удалить информацию из таблицы символов.

C: varargs

Списки аргументов переменной длины

В стандартном заголовочном файле имеется набор макроопределений, дающих способ перебора списка аргументов. Реализация этого заголовочного файла системно-зависима, однако интерфейс всегда единообразный. Для объявления переменной, ссылающейся по очереди на каждый аргумент, имеется тип va_list. Макрос va_start инициализирует переменную типа va_list так, чтобы переменная указывала на первый безымянный аргумент. Функция должна иметь как минимум один аргумент с именем; последний именнованный аргумент используется макросом va_start для инициализации своей работы. Каждый вызов va_arg возвращает один аргумент и передвигает указатель типа va_list на следующий. Чтобы определить, какого типа аргумент нужно возвращать и на сколько передвигать указатель, va_arg использует заданное ему имя типа. Макрос va_end выполняет необходимые завершающие операции. Его необходимо вызвать до выхода из функции.

#include <stdarg.h>

void minprintf(char *fmt, ...) {
    va_list ap;
    char *p, *sval;
    int ival;
    double dval;

    va_start(ap, fmt);          /* установить ap на 1-ый аргумент без имени  */
    for (p = fmt; *p; p++) {
        if (*p != '%') {
            putchar(*p);
            continue;
        }
        switch (*++p) {
        case 'd':
            ival = va_arg(ap, int);
            printf("%d", ival);
            break;
        case 'f':
            dval = va_arg(ap, double);
            printf("%f", dval);
            break;
        case 's':
            for (sval = va_arg(ap, char*); *sval; putchar(*sval++));
            break;
        default:
            putchar(*sval);
            break;
        }
    }
    va_end(ap);
}

int main(void) {
    minprintf("can print %s: %d %f", "some text with numbers", 42, 3.1415);
    return 0;
}
can print some text with numbers: 42 3.141500

UNIX: ссылки

Отличия hardlink от symlink

  • hardlink: жёсткая ссылка, по сути этот копия того же файла, на который она ссылается.
  • symlink: мягкая ссылка, содержит путь до файла на который она ссылается.
  • inode: объект файловой системы, содержащий информацию о владельце файла, группе, правах доступа, размере, типе, времени модификации (mtime) и доступа к файлу (atime), времени модификации индексного дескриптора (ctime) и счётчик жёстких ссылок на файл. Каждый inode имеет номер, присваиваемый ему файловой системой в момент её создания.
ls -lih *.org
1700798 -rw-r--r-- 1 pimiento pimiento  19K февр.  8 14:30 c_structures.org
1657341 -rw-r--r-- 1 pimiento pimiento 7,8K янв.  30 12:16 decorators.org
1556139 -rw-r--r-- 1 pimiento pimiento 4,0K янв.  16 22:37 export_to_gfm.org
1656099 -rw-r--r-- 1 pimiento pimiento 2,2K янв.  16 22:33 pdftk_and_djvu.org
 683609 -rw-r--r-- 1 pimiento pimiento 7,6K февр.  4 21:03 processes.org
1687699 -rw-r--r-- 1 pimiento pimiento 3,4K янв.  16 22:38 publish_to_blogger.org
 588563 -rw-r--r-- 1 pimiento pimiento 2,9K февр.  4 13:15 python_coctions.org
1664005 -rw-r--r-- 1 pimiento pimiento  14K янв.  30 14:43 python_gc.org
1664043 -rw-r--r-- 1 pimiento pimiento 5,6K янв.  30 19:12 python_graphs.org
1616883 -rw-r--r-- 1 pimiento pimiento   29 февр.  6 13:56 python_logging.org
 588256 -rw-r--r-- 1 pimiento pimiento 5,1K февр.  4 12:52 python_os.org
1700689 -rw-r--r-- 1 pimiento pimiento 5,2K февр.  8 15:19 unix_hardlink_symlink.org
1616560 -rw-r--r-- 1 pimiento pimiento 5,8K февр.  6 12:41 ип_валютный_контроль.org

Первая колонка отображает номер inode. Далее указаны права доступа, счётчик hardlink-ов на этот файл и т.д.

Создадим, например, жёсткую ссылку на один из файлов:

ln unix_hardlink_symlink.org unix_hardlink_symlink.hardlink.org
ls -lih |grep 1700689
1700689 -rw-r--r-- 2 pimiento pimiento 5,2K февр.  8 15:19 unix_hardlink_symlink.hardlink.org
1700689 -rw-r--r-- 2 pimiento pimiento 5,2K февр.  8 15:19 unix_hardlink_symlink.org

Таким образом счётчик ссылок показывает нам, что один и тот же файл хранится под двумя разными именами.

Мягкая ссылка создаётся с помощью той же команды ln, но с ключом -s:

ln -s unix_hardlink_symlink.org unix_hardlink_symlink.symlink.org
ls -lih |grep unix_hardlink_symlink
1700689 -rw-r--r-- 2 pimiento pimiento 5,2K февр.  8 15:19 unix_hardlink_symlink.hardlink.org
1700689 -rw-r--r-- 2 pimiento pimiento 5,2K февр.  8 15:19 unix_hardlink_symlink.org
1688411 lrwxrwxrwx 1 pimiento pimiento   25 февр.  8 15:19 unix_hardlink_symlink.symlink.org -> unix_hardlink_symlink.org

Мы создали новый объект файловой системы, который указывает на уже существующий файл. В правах доступа появилось указание что новый объект файловой системы имеет тип lsymbolic link. Необходимо отметить, что inode-номера для оригинального файла и для symlink-а различаются, так как это два независимых файла для файловой системы.

hardlink не может указывать на файл в другой ФС, так как inode может принадлежать только одной ФС, symlink — может.

При удалении hardlink-а файл будет существовать до тех пор, пока существует хотя бы один hardlink на него, но может менять местоположение, если был удалён оригинальный фал и остался hardlink на него в другом каталоге. При удалении же оригинального файла для symlink — файл-ссылка просто станет нерабочей.

С помощью hardlink нельзя создать ссылку на каталог, но можно с помощью symlink.

C: структуры

Структура

Это совокупность нескольких переменных, часто различных типов, сгруппированных под единым именем для удобства обращения. Главное изменение, внесённое стандартом ANSI в работу со структурами, — это определение присваивания структур. Теперь структуры можно копировать, присваивать, передавать в функции и возвращать из функций.

Ключевое слово struct начинает объявление структуры, состоящее из списка объявлений элементов в фигурных скобках. После слова struct может стоять необязательный идентификатор, именуемый меткой структуры. Метка обозначает конкретный структурный тип; впоследствии её можно использовать для краткости, опуская всё, что находится в скобках при объявлении структур того же типа.

struct point {
    int x;
    int y;
};

Переменные, перечисленные в объявлении структуры, называются её членами, элементами или полями. Элемент структуры или её метка может иметь то же имя, что и обыкновенная переменная безо всякого конфликта, поскольку они всегда отличаются по контексту.

Объявление со словом struct фактически вводит новый тип данных. Поэтому допустимо такое объявление переменных:

struct { int x; int y; } x, y z;

Данный код объявляет переменные (x, y, z) определённого именованного типа и выделяет для них место в памяти. Объявление структуры, после которого нет списка переменных, не выделяет никакой памяти для объектов, а просто описывает форму структуры. Так же можно объявлять переменные, используя метку структуры:

struct point pt;

Структуру можно инициализировать, поставив после её определения список значений-констант:

struct point maxpt = { 320, 200 };

Обращение к элементам структуры выполняется следующим образом:

struct point pt = { 1, 2 };
double dist = sqrt((double)pt.x * pt.x + (double)pt.y * pt.y);
printf("distance from O(0, 0) to pt(%d, %d) is %f", pt.x, pt.y, dist);
distance from O(0, 0) to pt(1, 2) is 2.236068

Структуры можно вкладывать друг в друга:

struct point {
    int x;
    int y;
};
struct rect {
    struct point pt1;
    struct point pt2;
};

struct rect screen = {{0, 0}, {10, 10}};
printf("rectangle with diagonal points: (%d, %d), (%d, %d)",
       screen.pt1.x, screen.pt1.y,
       screen.pt2.x, screen.pt2.y);
rectangle with diagonal points: (0, 0), (10, 10)

Структуры и функции

Расширенными операциями над структурами являются копирование или присваивание структуры как целого, взятие её адреса операцией &, а так же обращение к её элементам. Копирование и присваивание включают также в себя передачу аргументов в функции и возвращение значений из функций. Структуры нельзя сравнивать между собой. Структуру можно инициализировать списком констант-инициализаторов для всех её полей.

struct point makepoint (int x, int y) {
    return (struct point){x,y};
}

int main(void) {
    struct rect screen;
    struct point middle;
    screen.pt1 = makepoint(0, 0);
    screen.pt2 = makepoint(1000, 1000);
    middle = makepoint((screen.pt1.x + screen.pt2.x) / 2,
                       (screen.pt1.y + screen.pt2.y) / 2);
    printf("middle point is (%d, %d)", middle.x, middle.y);
    return 0;
}
middle point is (500, 500)
struct point addpoint(struct point p1, struct point p2) {
    p1.x += p2.x;
    p1.y += p2.y;
    return p1;
}

Вместо того чтобы помещать результат во временную переменную, мы инкрементировали компоненты структуры p1, чтобы подчеркнуть тот факт, что параметры-структуры передаются по значениям, как и любые другие параметры.

Если в функцию необходимо передать большую структуру, это лучше сделать передав указатель на неё, а не копию всех её данных. Указатели на структуры обладают всеми свойстваи указателей на обычные переменные.

struct point origin = {1, 2}, *pp = &origin;
printf("origin is (%d, %d)\n", (*pp).x, (*pp).y);
origin is (1, 2)

Указатели на структуры используются так часто, что для удобства записи ссылок по ним введено дополнительное обозначение: p->элемент-структуры

struct point origin = {1, 2}, *pp = &origin;
printf("origin is (%d, %d)", pp->x, pp->y);
origin is (1, 2)

Массивы структур

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define MAXWORD 100
#define BUFSIZE 100

struct key {
    char *word;
    int count;
} keytab[] = {
    "auto", 0, "break", 0, "case", 0, "char", 0, "const", 0, "continue", 0, "default", 0,
    "do", 0, "double", 0, "else", 0, "enum", 0, "extern", 0, "float", 0, "for", 0,
    "goto", 0, "if", 0, "int", 0, "long", 0, "register", 0, "return", 0, "short", 0,
    "signed", 0, "sizeof", 0, "static", 0, "struct", 0, "switch", 0, "typedef", 0,
    "union", 0, "unsigned", 0, "void", 0, "volatile", 0, "while", 0
};

#define NKEYS (sizeof keytab / sizeof keytab[0])

char buf[BUFSIZE];
int bufp = 0;

int getword(char *, int);
int binsearch(char *, struct key *, int);
int getch(void);
void ungetch(int c);

int main(void) {
    int n;
    char word[MAXWORD];
    while (getword(word, MAXWORD) != EOF) {
        if (isalpha(word[0]))
            if ((n = binsearch(word, keytab, NKEYS)) >= 0)
                keytab[n].count++;
    }
    for (n = 0; n < NKEYS; n++) {
        if (keytab[n].count > 0)
            printf("%4d %s\n", keytab[n].count, keytab[n].word);
    }
    return 0;
}

int binsearch(char *word, struct key *tab, int n) {
    int cond;
    int low, high, mid;

    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low+high) / 2;
        if ((cond = strcmp(word, tab[mid].word)) < 0)
            high = mid - 1;
        else if (cond > 0)
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

int getword(char *word, int lim) {
    int c;
    char *w = word;
    while (isspace(c = getch()))
        ;
    if (c != EOF)
        *w++ = c;
    if (!(isalpha(c) || c == '_')) {
        *w = '\0';
        return c;
    }
    for (;--lim>0;w++) {
        if (!isalnum(*w = getch())) {
            ungetch(*w);
            break;
        }
    }
    *w = '\0';
    return word[0];
}

int getch(void) {
    return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c) {
    if (bufp >= BUFSIZE) printf("ungetch too many characters\n");
    else buf[bufp++] = c;
}

typedef

Имя нового типа, объявляемое в typedef, стоит не сразу после ключевого слова, а на месте имени переменной. Синтаксически ключевое слово typedef можно считать аналогом идентификатора класса памяти: extern, static и т.п. Новые типы, определяемые с помощью typedef, начинаются с прописной буквы, чтобы можно было их легко различить.

typedef struct tnode *Treeptr;

typedef struct tnode {
    char *word;
    int count;
    struct tnode *left;
    struct tnode *right;
} Trenode;

Treeptr talloc(void) {
    return (Treeptr)malloc(sizeof(Treenode));
}

Фактически, оператор typedef очень напоминает директиву #define с тем исключением, что, поскольку он анализируется компилятором, он может допускать такие текстовые подстановки, которые препроцессору не по силам. Например:

typedef int (*PFI)(char*, char*);

Здесь опеределяется тип PFI — "указатель на функцию от двух аргументов типа char*, возвращающую int". Этот тип можно использовать, например, таким образом:

PFI strcmp, numcmp;

Объединения

Это переменная, которая может содержать объекты различных типов и размеров (но не одновременно); при этом удовлетворение требований к размеру и выравниванию возлагается на компилятор. С помощью объединений можно работать с данными различных типов в пределах одного участка памяти, не привнося в программу элементы низкоуровневого, машинно-зависимого программирования.

union u_tag {
    int ival;
    float fval;
    char *sval;
} u;

Переменная u будет иметь достаточную длину, чтобы содержать данные самого длинного из трёх типов; конкретный размер зависит от системы и реализации. Переменной u можно присваивать данные любого типа, а затем использовать их в выражениях (строго по правилам работы с конкретным типом). Извлекать можно данные только того типа, который был помещён при последнем обращении к переменной. Следить и помнить, какие именно данные были помещены в объединение, — это забота программиста; если поместить значение одного типа, а извлечь его как значение другого, результат будет системно-зависимым и трудно предсказуемым.

Обращение к элементам объединения выполняется так же, как к элементам структуры:

имя-объединения.элемент
указатель-на-объединение->элемент

Пусть в переменной utype хранится информация о типе данных, находящихся в текущий момент в объединении:

if (utype == INT)
    printf("%d\n", u.ival);
else if (utype == FLOAT)
    printf("%f\n", u.fval);
else if (utype == STRING)
    printf("%s\n", u.sval);
else
    printf("bad type %d in utype\n", utype);

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

#define INT 0
#define FLOAT 1
#define STRING 2

struct {
    char *name;
    int flags;
    int utype;
    union {
        int ival;
        float fval;
        char *sval;
    } u;
} symtab[] = {
    "test", 4, STRING, "data"
};

printf("symtab[%s]: %s", symtab[0].name, symtab[0].u.sval);
symtab[test]: data

Фактически, объединение является структурой, в которой все элементы имеют нулевое смещение от её начала, сама она имеет достаточную длину, чтобы в неё поместился самый длинный элемент, и при этом выравнивание происходит правильно для всех типов данных в объединении. Над объединениями разрешено выполнять те же операции, что и над структурами: присваивать или копировать как единое целое, брать адрес и обращаться к отдельным элементам.

union {
    struct point pt;
    struct rect r;
} g;

struct point pt1 = {1, 2};
struct rect r1 = { {1, 2}, {10, 11} };
g.pt = pt1;
printf("g: %d, %d\n", g.pt.x, g.pt.y);

g.r = r1;
printf("g: (%d, %d), (%d, %d)", g.r.pt1.x, g.r.pt1.y, g.r.pt2.x, g.r.pt2.y);
g: 1, 2
g: (1, 2), (10, 11)

Битовые поля

Внутри системно-зависимой единицы памяти, которую мы будем называть "словом", можно задать битовое поле (bit-field) — совокупность идущих подряд битов. Синтаксис определения и использования полей основан на структурах.

struct {
    unsigned int is_keyword :1;
    unsigned int is_extern  :1;
    unsigned int is_static  :1;
} flags;

Данный код является заменой коду на константах:

#define KEYWORD  01
#define EXTERNAL 02
#define STATIC   04

enum { KEYWORD = 01, EXTERNAL = 02, STATIC = 04 };

В переменной flags содержится три однобитных поля. Число после двоеточия задаёт ширину поля в битах. Поля объявлены как unsigned int, чтобы гарантированно быть велечинами без знака. Практически всё, что связано с битовыми полями, является системно-зависимым. Например, только в конкретной реализации определяется, могут ли поля перекрывать границы слов. Поля не обязаны иметь имена; безымянные поля (двоеточия с размером после них) часто используются для пропуска и резервирования отдельных битов. Для принудительного выравнивания по границе следующего слова можно использовать специальное значение длины поля, равное 0. Совокупность полей — не массив, и у них нет адресов, поэтому операция & к ним неприменима.

Процесс в UNIX

Процесс

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

  • Процесс является тлько «мёртвой» статической оболочкой, хранящей учётные данные и обеспечивающей окружение динамического исполнения потока, даже если это единственный (главный) исполняемый поток приложения (процесса), как это принято в терминологии, не имеющей отношения к потоковым понятиям.
  • Любые взаимодействия, синхронизация, диспетчирезация и другие механизмы имеют смысл только применительно к потокам, даже если это потоки, локализованные в рамках различных процессов. Здесь возникает термин IPC — средство взаимодействия процессов. Для однопотоковых приложений этот терминологический нюанс не вносит ровно никакого различия, но при переходе к многопотоковым приложениям мы должны рассуждать в терминах именно взаимодействующих потоков, локализованных внутри процессов (одного или различных)
  • В системах с аппаратной трансляцией адресов памяти (MMU — Memory Management Unit) процесс создаёт для своих потоков дополнительные «границы существования» — защищённое адресное пространство. Большинство сложностей, описываемых в литературе в связи с использованием IPC, обусловлено необходимостью взаимодействующих потоков преодолевать адресные барьеры, устанавливаемые процессами для каждого из них.

Атрибуты процессов

  • PID: идентификатор процесса, присваиваемый процессу при создании, например вызовом fork(). PID позволяет системе однозначно идентифицировать каждый процесс. При создании процесса ему присваивается первый свободный идентификатор. Присвоение происходит по возрастающей до тех пор пока не кончатся доступные значения PID. Тогда следующий процесс получает минимальный свободный PID, и весь цикл повторяется снова. Процесс, загружавший ОС, является родительским для всех процессов в системе и его PID = 1, обычно называется init, запускается ядром ОС по окончании процедуры bootstrap. Процесс с PID = 0 это обычно процесс scheduler также называемый swapper. Процесс init никогда не умирает в процессе работы ОС. Это обычный пользовательский процесс (в отличие от процесса swapper, работающего в ядре), хотя и запущен с привелегиями суперпользователя.
pid_t p = getpid();
printf("current pid: %zu", p);
current pid: 12249
  • PPID: PID процесса, породившего данный процесс.
pid_t pp = getppid();
printf("current ppid: %zu", pp);
current ppid: 5087
  • TTY: терминальная линия: терминал или псевдотерминал, ассоциированный с процессом. Если процесс становится процессом-демоном, то он отсоединяется от своей терминальной линии и не имеет ассоциированной терминальной линии.
  • RID: реальный индентификатор пользователя.
uid_t u = getuid();
printf("current uid: %zu", u);
current uid: 1000
  • EUID: эффективный идентификатор пользователя. Эффективный идентификатор служит для определения прав доступа процесса к системным ресурсам. Обычно RID и EUID совпадают, но установка SUID флага для исполняемого файла процесса позволяет расширить полномочия процесса.
uid_t eu = geteuid();
printf("current effective uid: %zu", eu);
current effective uid: 1000
  • RGID: реальный идентификатор группы.
gid_t g = getgid();
printf("current gid: %zu", g);
current gid: 1000
  • EGID: эффективный идентификатор группы. EGID не совпадает с RGID в случае когда установлен флаг SGID.
gid_t eg = getegid();
printf("current effective gid: %zu", eg);
current effective gid: 1000

Часто в качестве атрибутов процесса называют и приоритет выполнения. Однако приоритет является атрибутом не процесса, а потока, но если поток единственный (главный, порождённый функцией main()), его приоритет и есть то, что понимается под «приоритетом процесса»

Python: collections модуль

Некоторые интересные классы из модуля collections

Для начала, нам необходимо импортировать модуль

import collections

Counter

Это подкласс класса dict.

метод elements

Возвращает итератор над элементами counter-а, где каждый ключ будет повторён столько раз, каково значение этого ключа.

import collections

c = collections.Counter(a=4, b=2, c=0, d=-2)
print(list(c.elements()))
['a', 'a', 'a', 'a', 'b', 'b']

метод most_common

Возвращает лист пар в порядке убывания значений.

import collections
print(collections.Counter('abracadabra').most_common(3))
[('a', 5), ('b', 2), ('r', 2)]

Сложение и вычитание

import collections

a = collections.Counter(a=4, b=2, c=0, d=-2)
b = collections.Counter(a=1, b=2, c=3, d=4)

print(a + b)
print(a - b)
print(a & b)
print(a | b)
a.subtract(b)
print(a)
Counter({'a': 5, 'b': 4, 'c': 3, 'd': 2})
Counter({'a': 3})
Counter({'b': 2, 'a': 1})
Counter({'d': 4, 'a': 4, 'c': 3, 'b': 2})
Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})

Deque

import collections

d = collections.deque([1, 2, 3, 4, 5])
d.append(6)
print(d)
d.appendleft(0)
print(d)
print(d.count(2))
d.clear()
print(d)
d.extend(['a', 'b', 'c'])
print(d)
d.extendleft(['x', 'y', 'z'])
print(d)
print(d.pop())
print(d)
print(d.popleft())
print(d)
d.remove('x')
print(d)
d.reverse()
print(d)
d.rotate(2)
print(d)
deque([1, 2, 3, 4, 5, 6])
deque([0, 1, 2, 3, 4, 5, 6])
1
deque([])
deque(['a', 'b', 'c'])
deque(['z', 'y', 'x', 'a', 'b', 'c'])
c
deque(['z', 'y', 'x', 'a', 'b'])
z
deque(['y', 'x', 'a', 'b'])
deque(['y', 'a', 'b'])
deque(['b', 'a', 'y'])
deque(['a', 'y', 'b'])

namedtuple

Immutable!

import collections

Point = collections.namedtuple('Point', ['x', 'y'])
p = Point(x=1, y=2)
print(p)
print(p.x)
Point(x=1, y=2)
1

Python: модуль os

Основные функции в модуле os

import os

print("%s\n%s\n%s\n%s" % (
    os.name,
    os.environ['SHELL'],        # os.environ will print too much text

    # os.getlogin(), # bug in Python, better use pwd.getpwuid(os.getuid()).pw_name

    os.getpid(),
    os.uname(),
))
posix
/bin/zsh
13774
posix.uname_result(sysname='Linux', nodename='tpad', release='3.19.0-28-generic', version='#30~14.04.1-Ubuntu SMP Tue Sep 1 09:32:55 UTC 2015', machine='x86_64')

Аттрибуты файлов и директорий

import os

print(os.access("/tmp", os.R_OK | os.W_OK))
print(os.access("/", os.W_OK))
print(os.access("/bin/bash", os.R_OK | os.X_OK))
True
False
True
import os
import grp
import stat

def perm(st):
    is_dir = 'd' if stat.S_ISDIR(st.st_mode) else '-'
    d = {'7': 'rwx', '6': 'rw-', '5': 'r-x', '4': 'r--',
         '3': '-wx', '2': '-w-', '1': '--x', '0': '---'}
    p = str(oct(st.st_mode)[-3:])
    return is_dir + ''.join(d.get(x, x) for x in p)

filepath = "/tmp/test.txt"
with open(filepath, "w") as f:
    s1 = os.stat(filepath)
    os.chdir("/tmp")
    print('test.txt' in os.listdir())
    os.chmod(filepath, 2486)
    os.chown(filepath, s1.st_uid, os.getgroups()[0])
    s2 = os.stat(filepath)
    print("before: %s\tafter: %s" % (perm(s1), perm(s2)))
    print("before: %s\tafter: %s" % (
        grp.getgrgid(s1.st_gid).gr_name, grp.getgrgid(s2.st_gid).gr_name
    ))

os.unlink(filepath)
True
before: -rw-r--r--      after: -rw-rw-rw-
before: pimiento        after: adm

Работа с процессами

import os

if os.name == "nt":
    command = "dir"
else:
    command = "ls -l"

print(os.system(command))
total 92
-rw-r--r-- 1 pimiento pimiento  7981 янв.  30 12:16 decorators.org
-rw-r--r-- 1 pimiento pimiento  4059 янв.  16 22:37 export_to_gfm.org
-rw-r--r-- 1 pimiento pimiento 35141 янв.  16 22:56 LICENSE
-rw-r--r-- 1 pimiento pimiento  2206 янв.  16 22:33 pdftk_and_djvu.org
-rw-r--r-- 1 pimiento pimiento  3394 янв.  16 22:38 publish_to_blogger.org
-rw-r--r-- 1 pimiento pimiento 13902 янв.  30 14:43 python_gc.org
-rw-r--r-- 1 pimiento pimiento  5643 янв.  30 19:12 python_graphs.org
-rw-r--r-- 1 pimiento pimiento  4988 февр.  4 12:50 python_os.org
-rw-r--r-- 1 pimiento pimiento   116 янв.  16 22:53 README.md
0

Запуск нового процесса

import os
import sys

program = "echo"
arguments = ["Hello and goodbye!"]
os.execvp(program, (program,) + tuple(arguments))
Hello and goodbye!
import os


def run(program, *args):
    pid = os.fork()
    if not pid:                 # child process

        os.execvp(program, (program,) + args)
    print("I'm parent")
    return os.wait()[0]

run("echo", "Hello from fork!")
print("goodbye")
Hello from fork!
I'm parent
goodbye

fork вернёт нулевой pid для нового процесса (возврат значения fork будет первым, что произойдёт в этом процессе) и не-нулевое значение для оригинального процесса. В случае с Windows надо пользоваться функцией spawn, так fork в Windows не поддерживается.

Python daemon

import os
import time

pid = os.fork()
if pid:
    os._exit(0)                 # kill original


print("daemon started")
time.sleep(1)
print("daemon terminated")
daemon started
daemon terminated

Это очень примитивный пример демона на Python, так как необходимо ещё позаботиться о перенаправлении stdout и stderr в dev-null и о закрытии stdin. Необходимо позаботиться о вызове os.setpgrp чтобы сигналы, посланные процессу не вызывали проблем для нашего демона. О демонах в UNIX я напишу когда-нибудь отдельно и подробно, на основе книги APUE.

Python: обход графов

Граф

Будет использоваться ненаправленный связный граф V=6 E=6. Существует две популярные методики представления графов: матрица смежности (эффективна с плотными графами) и список связей (эффективно с разряженными графами). Будем использовать второй способ.

graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E']}

Depth-First Search — Поиск вглубину

Алгоритм поиска вглубину: исследуем сначала все возможные вершины (из выбранного корня) доступные из текущей, прежде чем возвращаться назад. Данный алгоритм можно реализовать как рекурсивно, так и итеративно. Последовательность действий:

  1. Помечаем текущую вершину как посещённую
  2. Исследуем каждую соседнюю вершину не включённую в список уже посещённых
  • Вариант с DFS and BFS in Python (модифицированный, т.к. set не поддерживает упорядоченность элементов)
graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E']}

def dfs(graph, start):
    visited, stack = [], [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.append(vertex)
            stack.extend(set(graph[vertex]) - set(visited))
    return visited

print(dfs(graph, 'A'))
['A', 'C', 'F', 'E', 'B', 'D']
  • Вариант с DFS and BFS graph traversal (Python recipe) (модифицированный, т.к. для реализации стека нам необходимо добавлять элементы в конец списка, а не в начало)
graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E']}


def iteractive_dfs(graph, start, path=None):
    """iterative depth first search from start"""
    if path is None:
        path = []
    q = [start]
    while q:
        v = q.pop()
        if v not in path:
            path = path + [v]
            q += graph[v]
    return path

print(iteractive_dfs(graph, 'A'))
['A', 'C', 'F', 'E', 'B', 'D']

DFS Paths — поиск пути между двумя вершинами

graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E']}

def dfs_paths(graph, start, goal):
    stack = [(start, [start])]  # (vertex, path)

    while stack:
        (vertex, path) = stack.pop()
        for next in set(graph[vertex]) - set(path):
            if next == goal:
                yield path + [next]
            else:
                stack.append((next, path + [next]))

print(list(dfs_paths(graph, 'A', 'F')))

Bread-Firsth Search — Поиск вширину

Позволяет найти кратчайший путь между двумя вершинами. Довольно сложно реализовать рекурсивно, гораздо проще реализовать его с использованием очереди.

graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E']}
from queue import deque


def bfs(graph, start):
    visited, queue = [], deque([start])
    while queue:
        vertex = queue.pop()
        if vertex not in visited:
            visited.append(vertex)
            queue.extendleft(set(graph[vertex]) - set(visited))
    return visited

print(bfs(graph, 'A'))
['A', 'B', 'C', 'E', 'D', 'F']

BFS Paths

from queue import deque
graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E']}


def bfs_paths(graph, start, goal):
    queue = deque([(start, [start])])
    while queue:
        (vertex, path) = queue.pop()
        for next in set(graph[vertex]) - set(path):
            if next == goal:
                yield path + [next]
            else:
                queue.appendleft((next, path+[next]))

print(list(bfs_paths(graph, 'A', 'F')))


def shortest_path(graph, start, goal):
    try:
        return next(bfs_paths(graph, start, goal))
    except StopIteration:
        return None

print(shortest_path(graph, 'A', 'F'))
print(shortest_path(graph, 'E', 'D'))
print(shortest_path(graph, 'A', 'D'))
print(shortest_path(graph, 'F', 'D'))
[['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
['A', 'C', 'F']
['E', 'B', 'D']
['A', 'B', 'D']
['F', 'E', 'B', 'D']

Python: управление памятью и GC

Как Python управляет памятью

Детали того как Python управляет памятью зависят от реализации Python. Стандартная реализация Python на C использует подсчёт ссылок для выявления недостежимых объектов и отдельный механизм для отслеживания и управления циклическими ссылками, периодически вызывая алгоритм обнаружения циклических ссылок, который смотрит на недостижимые циклы и удаляет объект, входящие в такие циклические зависимости. Модуль gc предоставляет интерфейс для принудительного вызова функций сборки мусора, получения статистики и оптимизации параметров коллектора.

Иногда объекты остаются в трейсбэках и не могут быть деаллоцированы, как мы того ожидаем. Чтобы очистить трейсбэки:

import sys
sys.exc_clear()
sys.exc_traceback = sys.last_traceback = None

getrefcount

import sys
foobar = "Hello World"
barfoo = foobar
print(sys.getrefcount(foobar))
print(sys.getrefcount(barfoo))
del foobar
print(sys.getrefcount(barfoo))
5
5
4

Всегда отнимаем единицы от getrefcount — она автоматически добавляется при вызове функции. (В оригинале статьи sys.getrefcount(foobar) -> 3, sys.getrefcount(barfoo) -> 3). Когда удаляется ссылка, счётчик уменьшается на единицу. Когда он становится равным нулю — удаляется сам объект. Это — decref (по названию макроса в C API, делающего всю работу).

Дерево и decref

import sys


class Parent(object):

    def __init__(self):
        self.children = []

    def add(self, ch):
        self.children.append(ch)
        ch.parent = self


class Child(object):

    def __init__(self):
        self.parent = None

p = Parent()
p.add(Child())

Parent имеет ссылку на child, а тот в свою очередь — на родителя. Объекты останутся в памяти, даже если мы удалим все внешние ссылки на них. Результат — мусор!

Garbage Collector

Для решения предыдущей проблемы в Python появился GC (с 2.1+). В GC реализован cycle finder, который отыскивает циклические зависимости. Т.е. если объект ссылается на другой объект, а второй объект ссылается на первый и никто не ссылается на них снаружи, то эти объекты попадут под GC и их успешно разименуют. Пиковое потребление памяти при этом может быть довольно большим. Проблемы возникают, когда один из объектов циклической зависимости имеет метод del или написан как extension, т.е. не на Python. Для решения таких проблем появился модуль weakref — слабая ссылка, которая как бы видит другой объект, но при этом не увеличивает его счётчик.

Сборщик мусора

Сборщик мусора имеет три поколения (0, 1, 2). При создании объекта, он попадает в нулевое поколение. У каждого поколения есть счётчик и порог:

  • При добавлении объекта в поколение счётчик увеличивается.
  • При выбывании из поколения счётчик уменьшается.
  • Когда счётчик превысит пороговое значение — по всем объектам из поколения пройдётся сборщик мусора. Кого найдёт — удалит.
  • Все выжившие в поколении объекты перемещаются в следующее (0 → 1, 1 → 2, 1 → 2). Из второго поколения объекты никуда не попадают и остаются там навечно.
  • Перемещённые в следующее поколение объекты меняют соответствующий счётчик, и операция может повториться уже для следующего поколения.
  • Счётчик текущего поколения сбрасывается.

Объекты, подлежащие уничтожение, но имеющие переопределённый метод del, не могут быть собраны. Причина проста: эти объекты могут ссылаться друг на друга. Python не способен определить безопасный порядок вызова del. Если вызвать деструкторы в произвольном порядке, то можно получить ситуацию вида:

  • Деструктор объекта (a) для работы требует объект (b).
  • Последний в своём деструкторе обращается к объекту (a).
  • При вызове del у (a) деструктор (b) не сможет отработать нормально. Ссылка на (a) будет значение None.

Чтобы не заставлять программиста корректно разрешать такие ситуации было принято решение не уничтожать подобные объекты а просто перемещать их в gc.garbage.

Слабые ссылки, weakref

Обычно, объекты не будут удалены пока не будут удалены все ссылки на них:

class Foo(object):
    def __init__(self):
        self.obj = None
        print('created')
    def __del__(self):
        print('destroyed')
    def show(self):
        print(self.obj)
    def store(self, obj):
        self.obj = obj

print("> a = Foo()")
a = Foo()
print("> b = a")
b = a
print("> del a")
del a
print("> del b")
del b
> a = Foo()
created
> b = a
> del a
> del b
destroyed

Слабые ссылки, напротив, не увеличивают счётчик ссылок на объект. Существование слабой ссылки на объект никогда не воспрепятствует уничтожению объекта. Т.о., если на объект указывают только слабые ссылки, то это этот объект будет уничтожен.

import weakref

class Foo(object):
    def __init__(self):
        self.obj = None
        print('created')
    def __del__(self):
        print('destroyed')
    def show(self):
        print(self.obj)
    def store(self, obj):
        self.obj = obj

print("> a = Foo()")
a = Foo()
print("> b = weakref.ref(a)")
b = weakref.ref(a)
print("> a == b()")
print(a == b())
print("b().show()")
b().show()
print("del a")
del a
print("b() is None")
print(b() is None)
> a = Foo()
created
> b = weakref.ref(a)
> a == b()
True
b().show()
None
del a
destroyed
b() is None
True

Proxy

В качестве более простой альтернативы weakref.ref можно использовать weakref.proxy. Proxy-объект ведёт себя как сильная ссылка на объект, но выбрасывает exception когда используется послет того как оригинальный объект был удалён.

import weakref

class Foo(object):
    def __init__(self):
        self.obj = None
        print('created')
    def __del__(self):
        print('destroyed')
    def show(self):
        print(self.obj)
    def store(self, obj):
        self.obj = obj

print("> a = Foo()")
a = Foo()
print("> b = weakref.proxy(a)")
b = weakref.proxy(a)
print("> b.store('fish')")
b.store('fish')
print("> b.show()")
b.show()
print("> del a")
del a
print("> b.show() # -> will produce exception ReferenceError")
# b.show() -> will produce exception
> a = Foo()
created
> b = weakref.proxy(a)
> b.store('fish')
> b.show()
fish
> del a
destroyed
> b.show() # -> will produce exception ReferenceError

Циклические ссылки, Cyclic references

Необходимость в слабых ссылках возрастает когда объекты имеющие сильные ссылки образуют циклы.

class Foo(object):
    def __init__(self):
        self.obj = None
        print('created')
    def __del__(self):
        print('destroyed')
    def show(self):
        print(self.obj)
    def store(self, obj):
        self.obj = obj

a = Foo()
# created

b = Foo()
# created

a.store(b)
b.store(a)
del a
del b

Метод-деструктор для (a) и (b) никогда не будет вызван и объекты будут жить в памяти до момента окончания работы интерпретатора. Подобные примеры циклической зависимости могут быть в двусвязных списках, в деревьях. Решение проблемы — хранить слабые ссылки.

import weakref

class Foo(object):
    def __init__(self):
        self.obj = None
        print('created')
    def __del__(self):
        print('destroyed')
    def show(self):
        print(self.obj)
    def store(self, obj):
        self.obj = weakref.ref(obj)

a = Foo()
# created

b = Foo()
# created

c = Foo()
# created

a.store(b)
b.store(c)
c.store(a)
del a
# destroyed

del b
# destroyed

del c
# destroyed

Dead-on-arrival

Модуль weakref не может создавать слабые ссылки для всяких объектов. Например, попытка создать слабую ссылку на list, tuple, dictionary, numeric, string или None вызовет возникновение TypeError. Но иногда создание слабой ссылки падает молча

import weakref

class Foo(object):
    def __init__(self):
        self.obj = None
        print('created')
    def __del__(self):
        print('destroyed')
    def show(self):
        print(self.obj)
    def store(self, obj):
        self.obj = weakref.ref(obj)

a = Foo()
# created

b = Foo()
# created

a.store(b.show)                 # store creates a weak reference

a.show()
# <weakref at 0x7f0542a095e8; dead>

Причина такого поведения в том, что (bound method) b.show создаётся и передаётся в метод Foo.store. Этот метод сохраняет слабую ссылку на b.show и переменную-экземпляр a.obj. Когда store метод заканчивает свою работу, то больше не существует сильной ссылки на метод b.show и таким образом, он автоматически уничтожается. Такая ссылка на b.show называется dead-on-arrival.

Ссылки

Декораторы в Python

Декораторы и Паттерн Декоратор

Возможно использовать декораторы в Python чтобы реализовать паттерн декоратор, но это крайне редкое их использование. Декораторы в Python больше всего похожи на макросы.

Декораторы функций

class myDecorator(object):

    def __init__(self, f):
        print("inside my_decorator.__init__()")
        f()

    def __call__(self):
        print("inside my_decorator.__call__()")


@myDecorator
def aFunction():
    print("inside aFunction")

print("Finished decorating aFunction()")

aFunction()
inside my_decorator.__init__()
inside aFunction
Finished decorating aFunction()
inside my_decorator.__call__()

Изменение имени функции, возвращённой из декоратора

Если мы используем декоратор-функцию, то возвращённая им функция будет иметь совсем другое название, для решения это проблемы мы можем переопределить аттрибут _name__

def entry_exit(f):
    def wrapper():
        print("Entering", f.__name__)
        f()
        print("Exited", f.__name__)
    wrapper.__name__ = f.__name__
    return wrapper

@entry_exit
def original_name():
    print("inside original name")

original_name()
Entering original_name
inside original name
Exited original_name

Декораторы с аргументами

class decorator_with_arguments(object):

    def __init__(self, arg1, arg2, arg3):
        """
        If there are decorator arguments, the function
        to be decorated is not passed to the constructor!
        """
        print("Inside __init__()")
        self.arg1 = arg1
        self.arg2 = arg2
        self.arg3 = arg3

    def __call__(self, f):
        """
        If there are decorator arguments, __call__() is only called once,
        as part of the decoration process! You can only give it a single argument,
        which is the function object.
        """
        print("Inside __call__()")
        def wrapper(*args):
            print("Inside wrapper()")
            print("Decorator arguments:", self.arg1, self.arg2, self.arg3)
            f(*args)
            print("After f(*args)")
        return wrapper

@decorator_with_arguments("hello", "world", 42)
def sayHello(a1, a2, a3, a4):
    print("sayHello arguments: ", a1, a2, a3, a4)

print("After decoration")

print("Preparing to call sayHello()")
sayHello("say", "hello", "argument", "list")
print("after first sayHello() call")
sayHello("a", "different", "set of", "arguments")
print("after second sayHello() call")
Inside __init__()
Inside __call__()
After decoration
Preparing to call sayHello()
Inside wrapper()
Decorator arguments: hello world 42
sayHello arguments:  say hello argument list
After f(*args)
after first sayHello() call
Inside wrapper()
Decorator arguments: hello world 42
sayHello arguments:  a different set of arguments
After f(*args)
after second sayHello() call

Модуль decorator

Так как написание корректного декоратора требует значительного опыта и не так уж просто как кажется, то был создан модуль decorator.

  1. Определение декоратора

    Декораторы могут быть двух видов:

  • signature-preserving декораторы, т.е., вызываемые объекты, принимающие функцию на фход и возвращающие функцию на выход с сохранением сигнатуры
  • signature-changing декораторы, т.е, декораторы, которые изменяют сигнатуру входной функции или декораторы, возвращающие non-callable объект К signature-changing декораторам относятся, например, декораторы @staticmethod и @classmethod, т.к. они принимают на вход функцию и возвращают объект дескриптора, который не является ни функцией, ни вызываемым объектом.
  1. Описание проблемы

    Предположим, что мы хотим трассировать выполнение функции:

try:
    from functools import update_wrapper
except ImportError:             # using Python version < 2.5

    def decorator_trace(f):
        def newf(*args, **kw):
            print "calling %s with args %s, %s" % (f.__name__, args, kw)
            return f(*args, **kw)
        newf.__name__ = f.__name__
        newf.__dict__.update(f.__dict__)
        newf.__doc__ = f.__doc__
        newf.__module__ = f.__module__
        return newf
else:                           # using Python 2.5+

    def decorator_trace(f):
        def newf(*args, **kw):
            print "calling %s with args %s, %s" % (f.__name__, args, kw)
            return f(*args, **kw)
        return update_wrapper(newf, f)
  1. Решение проблемы

    Решение проблемы с постояным отслеживанием чтобы все аттрибуты функции под декоратором остались прежними (имя, документация) заключается в использовании фабрики генераторов, которая спрячет всю сложность создания signature-preserving декораторов. Вот как мы можем реализовать функцию decoratortrace:

# Во-первых, импортируем модуль decorator

from decorator import decorator


# Затем объявляем вспомогательную функцию с сигнатурой (f, *args, **kwargs),

# которая вызывает оригинальную функцию f с аргументами args и kwargs

# и реализует возможность трассировки

def trace(f, *args, **kwargs):
    print("calling %s with args %s, %s" % (f.__name__, args, kwargs))
    return f(*args, **kwargs)


# decorator может конвертировать вспомогательную функцию в signature-preserving объект-декоратор

# т.е., это вызываемый объект, принимающий на вход функцию и возвращающий обёрнутую

# в декоратор функцию с такой же точно сигнатурой, как и у оригинальной функции.

@decorator(trace)
def f1(x):
    pass

f1(0)
    calling f1 with args (0,), {}

Основы Java

Hello World

public class HelloWorld {
  public static void main(String args[]) {
    System.out.println("Hello World!");
  }
}
Hello World!

jar

Create archive

jar cfe name.jar EntryPointClass A.class B.class C.class

List jar content

jar tf hw.jar
META-INF/
META-INF/MANIFEST.MF
HelloWorld.class

Exctract jar archive

jar xf name.jar

Run jar archive with entry point

java -jar hw.jar
Hello World!

Run jar archive without entry point

java -cp hw.jar HelloWorld
Hello World!

Primitive Types

Type Definition
boolean true or false
char 16-bit, Unicode character
byte 8-bit, signed, two\u2019s complement integer
short 16-bit, signed, two\u2019s complement integer
int 32-bit, signed, two\u2019s complement integer
long 64-bit, signed, two\u2019s complement integer
float 32-bit, IEEE 754, floating-point value
double 64-bit, IEEE 754

floating-points precision

If you want to ensure that your application produces exactly the same results on
different platforms, you can use the special keyword strictfp as a class modifier
on the class containing the floating-point manipulation.

default initialization

numeric types default to the appropriate flavor of zero,
characters are set to the null character (\0),
and Boolean variables have the value false.
Local variables, which are declared inside a method and live only for the duration of a method call,
on the other hand, must be explicitly initialized before they can be used.

Switch

takes an integer (or a numeric argument that can be automatically "promoted" to an integer type), a String type argument, or an "enum" type and selects among a number of alternative, constant case branches.

break & contiune labels

The break and continue statements look like those in the C language, but Java's forms have the additional ability to a label as an argument and jump out multiple levels to the scope of the labeled point in the code.

/*
 * Copyright (c) 1995, 2008, Oracle and/or its affiliates. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *   - Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *
 *   - Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *
 *   - Neither the name of Oracle or the names of its
 *     contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

class BreakWithLabelDemo {
    public static void main(String[] args) {

        int[][] arrayOfInts = {
            { 32, 87, 3, 589 },
            { 12, 1076, 2000, 8 },
            { 622, 127, 77, 955 }
        };
        int searchfor = 12;

        int i;
        int j = 0;
        boolean foundIt = false;

    search:
        for (i = 0; i < arrayOfInts.length; i++) {
            for (j = 0; j < arrayOfInts[i].length;
                 j++) {
                if (arrayOfInts[i][j] == searchfor) {
                    foundIt = true;
                    break search;
                }
            }
        }

        if (foundIt) {
            System.out.println("Found " + searchfor + " at " + i + ", " + j);
        } else {
            System.out.println(searchfor + " not in the array");
        }
    }
}

null

The expression null can be assigned to any reference type. It means "no reference". A null reference can't be used to reference anything and attempting to do so generates a NullPointerException at runtime.

catch

In Java 7, there is an alternative to using multiple catch clauses, and that is to handle multiple discrete exception types in a single catch clause using the &vert; or syntax:

try {
    // read from network…

    // write to file…

} catch (ZipException | SSLException e) {
    logException( e );
}

Using this &vert; or syntax, we receive both types of exception in the same catch clause. So, what is the actual type of the e variable that we are passing to our log method? (What can we do with it?) In this case, it will be neither ZipException nor SSLException but IOException, which is the two exceptions' nearest common ancestor (the closest parent class type to which they are both assignable). In many cases, the nearest common type among the two or more argument exception types may simply be Exception, the parent of all exception types.

printStackTrace

try {
    // complex, deeply nested stack

} catch (Exception e) {
    // dump information about exactly where the exception occured

    e.printStackTrace(System.err);
}

own exceptions

class ParseException extends Exception {
    ParseException() {
        super();
    }
    ParseException( String desc ) {
        super( desc );
    }
}

exceptions chaining

try {
} catch ( IOException cause ) {
    Exception e = new IOException("What we have here is a failure to communicate…");
    e.initCause( cause );
    throw e;
}

Assertions

The optional expression may evaluate to either a primitive or object type. Either way, its sole purpose is to be turned into a string and shown to the user if the assertion fails; most often you'll use a string message explicitly.

assert false;
assert (array.length > min);
assert a > 0 : a                   // shows value of a to the user

assert foo != null : "foo is null" // shows message "foo is null" to user
  • To enable assertions, use flag -ea or -enableassertions
java -ea MyApplication
  • To turn on assertions for a particular class, append the class name
java -ea:examples.MyClass MyApplication
  • To turn on assertions just for particular packages, append the package name with trailing ellipses (…)
java -ea:examples...MyApplication
  • To disable assertions in general, for a particular class or for a particular package, use flag -da or -disableassertions. You can combine all this to achieve arbitrary groupings
java -ea:examples... -da:examples.text -ea:examples.text.MonkeyTypewriters MyApplication

Arrays

Java supports the C-style curly braces construct for creating an array and initialize its elements

int [] primes = {2, 3, 5, 7, 7+4};

We can use curly braces syntax also to create anonymous arrays.

Good OOP design practices

  1. Hide as much of your implementation as possible. Define accessor methods to set and return values.
  2. Use composition instead of inheritance. Do you really need to inherit the whole public interface of an object (to be a "kind" of that object) or whether you can just delegate certain jobs to the object and use it by composition.
  3. Minimize relationships between objects and try to organize related objects in packages. The more loosely coupled your objects are, the easier it will be to reuse them later.

varargs

void printObjects (Object ... list) {
    for (Object o : list)
        System.out.println( o );
}

Inside the printObjects method, the variable list is actually an Object [] type.

public class VarargsTest {
  static int zeroArray (int[] numbers) {
    return numbers[0];
  }

  static int zeroVarargs(int ... numbers) {
    return numbers[0];
  }

  public static void main(String args[]) {
    System.out.println(zeroArray(new int[]{1, 2, 3, 4}));
    System.out.println(zeroVarargs(1, 2, 3, 4));
  }
}
1
1

constructor and this method

You can invoke a second constructor (delegate to it) only as the first statement of your constructor. For example, the following code is illegal and causes a compile-time error:

class Car {
    Car(String m) {
        int doors = someMethod();
        this(m, doors);         // Error: constructor call must be first statement

    }
}

The simple model name constructor can't do any additional setup before calling the more explicit constructor. It can't even refer to an instance member for a constant value:

class Car {
    ...
    final int default_doors = 4;
    ...
    Car(String m) {
        this(m, default_doors); // Error: referencing uninitialized variable

    }
    ...
}

The instance variable defaultDoors is not initialized until a later point in the chain of constructor calls setting up the object, so the compiler doesn't let us access it yet. Fortunately, we can solve this particular problem by using a static variable instead of an instance variable:

class Car {
    ...
    static final int DEFAULT_DOORS = 4;
    ...
    Car(String m) {
        this(m, DEFAULT_DOORS); // OKAY

    }
}

The static members of a class are initialized when the class is first loaded into the virtual machine, so it's safe to access them in a constructor.

Initializer blocks

It's executed once, at the time the object is constructed, or, in the case of a code block marked static, at the time the class is loaded

class MyClass {
    Properties myProps = new Properties();
    // set up myProps

        {
            myProps.put("foo", "bar");
            myProps.put("boo", "gee");
        }
    int a = 5;
    ...
}

It allows the static members of a class to have complex initialization just like objects do with constructors:

class ColorWheel {
    static Hashtable colors = new Hashtable();

    // set up colors

    static {
        colors.put("Red", Color.red );
        colors.put("Green", Color.green );
        colors.put("Blue", Color.blue );
        ...
            }
    ...
}

The first time the class ColorWheel is referenced and loaded, the static components of ColorWheel are evaluated in the order they appear in the source.

String examples

public class StringConcat {
  public static void main(String args[]) {
    System.out.println("A" + 12);
    System.out.println('A' + "12");
    System.out.println('A' + '1' + "2");
    System.out.println("A" + ('\t' + '\u0003'));
  }
}
A12
A12
1142
A12
public class StringReverse {
  public static boolean isPalindrome(String text) {
    String s = new String(text.toLowerCase().replaceAll("[^a-zа-я0-9]", ""));
    return (new StringBuilder(s).reverse().toString()).equals(s);
  }

  public static void main(String args[]) {
    System.out.println(isPalindrome("рсфср"));
    System.out.println(isPalindrome("ссср"));
    System.out.println(isPalindrome("Madam I'm Adam"));
    System.out.println(isPalindrome("А роза упала на лапу Азора"));
  }
}
true
false
true
true

Экспорт из Org-Mode в Github Flavored Markdown

Чтобы при экспорте поддерживались различные фичи Github Flavored маркдауна,надо установить ox-gfm и экспортировать при помощи org-gfm-export-as-markdown.

Пример кода на Racket

(define (add x y)
  (+ x y))

(add 3 4)
7

Пример кода на OCaml

let add x y = x + y;;
add 3 4;;
7

Пример кода на Java

public class HelloWorld {
  public static void main(String args[]) {
    String greeting = "Hello World!";
    System.out.println(greeting);
  }
}
Hello World!

Пример кода на Scala

object HelloWorld {
  def main(args: Array[String]) {
    println("Hello, world!")
  }
}
Hello, world!

Пример кода на Python

def greeting(message):
    print(message)

greeting("Hello world!")
Hello world!

Пример кода на C (надо исправить заглавную C на маленькую c при экспорте!)

int main(void) {
    char *greeting = "Hello World!";
    printf("%s\n", greeting);
    return 0;
}
Hello World!

Исходный код этой страницы в org-mode

#+OPTIONS: toc:nil

* Учусь экспортировать org-mode в Markdown
  Чтобы при экспорте поддерживались различные фичи Github Flavored маркдауна, надо установить [[https://github.com/larstvei/ox-gfm][ox-gfm]] и экспортировать при помощи /org-gfm-export-as-markdown/.

  Пример кода на *Racket*
  #+BEGIN_SRC scheme :exports both
    (define (add x y)
      (+ x y))

    (add 3 4)
  #+END_SRC

  #+RESULTS:
  : 7

  Пример кода на *OCaml*
  #+BEGIN_SRC ocaml :exports both
    let add x y = x + y;;
    add 3 4;;
  #+END_SRC

  #+RESULTS:
  : 7

  Пример кода на *Java*
  #+BEGIN_SRC java :classname HelloWorld :results output :exports both
    public class HelloWorld {
      public static void main(String args[]) {
        String greeting = "Hello World!";
        System.out.println(greeting);
      }
    }
  #+END_SRC

  #+RESULTS:
  : Hello World!

  Пример кода на *Scala*
  #+BEGIN_SRC scala :results output :exports both
    object HelloWorld {
      def main(args: Array[String]) {
        println("Hello, world!")
      }
    }
  #+END_SRC

  #+RESULTS:
  : Hello, world!

  Пример кода на *Python*
  #+BEGIN_SRC python :results output :exports both
    def greeting(message):
        print(message)

    greeting("Hello world!")
  #+END_SRC

  #+RESULTS:
  : Hello world!

  Пример кода на C
  #+BEGIN_SRC C :results output :includes <stdio.h> :exports both
    int main(void) {
        char *greeting = "Hello World!";
        printf("%s\n", greeting);
        return 0;
    }
  #+END_SRC

  #+RESULTS:
  : Hello World!

  #+BEGIN_SRC org :exports code
    # here is org-mode source of that example!
  #+END_SRC

Экспорт из org-mode в Blogger (неактуально)

Сегодня задался задачей настроить отправку сообщений в блог из уютного Emacs и супер-удобного Org-mode в бложик на Blogger. Выбор пал на BPE, который умеет именно это: экспортировать org-документы в Blogger. Он конечно не умеет множество других вкусностей: показывать список сообщений, редактировать уже отправленные, но это пока не важно. Будет сильно неудобно, перееду на stand-alone блог.

Итак, сегодня я хочу рассказать как завести всю эту машинерию с BPE

Установка

BPE имеет в зависимостях несколько вещей:

  1. Надо установить googlecl
sudo apt-get install googlecl
  1. Надо установить html-minify
apt-get install python-software-properties
apt-add-repository ppa:chris-lea/node.js
apt-get update
apt-get install nodejs
-   Установить **html-minify**:
sudo npm -g install html-minify
  1. Установить сам BPE:
(package-install 'bpe)

Настройка

(require 'bpe)
(require 'htmlize nil 'noerror)
(setq bpe:account "yourmail@gmail.com")
(setq bpe:blog-name
      ;; В моём случае это "Жизнь, как она интересна"

      "Именно что заголовок вашего блога")
(define-key org-mode-map (kbd "C-c C-p") 'bpe:post-article)
(define-key org-mode-map (kbd "C-c C-i") 'bpe:insert-template)
(setq bpe:lang "ru_RU.UTF-8")

Запуск

Во время редактирования org-документа запустить bpe:post-article, в браузере попросят авторизовать приложение. После авторизации приложения в браузере надо нажать Enter в окошке bpe-post и сообщение будет отправлено.

! Сообщение попадёт в черновики, bpe.el вызывает google blogger post с флагом draft.

Проблемы

Вообще, схема работы BPE такая:

  • Сжать html в одну строчку с помощью htmlminimize утилиты
  • Вызвать google blogger post -u "yourmail@gmail.com" –blog "Название блога" и другие всякие ключи

К сожалению, htmlnotify не умеет заменять переносы строк на пробелы. Поэтому приходится добавлять пробел в начало каждой строки.
Для обхода этой проблемы можно использовать visual-line-mode!

PDFTK и DJVU

Понадобилось мне для дела обучения одной эквадорской девочки русскому языку научиться разным фокусам с PDF и DJVU. И подсказали мне полезнейшие утилиты для работы с PDF и DJVU из командной строки: PDFTK и DDJVU

PDFTK

Эта консольная утилита работы с PDF умеет следующие вещи:

  • Объединять несколько документов в один
  • Разбивать документ на несколько
  • Менять порядок страниц в документе
  • Шифровать/дешифровать документ
  • Заполнять PDF Forms с помощью
  • Добавлять водяные знаки, штампы
  • Узнавать/изменять/добавлять закладки и метадату
  • Разбить документ на одностраничные документы
  • Сжать или распаковать страницы в документе
  • Попытаться починить порченый документ

В моём случае меня интересовала возможность создавать из несколько PDF документов в один.

pdftk A=eor.pdf B=sazov1.pdf C=hprc.pdf D=brr.pdf \

    cat A32 B13 B10 A33-35 C7-8 D7 B12 output урок1.pdf

DDJVU

ddjvu нужен для перевода djvu файла или отдельных его страниц в картинку или pdf. Использовал я его для конвертации djvu документа в pdf документ, чтобы в дальнейшем можно было работать над этим pdf документов при помощи pdftk

ddjvu -format=pdf ../Essentials_of_Russian.djvu eor.pdf

Полезные ссылки

pdflabs.com