Вчера Google выпустил новую библиотеку регулярных выражений — RE2. Библиотека написана на C++.

Существует два подхода к реализации регулярных выражений: недетерминированные конечные автоматы (NFA) и детерминированные конечные автоматы (DFA). Первый механизм регулярных выражений используется, например, в Perl, Python, Ruby и .NET. К сожалению, в этом случае время работы программы может расти экспоненциально, а также может неограниченно расти использование стека. Такое поведение оказалось неприемлемым для таких проектов Google, как Code Search, Sawzall и Bigtable, поэтому программисты компании написали библиотеку на основе детерминированных конечных автоматов. RE2 гарантирует линейную скорость выполнения поиска и ограниченное использование стека. DFA также используется, например, в lex и egrep. В отличие от большинства подобных реализаций RE2 поддерживает почти все основные возможности PCRE.

Библиотека распространяется под BSD лицензией.

UPD: Убрал Tcl из примеров NFA, сейчас там используются DFA.

Я заметил, у разработчиков совершенно полярное отношение к библиотеке Boost.Spirit: либо она им жутко не нравится, либо они фанатеют от нее. Конечно, описывать грамматику на C++ – занятие на любителя. Таким любителем оказался и я, когда познакомился со Спиритом. Хочу показать, как с помощью Спирита можно довольно просто решать повседневные задачи разбора текста.

Простая задача – как два пальца

На Спирите очень удобно писать маленькие парсеры «не отходя от кассы» – прямо в C++ коде. Вот например, как вы поступите если нужно распарсить строку вида «число-число», которая задает диапазон страниц для печати? На Спирите – одна строчка:

bool ok = parse(First, Last, (uint_ >> L"-" >> uint_), MinMax) && (First == Last);

Посложнее…

Более того – можно ненамного сложнее создавать и парсеры побольше. В качестве примера рассмотрю парсер мини-языка, который я делал для API Яндекс.Бара. Задача была такова: для облегчения загрузки плагинов в баре используется XML, который довольно избыточный сам по себе. Но зато XML легче грузить из JavaScript-а, чем парсить произвольный формат (на JS пишутся расширения под FireFox, в том числе и Я.Бар).

Итак, что мне было нужно – имея на входе обычную инфиксную нотацию:

Краткое содержание статьи (для тех кто знаком с boost::mpl), typename опущены для ясности:

a = b;				==>		typedef b a;
f(x)				==>		f<x>::type
f(x) { return x*; }		==>		template<typename x> struct x { typedef x* type; };
f()(x)				==>		f::apply<x>::type
a[x]				==>		mpl::at<a, x>::type
(x ? y : z)			==>		mpl::if_<x, y, z>::type
switch (if_<x, y, z>)		==>		*Уфф*, общая (default) и частичные специализации
{
	case if_<bool_<false>, y, z>: return y;
	default: return z;
}

Под хабракатом есть немного пояснений :)

Покажет ли ваш редактор/IDE, что «a++;» в этом C/C++ коде — часть комментария?
int a=1;
//some comment \
a++;
printf("%d\n",a);

А такой вариант?
int a=1;
//some comment ??/
a++;
printf("%d\n",a);

Всем привет. А особенно тем, кто пишет на плюсах и интересуется грядущими изменениями языка.
Для исследования фич нового стандарта С++ я сделал забавную штуку — функцию для превращения простого функтора в ленивый. Т.е. вычисляемый не более одного раза, и только при первом обращении.
Для использования вам понадобится простой функтор, без аргументов, возвращающий значение.
Применяете к нему calc_once(some_func) — и он становится ленивым.

auto my_func = calc_once([]{ return SomeHugeCalculation(); });
if ((my_func() && some_case) || (!my_func() && some_other_case))
{
}

* This source code was highlighted with Source Code Highlighter.

Под хабракатом код, там и auto, и decltype, и лямбды.

UPD. Спасибо за карму. Перенес в блог С++.

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

Со времён, когда проектировался С++, относительная (к скорости оперативной памяти) скорость процессора выросла в 400 раз. Плюс к тому, у процессора появились большие кэши и предсказание ветвлений в коде. Всё это вместе самым серьёзным образом сказывается на эффективности С++ на современных платформах. Ниже даю аннотацию и пару ссылок, где предлагается использовать эти факты для повышения эффективности кода.

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

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

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

Утечка памяти — довольно серьезная и опасная проблема. Быть может, пользователь и не заметит однократной утечки каких-нибудь 32Кб памяти (а ведь это целые 5% от 640Кб, которых «хватит всем»), но постоянно теряя сложные иерархические структуры или массивы размером больше INT_MAX (которые мы так любим создавать на 64-битной архитектуре) мы обречем его на страдания, а наш продукт на провал.

Не допускать ситуации вроде бы и не трудно — воспользуемся правилом «класть на место всё что взяли», но на практике это сильно осложняется человеческим фактором (банальная невнимательность), хитростью архитектуры и нелинейным порядком выполнения операторов, например, из-за применения исключений.

А можно было бы просто «отдаться» автоматическому сборщику мусора, ценой потери производительности (и это не обязательно Managed C++, для Native C++ / C есть библиотеки сборки мусора, вот, например).

Но мы поговорим о ситуации когда уже «всё плохо».

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

В C++ это обычно делается выводом в поток (как вариант — использование boost: lexical_cast<> — что в нашем случае практически одно и тоже).

Для встроенных типов это не проблема, а вот как быть, если нужно вывести скажем std: vector? Увы, но у std: vector нет оператора вывода в поток.

В результате решения этой проблемы написал код, которым хочу поделиться с сообществом.

Постановка задачи

Что же я имел ввиду, когда написал «неизвестное» имя функции? А значит это то, что имя функции, её параметры и, в конце концов, соглашение вызова, становятся известными только во время выполнения программы. Займемся её вызовом! =)

