gsoc, text search selectivity and dllist enhancments - Mailing list pgsql-hackers

Hi,

attached are two patches against HEAD. The smaller one is meant to be
commited - it adds some functions that manipulate double-linked lists,
namely inserting a new cell after or before another cell and swapping
two adjacent cells. It felt like being back in the first year of
studies. I hope I didn't mess those pointers up.

The gzipped one is WIP for my GSoC project. I've reworked the algorithm
for determing most common lexemes. The goal was to avoid scanning
through all currently kept lexemes in each iteration of the loop that
processes all lexemes from sample tsvectors. Heikki suggested to
introduce a hashtable, so I did that. It works, passes regression tests
and correctly identifies most common lexemes in my toy test database.
Of course it's all quite useless without a selectivity operator that
could use those statistics. I'm sending it in to maybe get some feedback
during the commit fest.

The second patch depends on the first, and also on the one I sent eariler:
http://archives.postgresql.org/message-id/484418B8.6060004@students.mimuw.edu.pl

I'll add the first one to the commit fest page, and I'm sending it to
-hackers with congratulations on the decision to ditch -patches ;)

Cheers,
Jan

--
Jan Urbanski
GPG key ID: E583D7D2

ouden estin
diff --git a/src/backend/lib/dllist.c b/src/backend/lib/dllist.c
index b771fce..79c402e 100644
*** a/src/backend/lib/dllist.c
--- b/src/backend/lib/dllist.c
***************
*** 212,214 ****
--- 212,336 ----
      l->dll_head = e;
      /* We need not check dll_tail, since there must have been > 1 entry */
  }
+
+ /* Insert a node after the given target node. */
+ void
+ DLAddAfter(Dlelem *e, Dlelem *target)
+ {
+     Dllist    *l = target->dle_list;
+
+     e->dle_list = l;
+     e->dle_prev = target;
+     e->dle_next = target->dle_next;
+
+     if (l->dll_tail != target)
+     {
+         /* Target is not the tail */
+         Assert(target->dle_next != NULL);
+         target->dle_next->dle_prev = e;
+     }
+     else
+     {
+         /* Target is the tail */
+         Assert(target->dle_next == NULL);
+         l->dll_tail = e;
+     }
+     target->dle_next = e;
+     return;
+ }
+
+ /* Insert a node before the given target node. */
+ void
+ DLAddBefore(Dlelem *e, Dlelem *target)
+ {
+     Dllist    *l = target->dle_list;
+
+     e->dle_list = l;
+     e->dle_prev = target->dle_prev;
+     e->dle_next = target;
+
+     if (l->dll_head != target)
+     {
+         /* Target is not the head */
+         Assert(target->dle_prev != NULL);
+         target->dle_prev->dle_next = e;
+     }
+     else
+     {
+         /* Target is the head */
+         Assert(target->dle_prev == NULL);
+         l->dll_head = e;
+     }
+     target->dle_prev = e;
+     return;
+ }
+
+ /* Swap a node with its successor */
+ void
+ DLSwapWithNext(Dlelem *e)
+ {
+     Dllist    *l = e->dle_list;
+     Dlelem    *tmp;
+
+     Assert(e->dle_next != NULL);
+
+     tmp = e->dle_next;
+     e->dle_next = tmp->dle_next;
+     if (l->dll_tail != tmp)
+     {
+         Assert(tmp->dle_next != NULL);
+         tmp->dle_next->dle_prev = e;
+     }
+     else
+     {
+         l->dll_tail = e;
+     }
+     if (l->dll_head != e)
+     {
+         Assert(e->dle_prev != NULL);
+         e->dle_prev->dle_next = tmp;
+     }
+     else
+     {
+         l->dll_head = tmp;
+     }
+     tmp->dle_prev = e->dle_prev;
+     e->dle_prev = tmp;
+     tmp->dle_next = e;
+     return;
+ }
+
+ /* Swap a node with its predecessor */
+ void
+ DLSwapWithPrevious(Dlelem *e)
+ {
+     Dllist    *l = e->dle_list;
+     Dlelem    *tmp;
+
+     Assert(e->dle_prev != NULL);
+
+     tmp = e->dle_prev;
+     e->dle_prev = tmp->dle_prev;
+     if (l->dll_head != tmp)
+     {
+         Assert(tmp->dle_prev != NULL);
+         tmp->dle_prev->dle_next = e;
+     }
+     else
+     {
+         l->dll_head = e;
+     }
+     if (l->dll_tail != e)
+     {
+         Assert(e->dle_next != NULL);
+         e->dle_next->dle_prev = tmp;
+     }
+     else
+     {
+         l->dll_tail = tmp;
+     }
+     tmp->dle_next = e->dle_next;
+     e->dle_next = tmp;
+     tmp->dle_prev = e;
+     return;
+ }
diff --git a/src/include/lib/dllist.h b/src/include/lib/dllist.h
index d754b03..597e71f 100644
*** a/src/include/lib/dllist.h
--- b/src/include/lib/dllist.h
***************
*** 72,77 ****
--- 72,81 ----
  extern Dlelem *DLRemHead(Dllist *list); /* remove and return the head */
  extern Dlelem *DLRemTail(Dllist *list);
  extern void DLMoveToFront(Dlelem *e);    /* move node to front of its list */
+ extern void DLAddAfter(Dlelem *e, Dlelem *target); /* add node after another */
+ extern void DLAddBefore(Dlelem *e, Dlelem *target); /* same, but add before */
+ extern void DLSwapWithNext(Dlelem *e);
+ extern void DLSwapWithPrevious(Dlelem *e);

  /* These are macros for speed */
  #define DLGetHead(list)  ((list)->dll_head)