Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita66ee69

Browse files
committed
Embedded list interface
Provide a common implementation of embedded singly-linked anddoubly-linked lists. "Embedded" in the sense that the nodes'next/previous pointers exist within some larger struct; this designchoice reduces memory allocation overhead.Most of the implementation uses inlineable functions (where supported),for performance.Some existing uses of both types of lists have been converted to the newcode, for demonstration purposes. Other uses can (and probably will) beconverted in the future. Since dllist.c is unused after this conversion,it has been removed.Author: Andres FreundSome tweaks by meReviewed by Tom Lane, Peter Geoghegan
1 parentf862a32 commita66ee69

File tree

9 files changed

+1079
-530
lines changed

9 files changed

+1079
-530
lines changed

‎src/backend/lib/Makefile

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,6 @@ subdir = src/backend/lib
1212
top_builddir = ../../..
1313
include$(top_builddir)/src/Makefile.global
1414

15-
OBJS =dllist.o stringinfo.o
15+
OBJS =ilist.o stringinfo.o
1616

1717
include$(top_srcdir)/src/backend/common.mk

‎src/backend/lib/dllist.c

Lines changed: 0 additions & 214 deletions
This file was deleted.

‎src/backend/lib/ilist.c

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
/*-------------------------------------------------------------------------
2+
*
3+
* ilist.c
4+
* support for integrated/inline doubly- and singly- linked lists
5+
*
6+
* Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
7+
* Portions Copyright (c) 1994, Regents of the University of California
8+
*
9+
*
10+
* IDENTIFICATION
11+
* src/backend/lib/ilist.c
12+
*
13+
* NOTES
14+
* This file only contains functions that are too big to be considered
15+
* for inlining. See ilist.h for most of the goodies.
16+
*
17+
*-------------------------------------------------------------------------
18+
*/
19+
#include"postgres.h"
20+
21+
/* See ilist.h */
22+
#defineILIST_INCLUDE_DEFINITIONS
23+
24+
#include"lib/ilist.h"
25+
26+
/*
27+
* removes a node from a list
28+
*
29+
* Attention: O(n)
30+
*/
31+
void
32+
slist_delete(slist_head*head,slist_node*node)
33+
{
34+
slist_node*last=&head->head;
35+
slist_node*cur;
36+
boolfoundPG_USED_FOR_ASSERTS_ONLY= false;
37+
38+
while ((cur=last->next)!=NULL)
39+
{
40+
if (cur==node)
41+
{
42+
last->next=cur->next;
43+
#ifdefUSE_ASSERT_CHECKING
44+
found= true;
45+
#endif
46+
break;
47+
}
48+
last=cur;
49+
}
50+
51+
slist_check(head);
52+
Assert(found);
53+
}
54+
55+
#ifdefILIST_DEBUG
56+
/*
57+
* Verify integrity of a doubly linked list
58+
*/
59+
void
60+
dlist_check(dlist_head*head)
61+
{
62+
dlist_node*cur;
63+
64+
if (head==NULL|| !(&head->head))
65+
elog(ERROR,"doubly linked list head is not properly initialized");
66+
67+
/* iterate in forward direction */
68+
for (cur=head->head.next;cur!=&head->head;cur=cur->next)
69+
{
70+
if (cur==NULL||
71+
cur->next==NULL||
72+
cur->prev==NULL||
73+
cur->prev->next!=cur||
74+
cur->next->prev!=cur)
75+
elog(ERROR,"doubly linked list is corrupted");
76+
}
77+
78+
/* iterate in backward direction */
79+
for (cur=head->head.prev;cur!=&head->head;cur=cur->prev)
80+
{
81+
if (cur==NULL||
82+
cur->next==NULL||
83+
cur->prev==NULL||
84+
cur->prev->next!=cur||
85+
cur->next->prev!=cur)
86+
elog(ERROR,"doubly linked list is corrupted");
87+
}
88+
}
89+
90+
/*
91+
* Verify integrity of a singly linked list
92+
*/
93+
void
94+
slist_check(slist_head*head)
95+
{
96+
slist_node*cur;
97+
98+
if (head==NULL)
99+
elog(ERROR,"singly linked is NULL");
100+
101+
/*
102+
* there isn't much we can test in a singly linked list other that it
103+
* actually ends sometime, i.e. hasn't introduced a cycle or similar
104+
*/
105+
for (cur=head->head.next;cur!=NULL;cur=cur->next)
106+
;
107+
}
108+
109+
#endif/* ILIST_DEBUG */

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp