В основном ваша проблема заключается в том, что у вас есть определенные интервалы «действительной» памяти, память вне этих интервалов «недействительна», и вы хотите проверить заданный адрес, находится ли он в допустимом блоке памяти или нет.
Вы определенно можете сделать это, сохраняя начальные адреса всех выделенных блоков в двоичном дереве; затем найдите самый большой адрес в запрашиваемом адресе или ниже и просто убедитесь, что адрес соответствует длине действительного адреса. Это дает вам O (log n) времени запроса, где n = количество выделенных блоков. Конечно, этот же запрос можно использовать и для поиска самого блока, так что вы также можете прочитать содержимое блока по заданному адресу, который, я думаю, вам также понадобится.
Однако это не самая эффективная схема. Вместо этого вы можете использовать дополнительно одномерные деревья пространственных подразделений, чтобы пометить недействительные области памяти. Например, используйте дерево с коэффициентом ветвления 256 (соответствует 8 битам), которое отображает все эти блоки 16 КБ, в которых есть только недействительные адреса, на «1», а другие на «0»; дерево будет иметь только два уровня и будет очень эффективным для запроса. Когда вы видите адрес, сначала спросите это дерево, если оно определенно недействительно; только когда это не так, запросить другой. Это ускорит процесс ТОЛЬКО ЕСЛИ ВЫ ПОЛУЧИТЕ МНОГО НЕВЕРНЫХ ССЫЛК НА ПАМЯТЬ; если все ссылки на память действительно действительны и вы просто утверждаете, вы ничего не сохраните. Но вы можете перевернуть эту идею и использовать метку дерева для всех тех блоков 16 КБ или 256 В, которые имеют только допустимые адреса внутри них; насколько велико дерево, зависит от того, как работает ваш имитатор распределения памяти.