C++ - Страустрап Бьярн, Хилл Мюррей

Поскольку все статические объекты инициализируются нлем, это тривиальное описание таблицы 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.1.4 Обработка ошибок

Поскольку программа так проста, обработка ошибок не сотавляет большого труда. Функция обработки ошибок просто счтает ошибки, пишет сообщение об ошибке и возвращает управлние обратно:

int no_of_errors;

double error(char* s) (* cerr «„ "error: " «« s «« «\n“; no_of_errors++; return 1; *)

Возвращается значение потому, что ошибки обычно встречаются в середине вычисления выражения, и поэтому надо либо полностью прекращать вычисление, либо возвращать значение, которое по всей видимости не должно вызвать последующих ошибок. Для простого калькулятора больше подходит последнее. Если бы get_token() отслеживала номера строк, то error() мола бы сообщать пользователю, где приблизительно обнаружена ошибка. Это наверняка было бы полезно, если бы калькулятор использовался неитерактивно.