Визуализация кругового двойного связанного списка с использованием natvis

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

<Type Name="TListBidir&lt;*&gt;">
    <Expand>
        <LinkedListItems>
            <HeadPointer>next</HeadPointer>
            <NextPointer>next</NextPointer>
            <ValueNode>($T1 *)this</ValueNode>
        </LinkedListItems>
    </Expand>
</Type>

Я надеялся, что смогу добавить атрибут Condition для NextPointer, сравнивая его с заголовком списка, но, поскольку NextPoint оценивается в контексте узла, я не знаю, с чем его сравнивать:

<NextPointer Condition="next!=XXXXXXXXX">next</NextPointer>

Вот как это выглядело с предыдущими (2010 г.) визуализаторами, использующими директиву skip, как #list обрабатывал это автоматически:

#list защищен от бесконечных обходов и изящно справляется с циклическим списком. Кроме того, вы можете использовать выражение skip: для обозначения контрольного узла, о котором не следует сообщать. Хотя название подразумевает, что узел будет пропущен, на самом деле это приводит к остановке обхода, поэтому, если ваш дозорный узел находится первым, вы должны начать обход после него.

TListBidir<*,*,*>{
    children
    (
      #list(
        head: ((($T2 *)&$c)->next),
        next: next,
        skip : &($c)
      ): (($T1 *)(&$e))
    )
}

Как я могу объяснить в natvis отладчику, что он должен прекратить расширять список, как только он снова достигнет корневого элемента?


c++ visual-studio debugging debuggervisualizer natvis
person Suma    schedule 07.08.2012    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Платформа natvis в настоящее время не поддерживает круговые связанные списки без указания счетчика. Если вы предоставите счет, он должен работать. Тем не менее, без подсчета нет хорошего способа помешать расширению продолжаться вечно.

person Cagri Aslan    schedule 15.08.2012

arrow_upward
3
arrow_downward

У меня была аналогичная проблема, но не с круговым списком, а с узлом-сторожем в конце, который указывал на себя, и я придумал интересное решение, которое можно адаптировать к вашим потребностям: вы можете использовать тернарный оператор для подделки настоящее прекращение. Выражения внутри <NextPointer> могут быть любыми, которые вы можете написать на ванильном C, поэтому вы можете выполнять реальные вычисления (но, к сожалению, без рекурсии).

(Обратите внимание, что вам не разрешено помещать атрибут Condition в <NextPointer>, поэтому тернарный оператор — единственный способ выполнить там условия.)

Итак, в моем случае список завершился следующим образом:

<LinkedListItems>
    <HeadPointer>this</HeadPointer>
    <NextPointer>next != this ? next : 0</NextPointer>
    <ValueNode>items</ValueNode>
</LinkedListItems>

В вашем случае, если у каждого узла есть указатель на свой контейнер, вы можете использовать его для сравнения с головным узлом:

<LinkedListItems>
    <HeadPointer>container-&gt;head</HeadPointer>
    <NextPointer>next != container-&gt;head ? next : 0</NextPointer>
    <ValueNode>items</ValueNode>
</LinkedListItems>

Или, без сущностей &gt; и написанных как более традиционный C, это эквивалентно:

next != container->head ? next : NULL

Однако, если у вас нет какого-либо обратного указателя container, вам, вероятно, не повезло с этим, поскольку нет никакого способа, взглянув только на один узел в циклически связанном списке, чтобы ответить, действительно ли он " последний" узел.

person Sean Werkema    schedule 09.03.2016
comment
Гм, у вас нет троичной обратно? Разве это не должно быть next != container->head ? next : 0? Или, может быть, я не понимаю, что вы делаете? - person Adrian; 01.04.2016
comment
Да, в этой версии все было наоборот; Я исправлю это. Фактический код, который я использую, намного сложнее, потому что структура данных намного сложнее, но после нескольких дополнительных косвенных указателей все еще слабо сводится к циклически связанному списку. Я запутался, извлекая из него основную логику для этой публикации. - person Sean Werkema; 03.04.2016
comment
Я не знаю насчет VS2012, но в VS2013, если список в конце концов попадает на указатель, описанный в <HeadPointer>, он также останавливает список, как если бы <NextPointer> указывал на nullptr. - person Adrian; 04.04.2016

arrow_upward
3
arrow_downward

Вы можете сделать это с помощью элемента CustomListItems:

<CustomListItems>
    <Variable Name="orig_head" InitialValue="head"/>
    <Variable Name="iter" InitialValue="first_elem"/>
    <Loop>
        <Break Condition="iter == orig_head || iter == 0"/>
        <Item>*iter</Item>
        <Exec>iter = iter-&gt;next_elem</Exec>
    </Loop>
</CustomListItems>

CustomListItems позволяет сохранить заголовок в переменной, чтобы его можно было использовать при перемещении по списку. Если ваша голова имеет другой тип, то узлы списка вам нужно будет привести к типу узла.

person Marc Aldorasi    schedule 22.08.2016