Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The reason can be found in one of the comments:</p> <pre><code> 547/* 548 * Double linked lists with a single pointer list head. 549 * Mostly useful for hash tables where the two pointer list head is 550 * too wasteful. 551 * You lose the ability to access the tail in O(1). 552 */ </code></pre> <p>If you had *prev instead of **pprev, and because we are trying to save memory, we don't include *prev in the head, then our hlist implementation looks like this:</p> <pre><code>struct hlist_head { struct hlist_node *first = null; }; struct hlist_node { struct hlist_node *next; struct hlist_node *prev; }; </code></pre> <p>Notice that the <code>prev</code> pointer cannot point to the head, or <code>head-&gt;first</code> (unlike <code>**pprev</code>). This complicates the hlist implementation, as you'll see when we implement <code>hlist_add_before()</code>:</p> <pre><code>void hlist_init(struct hlist_head *head) { head-&gt;first = null; } void hlist_add_head(struct hlist_head *head, struct hlist_node *node) { struct hlist_node *next = head-&gt;first; head-&gt;first = node; node-&gt;next = next; node-&gt;prev = NULL; if (next) { next-&gt;prev = node; } } </code></pre> <p>Notice that <code>prev</code> has nothing to point to, in the above imeplementation of <code>hlist_add_head()</code>. So, now when you implement <code>hlist_add_before()</code> it looks like this:</p> <pre><code>void hlist_add_before(struct hlist_head *head, struct hlist_node *node, struct hlist_next *next) { hlist_node *prev = next-&gt;prev; node-&gt;next = next; node-&gt;prev = prev; next-&gt;prev = node; if (prev) { prev-&gt;next = node; } else { head-&gt;first = node; } } </code></pre> <p>Notice that now we need to pass in <code>head</code> as well to <code>hlist_add_before()</code>, which requires an extra <code>push</code> instruction for pushing <code>head</code> on the stack. Besides, there's an extra conditional check in the implementation, which further slows down things.</p> <p>Now, try implementing other hlist operations, with <code>*prev</code> instead of <code>**pprev</code>, and you'll find out that your implementation is going to be slower than what you saw in the linux kernel.</p>
    singulars
    1. This table or related slice is empty.
    1. POUse of double pointer in linux kernel Hash list implementation
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USSudhanshu
    1. USSudhanshu
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POUse of double pointer in linux kernel Hash list implementation
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COThanks for your answer. But my doubt is why not have *prev and have a doubly linked list. Using this you can traverse both ways. You can add and delete nodes in O(1). The memory used is same for both cases. I am obviously missing something here. Could you please point out my mistake?
      singulars
      1. PO
      1. USbala1486
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload