[В начало]

Проблема в стандарте № S0054

Краткое описание

Отсутствие указаний по поводу возможности или невозможности изменения расположения в памяти вершин бинарного дерева при работе с ним функций tsearch и tdelete.

Подробное описание

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

Раздел стандарта

The Open Group Base Specifications Issue 6 IEEE Std 1003.1, 2004 Edition (SUS 3.0), System Interfaces,<br> description of functions tsearch(), tdelete(), tfind(), twalk().

Возможные последствия

Возможна некорректная работа приложения, использующего функции tsearch(), tdelete(), tfind(), twalk(), если предположения разработчиков приложения о возможности изменения расположения вершин дерева в памяти не совпадают с поведением реализации.

Внешние проявления проблемы

В проверенной реализации (RedHat Fedore Core 4.0, glibc 2.3.5), при удалении корневой вершины, другая вершина копируется в корневую, а удаляется скопированная.

Способы устранения

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

“The position of a tree node in memory may change as a result of call to tsearch() or tdelete(). Application developers should know that node address returned by tfind() are not permanent and can be altered by calls to tsearch() or tdelete()”

Ссылки

Явных указаний на эту проблему не обнаружено.

Принято

POSIX aardvark,
Request Number 129

[В начало]