Необходимо реализовать класс для DNS cache с таким интерфейсом:

class DNSCache {
public:
  explicit DNSCache(size_t max_size);
  void update(const std::string& name, const std::string& ip);
  std::string resolve(const std::string& name);
};

Класс хранит в себе соответствия имя = ip адрес, максимальное число записей, которые он может хранить задается в конструкторе через max_size.

Через update() в класс поступают новые данные, которые могут или обновить существующую запись или добавить новую. При превышении лимита max_size из памяти должны удаляться самые давно неиспользуемые записи.

Метод resolve() возвращает из кеша IP адрес для имени name или пустую строку, если не найден.

Класс должен обеспечивать корректную работу в многопоточном приложении, когда update() и resolve() вызываются из разных ниток параллельно.

1. Для выполнения данного задания предварительно был объявлен абстрактный класс DNSCache (dns_cache.h). Тем самым вы явно указываем необходимый минимум, который должна иметь реализация данного класса, а также предоставляем удобный интерфейс для его использования.

2. Сама реализация представлена в файлах dns_cache_impl.h и dns_cache_impl.cpp. В качестве структур данных используются двунаправленный список (std::list) и ассоциативный контейнер на основе хеш-таблицы (std::unordered_map). Двунаправленный список используется как хранилище, в котором элементы хранятся в порядке их добавления/обновления. Также данный контейнер позволяет вставлять/удалять элементы за константное время. Благодаря этому можно отслеживать давно не обновляемые домены. Ассоциативный контейнер на основе хеш-таблицы используется дла быстрого поиска элементов по имени name в функции resolve(). В качестве значений хранятся итераторы на элементы двунаправленного списка.

3. Для корректной работы в многопоточном приложении используется мьютекс, а точнее его разновидность - std::shared_mutex. Данный мьютекс представляет два типа использования: уникальный доступ для записи одним потоком и общий доступ для чтения нескольким потокам. Это может значительно ускорить работу структур, которые используют данную конструкцию, если данные редко обновляются и часто используются для чтения.

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

1. Предложите работающую без ошибок реализацию класса, обеспечивающую максимальное быстродействие.

Ответ: Описание представленной реализации приведено в пункте "Реализация". Описанная реализация была протестирована на локальных тестах, которые также находятся в репозитории (test.h и test.cpp).

2. Какую сложность обеспечивает предложенное решение при вставке записей, при обновлении существующих записей, при поиске записей?

Ответ: При вставке записей: О(1). При обновлении записей: О(1). При поиске записей: О(1).

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

Ответ: Для этих целей был использован паттерн Singleton (см. п. 4 "Реализация").

1. С++20
2. GCC 11+ version requires
3. CMake 3.10 version requires