3.1.3 Таблица имен

3.1.3 Таблица имен

К таблице имен доступ осуществляется с помощью одной функции

name* look(char* p, int ins =0);

Ее второй параметр указывает, нужно ли сначала поместить строку символов в таблицу. Инициализатор =0 задает параметр, который надлежит использовать по умолчанию, когда look() взывается с одним параметром. Это дает удобство записи, когда look(«sqrt2») означает look(«sqrt2»,0), то есть просмотр, без помещения в таблицу. Чтобы получить такое же удобство записи для помещения в таблицу, определяется вторая функция:

inline name* insert(char* s) (* return look(s,1);*)

Как уже отмечалось раньше, элементы этой таблицы имеют тип:

srtuct name (* char* string; char* next; double value; *)

Член next используется только для сцепления вместе имен в таблице.

Сама таблица – это просто вектор указателей на объекты типа name:

const TBLSZ = 23; name* table[TBLSZ];

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

Для нахождения элемента в таблице в look() принимается простой алгоритм хэширования (имена с одним и тем же хэш-кдом зацепляются вместе):

int ii = 0; // хэширование char* pp = p; while (*pp) ii = ii««1 ^ *pp++; if (ii « 0) ii = -ii; ii %= TBLSZ;

То есть, с помощью исключающего ИЛИ каждый символ во входной строке «добавляется» к ii («сумме» предыдущих символов). Бит в x^y устанавливается единичным тогда и только тода, когда соответствующие биты в x и y различны. Перед примнением в символе исключающего ИЛИ, ii сдвигается на один бит влево, чтобы не использовать в слове только один байт. Это можно было написать и так:

ii ««= 1; ii ^= *pp++;

Кстати, применение ^ лучше и быстрее, чем +. Сдвиг важен для получения приемлемого хэш-кода в обоих случаях. Операторы

if (ii « 0) ii = -ii; ii %= TBLSZ;

обеспечивают, что ii будет лежать в диапазоне 0...TBLS1; % – это операция взятия по модулю (еще называемая получнием остатка).

Вот функция полностью:

extern int strlen(const char*); extern int strcmp(const char*, const char*); extern int strcpy(const char*, const char*);

name* look(char* p, int ins =0) (* int ii = 0; // хэширование char* pp = p; while (*pp) ii = ii««1 ^ *pp++; if (ii « 0) ii = -ii; ii %= TBLSZ;

for (name* n=table[ii]; n; n=n-»next) // поиск if (strcmp(p,n-»string) == 0) return n;

if (ins == 0) error(«имя не найдено»);

name* nn = new name; // вставка nn-»string = new char[strlen(p)+1]; strcpy(nn-»string,p); nn-»value = 1; nn-»next = table[ii]; table[ii] = nn; return nn; *)

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

Добавление нового name включает в себя создание нового объекта в свободной памяти с помощью операции new (см. #3.2.6), его инициализацию, и добавление его к списку имен. Последнее осуществляется просто путем помещения нового имени в голову списка, поскольку это можно делать даже не проверяя, имеется список, или нет. Символьную строку для имени тоже нужно сохранить в свободной памяти. Функция strlen() исползуется для определения того, сколько памяти нужно, new – для выделения этой памяти, и strcpy() – для копирования строки в память.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

3.2. Таблица Mangle

Из книги Iptables Tutorial 1.1.19 автора Andreasson Oskar

3.2. Таблица Mangle Как уже упоминалось выше, эта таблица предназначена, главным образом для внесения изменений в заголовки пакетов (mangle – искажать, изменять. прим. перев.). Т.е. в этой таблице вы можете устанавливать биты TOS (Type Of Service) и т.д.ОСТОРОЖНО: Еще раз напоминаю вам, что в


3.3. Таблица Nat

Из книги Microsoft Visual C++ и MFC. Программирование для Windows 95 и Windows NT автора Фролов Александр Вячеславович

3.3. Таблица Nat Эта таблица используется для выполнения преобразований сетевых адресов NAT (Network Address Translation). Как уже упоминалось ранее, только первый пакет из потока проходит через цепочки этой таблицы, трансляция адресов или маскировка применяются ко всем последующим


3.4. Таблица Filter

Из книги Создание шаблонов Joomla автора Автор неизвестен

3.4. Таблица Filter Как следует из названия, в этой таблице должны содержаться наборы правил для выполнения фильтрации пакетов. Пакеты могут пропускаться далее, либо отвергаться (действия ACCEPT и DROP соответственно), в зависимости от их содержимого. Конечно же, мы можем


4.2. Таблица трассировщика

Из книги TCP/IP Архитектура, протоколы, реализация (включая IP версии 6 и IP Security) автора Фейт Сидни М

4.2. Таблица трассировщика Кратко рассмотрим таблицу трассировщика, которую можно найти в файле /proc/net/ip_conntrack. Здесь содержится список всех активных соединений. Если модуль ip_conntrack загружен, то команда cat /proc/net/ip_conntrak должна вывести нечто, подобное:tcp 6 117 SYN_SENT src=192.168.1.6 dst=192.168.1.9


Таблица сообщений

Из книги Разработка приложений в среде Linux. Второе издание автора Джонсон Майкл К.

Таблица сообщений В библиотеке классов MFC для обработки сообщений используется специальный механизм, который получил название Message Map – таблица сообщений .Таблица сообщений состоит из набора специальных макрокоманд, ограниченных макрокомандами BEGIN_MESSAGE_MAP и END_MESSAGE_MAP.


Таблица

Из книги C++. Сборник рецептов автора Диггинс Кристофер

Таблица Чтобы создать таблицу можно воспользоваться главным меню Dremweaver, выбрав в нем Вставить | Таблица (Insert | Table). Опции Dreamweaver позволяют создавать таблицы любой сложности и структуры. Для примера мы продемонстрируем создание простой таблицы. Выберите цвет для таблицы по


5.24.2 Таблица ARP

Из книги Firebird РУКОВОДСТВО РАЗРАБОТЧИКА БАЗ ДАННЫХ автора Борри Хелен


2.4. Предотвращение конфликта имен с помощью пространств имен

Из книги Операционная система UNIX автора Робачевский Андрей М.

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


Таблица блокировок

Из книги Офисный компьютер для женщин автора Пастернак Евгения

Таблица блокировок Менеджер блокировок управляет таблицей блокировок для координации совместного использования ресурсов в клиентских потоках. Информация, предоставляемая здесь, может быть полезной при попытках исправить ситуации взаимных блокировок, например;* все в


Файловая таблица

Из книги Продвижение порталов и интернет-магазинов автора Гроховский Леонид О.

Файловая таблица Поля файлового дескриптора u_ofile и u_pofile содержат начальную информацию, необходимую для доступа процесса к данным файла. Дополнительная информация находится в системной файловой таблице и таблице индексных дескрипторов. Для обеспечения доступа процесса


Таблица ссылок

Из книги автора

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


3.1. Что такое таблица

Из книги автора

3.1. Что такое таблица Таблица состоит из ячеек, образующихся при пересечении строк и столбцов (рис. 3.2). Рис. 3.2. Пример стандартной таблицыРассмотрим элементы таблицы.• Ячейка – это основной элемент таблицы. Она формируется пересечением строки и столбца.• Строка – это


Сводная таблица

Из книги автора

Сводная таблица 1. Таблица приоритетов: критические, важные и незначительные ошибки.2. Формат: фактор, статус, что делать, приоритет.По результатам аудита составляется