How the system maintains menu order

Note: this page is highly technical and only needed if you want to change menu.inc itself.

We have seven integer columns each representing a piece of the materialized path (the path leading to the root), p1 .. p7 . This algorithm is Peter Wolanin's implementation of materialized path, heavy exploiting the fact that we know the max depth of the tree.

All the numbers you see here are menu link identifiers, a primary integer key for each menu link (in short: mlid). Note that for queries, the list of "parents" is derived from p1,p2,p3, not stored separately. mlid, plid are stored separately.

Materialized path mlid plid set of parents
5.0.0 5 0 0
5.6.0 6 5 5, 0
7.0.0 7 0 0
7.13.0 13 7 7. 0
7.15.0 15 7 7, 0
7.15.23 23 15 15, 7, 0
7.15.16 16 15 15, 7, 0
7.10.0 10 7 7, 0
7.10.22 23 15 15, 7, 0
12.0.0 12 0 0

to get the tree for mlid = 23, we construct parents from p2, p1, 0

SELECT * from {menu_links} WHERE plid in (15, 7, 0) ORDER BY p1 ASC, p2 ASC, p3 ASC

result (showing p1.p2.p3):
5.0.0
7.0.0
7.10.0
7.13.0
7.15.0
7.15.16
7.15.23
12.0.0

We need to sort each subtree by weight, title in PHP but that's an accetable compromise otherwise each edit would need heavy renumbering.

If we did the a select on the whole table to get the full tree:

5.0.0
5.6.0
7.0.0
7.10.0
7.10.22
7.13.0
7.15.0
7.15.16
7.15.23
12.0.0

Now inserting is simple and so is reparenting. For example, if we
reparent 5.0.0 under 7.0.0 we get:

Materialized path mlid plid set of parents
7.0.0 7 0 0
7.5.0 5 7 7, 0
7.5.6 6 5 7, 5, 0
7.13.0 13 7 7. 0
7.15.0 15 7 7, 0
7.15.23 23 15 15, 7, 0
7.15.16 16 15 15, 7, 0
7.10.0 10 7 7, 0
7.10.22 23 15 15, 7, 0
12.0.0 12 0 0
note- plid only changed for one item (mlid = 5, plid was 0, now 7)- like the current book module.

All the children get updated with a single query like

SET p1 = 7, p2 = p1, p3 = p2 WHERE p1 = 5 and p2 != 0

Thus, in general, reparenting involves two steps:

1) Put in the new value in the 'plid' column and p1...p6 columns for the repareted item (involves one UPDATE query)

2) run an update for the materialized path columns for all children of the reparented item to reflect the path that their list of parents (path to root or materialzed path) has changed.

table adjustment

demigod - April 4, 2008 - 13:51

I assume that the second last line in both the tables wasn't adjusted at all, since it would be more sensible to put

7.10.22          22    10    10, 7, 0

there.

edit:
And in the third line of the second table there are some parents switched:

7.5.6             6     5     5, 7, 0

correct me, if I'm wrong...
Paul

 
 

Drupal is a registered trademark of Dries Buytaert.