All, Here's an updated version of the patch which cleans up a couple of the previous issues, including addressing some of the free'ing issues.
Looking forward to comments.
Thanks,
Stephen
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index 0db60b1..85fb67f 100644
*** a/src/backend/nodes/copyfuncs.c
--- b/src/backend/nodes/copyfuncs.c
*************** _copyAlterTSConfigurationStmt(const Alte
*** 3695,3704 ****
* list MUST be of type T_List; T_IntList and T_OidList nodes don't
* need deep copies, so they should be copied via list_copy()
*/
- #define COPY_NODE_CELL(new, old) \
- (new) = (ListCell *) palloc(sizeof(ListCell)); \
- lfirst(new) = copyObject(lfirst(old));
-
static List *
_copyList(const List *from)
{
--- 3695,3700 ----
*************** _copyList(const List *from)
*** 3711,3723 ****
new = makeNode(List);
new->length = from->length;
! COPY_NODE_CELL(new->head, from->head);
prev_new = new->head;
curr_old = lnext(from->head);
while (curr_old)
{
! COPY_NODE_CELL(prev_new->next, curr_old);
prev_new = prev_new->next;
curr_old = curr_old->next;
}
--- 3707,3734 ----
new = makeNode(List);
new->length = from->length;
! new->head = new->base;
! new->avail_bitmap = (1 << LIST_PREALLOC) - 1 - 1;
!
! lfirst(new->head) = copyObject(lfirst(from->head));
!
prev_new = new->head;
curr_old = lnext(from->head);
while (curr_old)
{
! int free_spot = ffs(new->avail_bitmap);
!
! if (free_spot && free_spot <= LIST_PREALLOC)
! {
! prev_new->next = new->base + --free_spot;
! new->avail_bitmap &= ~(1 << free_spot);
! }
! else
! prev_new->next = (ListCell *) palloc(sizeof(ListCell));
!
! lfirst(prev_new->next) = copyObject(lfirst(curr_old));
!
prev_new = prev_new->next;
curr_old = curr_old->next;
}
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index 209b722..744ee8f 100644
*** a/src/backend/nodes/list.c
--- b/src/backend/nodes/list.c
*************** check_list_invariants(const List *list)
*** 39,44 ****
--- 39,45 ----
Assert(list->length > 0);
Assert(list->head != NULL);
Assert(list->tail != NULL);
+ Assert(list->base != NULL);
Assert(list->type == T_List ||
list->type == T_IntList ||
*************** check_list_invariants(const List *list)
*** 49,54 ****
--- 50,57 ----
if (list->length == 2)
Assert(list->head->next == list->tail);
Assert(list->tail->next == NULL);
+
+ Assert(list->avail_bitmap >= 0 && list->avail_bitmap <= (1 << LIST_PREALLOC) - 1);
}
#else
#define check_list_invariants(l)
*************** check_list_invariants(const List *list)
*** 56,63 ****
/*
* Return a freshly allocated List. Since empty non-NIL lists are
! * invalid, new_list() also allocates the head cell of the new list:
! * the caller should be sure to fill in that cell's data.
*/
static List *
new_list(NodeTag type)
--- 59,69 ----
/*
* Return a freshly allocated List. Since empty non-NIL lists are
! * invalid, new_list() starts as a 1-node list: the caller should
! * be sure to fill in the head cell's data.
! *
! * new_list() will allocate LIST_PREALLOC space for additional cells
! * to minimize palloc() calls.
*/
static List *
new_list(NodeTag type)
*************** new_list(NodeTag type)
*** 65,77 ****
List *new_list;
ListCell *new_head;
! new_head = (ListCell *) palloc(sizeof(*new_head));
! new_head->next = NULL;
! /* new_head->data is left undefined! */
!
new_list = (List *) palloc(sizeof(*new_list));
new_list->type = type;
new_list->length = 1;
new_list->head = new_head;
new_list->tail = new_head;
--- 71,94 ----
List *new_list;
ListCell *new_head;
! /*
! * Allocate our new_list, which will also include the first
! * block of ListCell's in the ->base var
! */
new_list = (List *) palloc(sizeof(*new_list));
new_list->type = type;
new_list->length = 1;
+
+ /* initialize the head node entry in new_list->base
+ * new_head->data will be undefined until the caller fills it in */
+ new_head = new_list->base;
+ new_head->next = NULL;
+
+ /* subtract 1 to get all-1's, marking all available
+ * subtract another 1 to clear the first bit, marking it
+ * used by the initially-allocated head node
+ */
+ new_list->avail_bitmap = (1 << LIST_PREALLOC) - 1 - 1;
new_list->head = new_head;
new_list->tail = new_head;
*************** static void
*** 89,98 ****
new_head_cell(List *list)
{
ListCell *new_head;
! new_head = (ListCell *) palloc(sizeof(*new_head));
! new_head->next = list->head;
list->head = new_head;
list->length++;
}
--- 106,123 ----
new_head_cell(List *list)
{
ListCell *new_head;
+ int free_spot = ffs(list->avail_bitmap);
! /* Check for a free spot in our initial allocation */
! if (free_spot && free_spot <= LIST_PREALLOC)
! {
! new_head = list->base + --free_spot;
! list->avail_bitmap &= ~(1 << free_spot);
! }
! else
! new_head = (ListCell *) palloc(sizeof(*new_head));
+ new_head->next = list->head;
list->head = new_head;
list->length++;
}
*************** static void
*** 108,115 ****
new_tail_cell(List *list)
{
ListCell *new_tail;
- new_tail = (ListCell *) palloc(sizeof(*new_tail));
new_tail->next = NULL;
list->tail->next = new_tail;
--- 133,148 ----
new_tail_cell(List *list)
{
ListCell *new_tail;
+ int free_spot = ffs(list->avail_bitmap);
+
+ if (free_spot && free_spot <= LIST_PREALLOC)
+ {
+ new_tail = list->base + --free_spot;
+ list->avail_bitmap &= ~(1 << free_spot);
+ }
+ else
+ new_tail = (ListCell *) palloc(sizeof(*new_tail));
new_tail->next = NULL;
list->tail->next = new_tail;
*************** static ListCell *
*** 185,192 ****
add_new_cell(List *list, ListCell *prev_cell)
{
ListCell *new_cell;
- new_cell = (ListCell *) palloc(sizeof(*new_cell));
/* new_cell->data is left undefined! */
new_cell->next = prev_cell->next;
prev_cell->next = new_cell;
--- 218,233 ----
add_new_cell(List *list, ListCell *prev_cell)
{
ListCell *new_cell;
+ int free_spot = ffs(list->avail_bitmap);
+
+ if (free_spot && free_spot <= LIST_PREALLOC)
+ {
+ new_cell = list->base + --free_spot;
+ list->avail_bitmap &= ~(1 << free_spot);
+ }
+ else
+ new_cell = (ListCell *) palloc(sizeof(*new_cell));
/* new_cell->data is left undefined! */
new_cell->next = prev_cell->next;
prev_cell->next = new_cell;
*************** lcons_oid(Oid datum, List *list)
*** 307,325 ****
}
/*
! * Concatenate list2 to the end of list1, and return list1. list1 is
! * destructively changed. Callers should be sure to use the return
! * value as the new pointer to the concatenated list: the 'list1'
! * input pointer may or may not be the same as the returned pointer.
*
! * The nodes in list2 are merely appended to the end of list1 in-place
! * (i.e. they aren't copied; the two lists will share some of the same
! * storage). Therefore, invoking list_free() on list2 will also
! * invalidate a portion of list1.
*/
List *
list_concat(List *list1, List *list2)
{
if (list1 == NIL)
return list2;
if (list2 == NIL)
--- 348,369 ----
}
/*
! * Return a list which contains the contents of list1 and list2.
*
! * Callers should be sure to use the return value as the new pointer
! * to the concatenated list, since an empty 'list1' will cause list2
! * to be returned.
! *
! * If the caller ensures that list1 is non-NIL prior to calling list_concat,
! * then they can free the ListCells in list2 using a regular list_free()
! * after the list_concat, but any data pointed to from the ListCells
! * could be referenced now by list1 and shouldn't be free'd.
*/
List *
list_concat(List *list1, List *list2)
{
+ ListCell *cell;
+
if (list1 == NIL)
return list2;
if (list2 == NIL)
*************** list_concat(List *list1, List *list2)
*** 329,337 ****
Assert(list1->type == list2->type);
! list1->length += list2->length;
! list1->tail->next = list2->head;
! list1->tail = list2->tail;
check_list_invariants(list1);
return list1;
--- 373,385 ----
Assert(list1->type == list2->type);
! foreach(cell, list2)
! switch (list1->type) {
! case T_List: list1 = lappend(list1, lfirst(cell)); break;
! case T_IntList: list1 = lappend_int(list1, lfirst_int(cell)); break;
! case T_OidList: list1 = lappend_oid(list1, lfirst_oid(cell)); break;
! default: break; /* shut up compiler */
! }
check_list_invariants(list1);
return list1;
*************** list_truncate(List *list, int new_size)
*** 359,364 ****
--- 407,417 ----
if (new_size >= list_length(list))
return list;
+ /*
+ * NOTE: This may technically leak some pre-alloc'd ListCells,
+ * but running down those that will be would defeat this being
+ * a 'list_truncate' instead of a 'list_delete'.
+ */
n = 1;
foreach(cell, list)
{
*************** list_delete_cell(List *list, ListCell *c
*** 555,561 ****
if (list->tail == cell)
list->tail = prev;
! pfree(cell);
return list;
}
--- 608,619 ----
if (list->tail == cell)
list->tail = prev;
! /* Check if this cell was pre-alloc'd; if so, mark its slot as available */
! if (cell >= list->base && cell <= (list->base + LIST_PREALLOC-1))
! list->avail_bitmap |= 1 << (cell - list->base);
! else
! pfree(cell);
!
return list;
}
*************** list_free_private(List *list, bool deep)
*** 1088,1094 ****
cell = lnext(cell);
if (deep)
pfree(lfirst(tmp));
! pfree(tmp);
}
if (list)
--- 1146,1156 ----
cell = lnext(cell);
if (deep)
pfree(lfirst(tmp));
!
! if (tmp >= list->base && tmp <= (list->base + LIST_PREALLOC-1))
! list->avail_bitmap &= 1 << (tmp - list->base);
! else
! pfree(tmp);
}
if (list)
*************** list_copy(const List *oldlist)
*** 1153,1161 ****
oldlist_cur = oldlist->head->next;
while (oldlist_cur)
{
ListCell *newlist_cur;
! newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
newlist_cur->data = oldlist_cur->data;
newlist_prev->next = newlist_cur;
--- 1215,1231 ----
oldlist_cur = oldlist->head->next;
while (oldlist_cur)
{
+ int free_spot = ffs(newlist->avail_bitmap);
ListCell *newlist_cur;
! if (free_spot && free_spot <= LIST_PREALLOC)
! {
! newlist_cur = newlist->base + --free_spot;
! newlist->avail_bitmap &= ~(1 << free_spot);
! }
! else
! newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
!
newlist_cur->data = oldlist_cur->data;
newlist_prev->next = newlist_cur;
*************** list_copy_tail(const List *oldlist, int
*** 1206,1214 ****
oldlist_cur = oldlist_cur->next;
while (oldlist_cur)
{
ListCell *newlist_cur;
! newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
newlist_cur->data = oldlist_cur->data;
newlist_prev->next = newlist_cur;
--- 1276,1292 ----
oldlist_cur = oldlist_cur->next;
while (oldlist_cur)
{
+ int free_spot = ffs(newlist->avail_bitmap);
ListCell *newlist_cur;
! if (free_spot && free_spot <= LIST_PREALLOC)
! {
! newlist_cur = newlist->base + --free_spot;
! newlist->avail_bitmap &= ~(1 << free_spot);
! }
! else
! newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
!
newlist_cur->data = oldlist_cur->data;
newlist_prev->next = newlist_cur;
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 344ebb7..e24ed8f 100644
*** a/src/backend/optimizer/util/clauses.c
--- b/src/backend/optimizer/util/clauses.c
*************** simplify_or_arguments(List *args,
*** 3323,3329 ****
List *oldhdr = unprocessed_args;
unprocessed_args = list_concat(subargs, unprocessed_args);
! pfree(oldhdr);
}
continue;
}
--- 3323,3329 ----
List *oldhdr = unprocessed_args;
unprocessed_args = list_concat(subargs, unprocessed_args);
! list_free(oldhdr);
}
continue;
}
*************** simplify_and_arguments(List *args,
*** 3425,3431 ****
List *oldhdr = unprocessed_args;
unprocessed_args = list_concat(subargs, unprocessed_args);
! pfree(oldhdr);
}
continue;
}
--- 3425,3431 ----
List *oldhdr = unprocessed_args;
unprocessed_args = list_concat(subargs, unprocessed_args);
! list_free(oldhdr);
}
continue;
}
diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c
index 97ab9d5..82f1923 100644
*** a/src/backend/parser/parse_clause.c
--- b/src/backend/parser/parse_clause.c
*************** transformFromClauseItem(ParseState *psta
*** 769,782 ****
*/
checkNameSpaceConflicts(pstate, l_relnamespace, r_relnamespace);
/*
* Generate combined relation membership info for possible use by
* transformJoinOnClause below.
*/
- my_relnamespace = list_concat(l_relnamespace, r_relnamespace);
- my_containedRels = bms_join(l_containedRels, r_containedRels);
! pfree(r_relnamespace); /* free unneeded list header */
/*
* Extract column name and var lists from both subtrees
--- 769,791 ----
*/
checkNameSpaceConflicts(pstate, l_relnamespace, r_relnamespace);
+ /* Combine the namespaces into a new list */
+ my_relnamespace = list_concat(l_relnamespace, r_relnamespace);
+
+ /*
+ * Free unneeded list pointers
+ *
+ * Verify that l_relnamespace was non-NIL before free'ing
+ */
+ if (!l_relnamespace)
+ list_free(r_relnamespace);
+
/*
* Generate combined relation membership info for possible use by
* transformJoinOnClause below.
*/
! my_containedRels = bms_join(l_containedRels, r_containedRels);
/*
* Extract column name and var lists from both subtrees
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 15b86dd..8b4dc6e 100644
*** a/src/include/nodes/pg_list.h
--- b/src/include/nodes/pg_list.h
***************
*** 39,55 ****
#include "nodes/nodes.h"
typedef struct ListCell ListCell;
- typedef struct List
- {
- NodeTag type; /* T_List, T_IntList, or T_OidList */
- int length;
- ListCell *head;
- ListCell *tail;
- } List;
-
struct ListCell
{
union
--- 39,49 ----
#include "nodes/nodes.h"
+ /* changing this would require changing the used bitmap */
+ #define LIST_PREALLOC 8
typedef struct ListCell ListCell;
struct ListCell
{
union
*************** struct ListCell
*** 61,66 ****
--- 55,72 ----
ListCell *next;
};
+ typedef struct List
+ {
+ NodeTag type; /* T_List, T_IntList, or T_OidList */
+ int length;
+ ListCell *head;
+ ListCell *tail;
+
+ /* pre-allocated ListCells */
+ int avail_bitmap; /* bitmap of available prealloc'd spots */
+ ListCell base[LIST_PREALLOC];
+ } List;
+
/*
* The *only* valid representation of an empty list is NIL; in other
* words, a non-NIL list is guaranteed to have length >= 1 and
signature.asc
Description: Digital signature
