KasperskyOS Community Edition 1.3

Использование строк KosString (strings.h)

API определен в заголовочном файле sysroot-*-kos/include/kos/strings.h из состава KasperskyOS SDK.

API позволяет использовать строки KosString, которые имеют следующие особенности:

1. Строка KosString представляет собой C-строку (с терминирующим нулем), следующую за заголовком со служебными данными.
2. Строки KosString хранятся в хеш-таблицах, представляющих собой массивы, элементами которых являются списки строк. (Указатели для создания связных списков строк хранятся в заголовках строк.) Каждый список состоит из одной или нескольких строк. В одном списке находятся строки, для которых остаток от деления хеш-значения строки на число списков в хеш-таблице имеет одинаковое значение. Основное свойство хеш-таблицы заключается в том, что вычислительная сложность поиска строки не зависит от степени заполнения этой таблицы, если все списки включают только одну строку.

   На практике при добавлении строк KosString в хеш-таблицу могут создаваться списки с несколькими строками, что приводит к варьированию вычислительной сложности поиска строк в хеш-таблице по следующей причине. При выполнении поиска для ключа вычисляется хеш-значение, которое преобразуется в индекс списка строк (вычислением остатка от деления хеш-значения на число списков), и, если в списке с рассчитанным индексом только одна строка, то после сравнения этой строки с ключом поиск будет завершен. Но если в списке с рассчитанным индексом несколько строк, то для завершения поиска может потребоваться сравнить ключ со всеми строками в этом списке. В таком случае вычислительная сложность поиска строки может быть больше, чем в случае с одной строкой в списке.

3. Строки KosString из одной хеш-таблицы уникальны, то есть в одной хеш-таблице нет одинаковых строк. Если строки из одной хеш-таблицы имеют разные идентификаторы, то это разные строки. (В API идентификатор строки KosString представляет собой указатель на эту строку.) Это позволяет сравнивать строки не по содержимому, а по идентификаторам, что обеспечивает независимость вычислительной сложности сравнения от размеров строк.
4. Размер строки KosString хранится в заголовке, а не рассчитывается на основе поиска терминирующего нуля, что обеспечивает независимость вычислительной сложности получения размера от фактического размера строки.
5. Строки KosString нельзя изменять. Эта особенность является следствием особенностей 2-4. Изменение строки может привести к появлению одинаковых строк в одной хеш-таблице, несоответствию фактического размера строки и сохраненного в заголовке, а также несоответствию содержимого строки индексу списка строк, в котором эта строка находится в хеш-таблице.
6. Строка KosString существует, пока счетчик ссылок на нее больше нуля. (Счетчик ссылок на строку хранится в заголовке.)

Сведения о функциях API приведены в таблице ниже.

Создание хеш-таблицы

Можно использовать хеш-таблицу по умолчанию, которая создается автоматически при инициализации библиотеки libkos. Эта таблица может включать не более 2039 списков строк с размером строк не более 65524 байт без учета терминирующего нуля.

Можно создать хеш-таблицу с требуемым максимальным числом списков строк и требуемым максимальным размером строк вызовом функции KosCreateStringRoot().

Хеш-таблица создается пустой, то есть не содержит строк.

Добавление строки KosString в хеш-таблицу

Чтобы добавить строку в хеш-таблицу по умолчанию, нужно вызывать функцию KosCreateString().

Чтобы добавить строку в заданную хеш-таблицу, нужно вызвать функцию KosCreateStringEx().

Если добавляемая строка уже есть в хеш-таблице, эти функции не добавляют новую строку, а передают через параметр outStr идентификатор уже существующей строки.

Поиск строки KosString в хеш-таблице

Чтобы выполнить поиск строки в хеш-таблице по умолчанию, нужно вызывать функцию KosGetString().

Чтобы выполнить поиск строки в заданной хеш-таблице, нужно вызывать функцию KosGetStringEx().

Поиск завершается успешно, если ключ и строка полностью совпадают.

Управление временем жизни строк KosString

Строка существует, пока счетчик ссылок на нее больше нуля. Функции KosCreateString() и KosCreateStringEx() добавляют в хеш-таблицу строку, счетчик ссылок на которую имеет значение 1. Если строка уже добавлена в хеш-таблицу, эти функции инкрементируют счетчик ссылок на эту строку. Функции KosGetString() и KosGetStringEx() инкрементируют счетчик ссылок на найденную строку. В дальнейшем этот счетчик можно инкрементировать и декрементировать для управления временем жизни строки. Передавая идентификатор строки другому компоненту программы, нужно инкрементировать счетчик ссылок на соответствующую строку, чтобы обеспечить существование этой строки на время, требуемое этому компоненту. Если строка больше не требуется, нужно декрементировать счетчик ссылок на эту строку, чтобы обеспечить ее уничтожение при отсутствии других ссылок.

Чтобы инкрементировать счетчик ссылок на строку, нужно вызвать функцию KosRefString() или KosRefStringEx().

Чтобы декрементировать счетчик ссылок на строку в хеш-таблице по умолчанию, нужно вызывать функцию KosPutString().

Чтобы декрементировать счетчик ссылок на строку в заданной хеш-таблице, нужно вызывать функцию KosPutStringEx().

Получение размера строки KosString

Чтобы получить размер строки без учета терминирующего нуля, нужно вызвать функцию KosGetStringLen().

Чтобы получить размер строки с учетом терминирующего нуля, нужно вызвать функцию KosGetStringSize().

Удаление хеш-таблицы

Чтобы удалить хеш-таблицу, нужно вызвать функцию KosDestroyStringRoot(). Таблица будет удалена только в том случае, если она пустая.

Сведения о функциях API

Функции strings.h