Обнаружил, что есть аспект работы C++, о котором я раньше как-то не задумывался. А именно: если у вас есть две реализации одного метода (перегрузка), отличающихся константностью *this:
    int & v();
    const int & v() const;
когда и какой метод будет вызываться?

Для меня красота C++ заключается, в первую очередь, во вседозволенности и ужасающей мощи языка. Мы можем работать с памятью так же плотно, как и в C, и в то же время имеем такие средства абстракции, как шаблоны и STL, где параметризовать можно что угодно и чем угодно.
Плата за это соответствующая — не всегда вразумительные ошибки компилятора (попробуйте забыть поставить точку с запятой после определения класса), очень большой срок подготовки и обучения программистов, но самое главное — некоторые баги становятся заметными только во время исполнения программы.
Мы хотим больше полезных ворнингов до запуска наших программ. Одно из средств получения желаемого — статический анализ кода. Статический — значит, не запуская программу. Интересны не только вероятные ошибки, случаи undefined behaviour, утечки памяти, но и вещи вроде недоступности/неиспользуемости кода, рекомендации по повышению интуитивности стиля программирования.

Введение

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

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

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

Неудаление мютекса приводит к утечке памяти, незахват — к некорректным данным, а неосвобождение — к блокировке всех функций, работающих с общими данными.

Ниже рассматривается работа с мютексами в Windows и Unix, подобная идея может быть использована при работе с другими объектами синхронизации.

Эта идея является частным случаем методики «Выделение ресурса — есть инициализация (RAII)».

Не самый популярный, но оттого не менее полезный сервис Google — возможность создать свою поисковую систему. Технология простая — вы отбираете сайты, в которых поисковик будет искать прежде всего, сужая, таким образом область поиска и получая красивые релевантные результаты.
Мне захотелось найти поисковик для C++, но я ничего полезного не увидел. Зашел на Google Custom Search, накидал список сайтов (штук 15, не больше) и увидел, что это хорошо — ищет уже гораздо лучше стандартного гугл-поиска. Вот ссылка на эту мини-искалку. Буду рад, если хабрасиплюсплюсеры помогут мне в развитии и пополнении списка допустимых сайтов. Тут есть следующие варианты:

• "ха! дык это ведь уже есть!" вы тыкаете меня носом в уже созданный тематический поисковик по C++, я посыпаю голову пеплом, закрываю топик и радостно этим поисковиком пользуюсь,
• "ура, мы создадим СВОЙ поисковик, с функторами и аллокаторами". Тут видится два разумных варианта. Первый — я раздаю 100 инвайтов желающим присоединиться к наполнению базы сайтов поисковика и они непосредственно включаются в редактирование. Или же можно содать общедоступную и свободно редактируемую страничку (да хоть эту), на которую сваливать все ссылки. Ну а страничка в качестве источника ссылок будет съедаться гуглом.
• также принимаются предложения по смене системы создания custom search, идеи о том, как можно подключать штуки вроде закладок delicious (или, например, ), помеченных соответствующими тегами, страниц MSDN, URL которых никак не связан с темой, и прочее.

STL славится своей способностью заполнять метры экранного пространства сообщениями об ошибках. Надоело смотреть на экран и видеть перлы вроде:

testmap.cpp:25: error: no matching function for call to ‘std::map<int, double, std::less, std::allocator<std::pair<const int, double> > >::map(int, int, int)’
/usr/include/c++/4.3/bits/stl_map.h:175: note: candidates are: std::map<_Key, _Tp, _Compare, _Alloc>::map(const std::map<_Key, _Tp, _Compare, _Alloc>&) [with _Key = int, _Tp = double, _Compare = std::less, _Alloc = std::allocator<std::pair<const int, double> >]
/usr/include/c++/4.3/bits/stl_map.h:165: note: std::map<_Key, _Tp, _Compare, _Alloc>::map(const _Compare&, const _Alloc&) [with _Key = int, _Tp = double, _Compare = std::less, _Alloc = std::allocator<std::pair<const int, double> >]


ну и еще пара десятков строк.

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

Не так давно понадобилась написать приложение которое бы автоматически отправляло сообщение по Skype определенному пользователю, который есть в списке контактов. Задача была не много сложнее, но дело не в этом. Решил написать маленькую статейку по использованию Skype API.

const int AllocAccountType_ACCOUNT_IS_CARRIED_ON_NON_CUSTOMER_SIDE_OF_BOOKS_AND_IS_CROSS_MARGINED = 6;
const char ClearingFeeIndicator_FULL_AND_ASSOCIATE_MEMBER_TRADING_FOR_OWN_ACCOUNT_AND_AS_FLOOR_BROKER[] = "F";


и так 2634 строки заголовочного файла с одними константами.

вот такое API приходится ковырять иногда. Есть еще примеры позлее?

P.s
Опубликовано по просьбе JohnWest

Я решил провести один эксперимент, суть его пока не могу разглашать, но по результатам обязательно опишу его))) Для этого эксперимента, мне нужно написать приложение которое работает как сервис в Windows.

Нужно заменить ровно один (любой) символ в следующей строке, причём так, чтобы она скомпилилась и было выведено ровно 20 звёздочек:

int main() { int i, n = 20; for (i = 0; i < n; i--) { printf("*"); } }

* This source code was highlighted with Source Code Highlighter.

Для тех, кто «набил руку» на особенностях C, задачка, скорее всего, сложности не представляет; но существует как минимум 3 решения, и если вы нашли одно — то это не повод расслабиться :) А может быть, вы найдёте ещё четвёртое, пятое..?
UPD 1: Первое правильное решение предложил lostmsu, остальные два — steck
Не читайте комменты, поломайте мозг!