This README.md file provides further information on the memory graph examples in
.pl format. Symbol '🚨' indicates that an example cannot be learned via ShaPE.
The memory graph was obtained from an execution of
bash and exhibits a cyclic doubly-linked list
(CDLL) data structure that encodes piped commands, where an initial node (n8)
wraps access to the underlying CDLL via a head pointer. The nesting detection
feature can correctly split the memory graph into two sub-graphs, i.e.,
containing the single wrapper struct node and the CDLL. However, the CDLL data
structure cannot be learned, because it requires more than three parameters.
A binary tree with a single terminal leaf node. Two entry pointers, i.e., one pointing to the root of the tree and one pointing to the terminal node. Note that ShaPE can only learn the correct predicate due to the existence of the second entry pointer, because otherwise it could not communicate the shared node.
A binary tree where both pointers of each node either point to valid child nodes or to NULL.
A simple binary tree where leaf nodes are NULL termianted. a simple binary tree example.
A binary tree with an additional pointer pointing to the parent of a node.
A simple binary tree where leaf nodes are root termianted.
A binary tree with an additional pointer pointing to the root of the tree.
A simple ternary tree with the three pointer fields mid, left, and right.
A simple binary tree where leaf nodes are self termianted.
A binary tree with three entry pointers: ep0 points to the root node of the tree, ep1 points to root->left, and ep2 points to root->right.
A standard cyclic doubly linked list. The matching predicate cannot be learned, because it requires more than three parameters.
A cyclic singly linked list.
A doubly-linked where the prev pointer of the first element still points to NULL. Such a situation may be found during a modifying operation.
The four element DLL used as the running example for the LPAR23 publication.
A doubly linked list where the entry pointer points to an inner node of the dll.
A doubly linked list with three elements; NULL terminated.
A doubly linked list with three elements dll; self terminated.
A doubly linked list with three elements where the prev pointer of the last node is set to NULL; NULL terminated.
A lasso (pan-handle list) where the beginning of the list and the beginning of the cycle is denoted by an entry pointer. Can be learned via ShaPE.
A lasso (pan-handle list) where only the first node of the initial list is pointed to by an entry pointer. This cannot be solved by ShaPE, because one cannot forsee if the next node is the first node of the cycle.
A pan-handle list with an initial list segment of fixed length one. This is the memory graph of the ShaPE logo.
A parent binary tree with a child nested singly linked list.
A parent cyclic singly linked list with a child nested binary tree.
A parent singly linked list with a child nested binary tree.
A shared head node (wrapper) that points to two unshared singly linked lists.
A generic skip list whose shape predicate cannot be learned via ShaPE.
A memory graph with two unshared sub-graphs that exhibit a singly linked list and a binary tree.
A singly linked list with an additional pointer pointing to the head, i.e., first element of the lists.
A singly linked list with two entry pointers pointing to the first and last node of the list.
A simple singly linked list; NULL terminated.
A singly linked list with an additional pointer pointing to the tail, i.e., last element of the lists.
A simple singly linked list; self terminated.
A wrapper node (wrapper) that points to two unshared sub-graphs exhibiting a
singly linked list and binary tree.
A wrapper node (wrapper) that points to two unshared sub-graphs exhibiting a
singly linked list and cyclic singly linked list.
A series of three memory graphs exhibiting a simple binary tree shape:
bt-null-1.pl, bt-null-2.pl, and bt-null-3.pl.
A series of three memory graphs exhibiting an unshared singly linked list and
binary tree: sll-and-bt-0.pl, sll-and-bt-1.pl, and sll-and-bt-2.pl.