diff src/backend/lib/Makefile index 2e1061e..7da1c45 *** a/src/backend/lib/Makefile --- b/src/backend/lib/Makefile *************** subdir = src/backend/lib *** 12,17 **** top_builddir = ../../.. include $(top_builddir)/src/Makefile.global ! OBJS = dllist.o stringinfo.o include $(top_srcdir)/src/backend/common.mk --- 12,17 ---- top_builddir = ../../.. include $(top_builddir)/src/Makefile.global ! OBJS = stringinfo.o ilist.o include $(top_srcdir)/src/backend/common.mk diff src/backend/lib/dllist.c new file mode . index 52af56a..e69de29 *** a/src/backend/lib/dllist.c --- b/src/backend/lib/dllist.c *************** *** 1,214 **** - /*------------------------------------------------------------------------- - * - * dllist.c - * this is a simple doubly linked list implementation - * the elements of the lists are void* - * - * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * src/backend/lib/dllist.c - * - *------------------------------------------------------------------------- - */ - #include "postgres.h" - - #include "lib/dllist.h" - - - Dllist * - DLNewList(void) - { - Dllist *l; - - l = (Dllist *) palloc(sizeof(Dllist)); - - l->dll_head = NULL; - l->dll_tail = NULL; - - return l; - } - - void - DLInitList(Dllist *list) - { - list->dll_head = NULL; - list->dll_tail = NULL; - } - - /* - * free up a list and all the nodes in it --- but *not* whatever the nodes - * might point to! - */ - void - DLFreeList(Dllist *list) - { - Dlelem *curr; - - while ((curr = DLRemHead(list)) != NULL) - pfree(curr); - - pfree(list); - } - - Dlelem * - DLNewElem(void *val) - { - Dlelem *e; - - e = (Dlelem *) palloc(sizeof(Dlelem)); - - e->dle_next = NULL; - e->dle_prev = NULL; - e->dle_val = val; - e->dle_list = NULL; - return e; - } - - void - DLInitElem(Dlelem *e, void *val) - { - e->dle_next = NULL; - e->dle_prev = NULL; - e->dle_val = val; - e->dle_list = NULL; - } - - void - DLFreeElem(Dlelem *e) - { - pfree(e); - } - - void - DLRemove(Dlelem *e) - { - Dllist *l = e->dle_list; - - if (e->dle_prev) - e->dle_prev->dle_next = e->dle_next; - else - { - /* must be the head element */ - Assert(e == l->dll_head); - l->dll_head = e->dle_next; - } - if (e->dle_next) - e->dle_next->dle_prev = e->dle_prev; - else - { - /* must be the tail element */ - Assert(e == l->dll_tail); - l->dll_tail = e->dle_prev; - } - - e->dle_next = NULL; - e->dle_prev = NULL; - e->dle_list = NULL; - } - - void - DLAddHead(Dllist *l, Dlelem *e) - { - e->dle_list = l; - - if (l->dll_head) - l->dll_head->dle_prev = e; - e->dle_next = l->dll_head; - e->dle_prev = NULL; - l->dll_head = e; - - if (l->dll_tail == NULL) /* if this is first element added */ - l->dll_tail = e; - } - - void - DLAddTail(Dllist *l, Dlelem *e) - { - e->dle_list = l; - - if (l->dll_tail) - l->dll_tail->dle_next = e; - e->dle_prev = l->dll_tail; - e->dle_next = NULL; - l->dll_tail = e; - - if (l->dll_head == NULL) /* if this is first element added */ - l->dll_head = e; - } - - Dlelem * - DLRemHead(Dllist *l) - { - /* remove and return the head */ - Dlelem *result = l->dll_head; - - if (result == NULL) - return result; - - if (result->dle_next) - result->dle_next->dle_prev = NULL; - - l->dll_head = result->dle_next; - - if (result == l->dll_tail) /* if the head is also the tail */ - l->dll_tail = NULL; - - result->dle_next = NULL; - result->dle_list = NULL; - - return result; - } - - Dlelem * - DLRemTail(Dllist *l) - { - /* remove and return the tail */ - Dlelem *result = l->dll_tail; - - if (result == NULL) - return result; - - if (result->dle_prev) - result->dle_prev->dle_next = NULL; - - l->dll_tail = result->dle_prev; - - if (result == l->dll_head) /* if the tail is also the head */ - l->dll_head = NULL; - - result->dle_prev = NULL; - result->dle_list = NULL; - - return result; - } - - /* Same as DLRemove followed by DLAddHead, but faster */ - void - DLMoveToFront(Dlelem *e) - { - Dllist *l = e->dle_list; - - if (l->dll_head == e) - return; /* Fast path if already at front */ - - Assert(e->dle_prev != NULL); /* since it's not the head */ - e->dle_prev->dle_next = e->dle_next; - - if (e->dle_next) - e->dle_next->dle_prev = e->dle_prev; - else - { - /* must be the tail element */ - Assert(e == l->dll_tail); - l->dll_tail = e->dle_prev; - } - - l->dll_head->dle_prev = e; - e->dle_next = l->dll_head; - e->dle_prev = NULL; - l->dll_head = e; - /* We need not check dll_tail, since there must have been > 1 entry */ - } --- 0 ---- diff src/backend/lib/ilist.c new file mode 100644 index ...de4a27d *** a/src/backend/lib/ilist.c --- b/src/backend/lib/ilist.c *************** *** 0 **** --- 1,117 ---- + /*------------------------------------------------------------------------- + * + * ilist.c + * support for integrated/inline doubly- and singly- linked lists + * + * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * src/backend/lib/ilist.c + * + * NOTES + * This file only contains functions that are too big to be considered + * for inlining. See ilist.h for most of the goodies. + * + *------------------------------------------------------------------------- + */ + #include "postgres.h" + + /* + * If inlines are in use, include the header normally which will get us only + * the function definitions as inlines. But if inlines aren't available, + * include the header with ILIST_DEFINE_FUNCTIONS defined; this makes it pour + * in regular (not inline) function declarations and the corresponding (non + * inline) definitions. + */ + #ifndef USE_INLINE + #define ILIST_DEFINE_FUNCTIONS + #endif + + #include "lib/ilist.h" + + /* + * removes a node from a list + * + * Attention: O(n) + */ + void + slist_delete(slist_head *head, slist_node *node) + { + slist_node *last = &head->head; + slist_node *cur; + bool found PG_USED_FOR_ASSERTS_ONLY = false; + + while ((cur = last->next) != NULL) + { + if (cur == node) + { + last->next = cur->next; + #ifdef USE_ASSERT_CHECKING + found = true; + #endif + break; + } + last = cur; + } + + slist_check(head); + Assert(found); + } + + #ifdef ILIST_DEBUG + /* + * Verify integrity of a doubly linked list + */ + void + dlist_check(dlist_head *head) + { + dlist_node *cur; + + if (head == NULL || !(&head->head)) + elog(ERROR, "doubly linked list head is not properly initialized"); + + /* iterate in forward direction */ + for (cur = head->head.next; cur != &head->head; cur = cur->next) + { + if (cur == NULL || + cur->next == NULL || + cur->prev == NULL || + cur->prev->next != cur || + cur->next->prev != cur) + elog(ERROR, "doubly linked list is corrupted"); + } + + /* iterate in backward direction */ + for (cur = head->head.prev; cur != &head->head; cur = cur->prev) + { + if (cur == NULL || + cur->next == NULL || + cur->prev == NULL || + cur->prev->next != cur || + cur->next->prev != cur) + elog(ERROR, "doubly linked list is corrupted"); + } + } + + /* + * Verify integrity of a singly linked list + */ + void + slist_check(slist_head *head) + { + slist_node *cur; + + if (head == NULL) + elog(ERROR, "singly linked is NULL"); + + /* + * there isn't much we can test in a singly linked list other that it + * actually ends sometime, i.e. hasn't introduced a circle or similar + */ + for (cur = head->head.next; cur != NULL; cur = cur->next) + ; + } + + #endif /* ILIST_DEBUG */ diff src/backend/postmaster/autovacuum.c index 74db821..c3ac219 *** a/src/backend/postmaster/autovacuum.c --- b/src/backend/postmaster/autovacuum.c *************** *** 77,83 **** #include "catalog/pg_database.h" #include "commands/dbcommands.h" #include "commands/vacuum.h" ! #include "lib/dllist.h" #include "libpq/pqsignal.h" #include "miscadmin.h" #include "pgstat.h" --- 77,83 ---- #include "catalog/pg_database.h" #include "commands/dbcommands.h" #include "commands/vacuum.h" ! #include "lib/ilist.h" #include "libpq/pqsignal.h" #include "miscadmin.h" #include "pgstat.h" *************** typedef struct avl_dbase *** 152,157 **** --- 152,158 ---- Oid adl_datid; /* hash key -- must be first */ TimestampTz adl_next_worker; int adl_score; + dlist_node adl_node; } avl_dbase; /* struct to keep track of databases in worker */ *************** typedef struct *** 258,265 **** static AutoVacuumShmemStruct *AutoVacuumShmem; ! /* the database list in the launcher, and the context that contains it */ ! static Dllist *DatabaseList = NULL; static MemoryContext DatabaseListCxt = NULL; /* Pointer to my own WorkerInfo, valid on each worker */ --- 259,269 ---- static AutoVacuumShmemStruct *AutoVacuumShmem; ! /* ! * the database list (of avl_dbase elements) in the launcher, and the context ! * that contains it ! */ ! static dlist_head DatabaseList = DLIST_STATIC_INIT(DatabaseList); static MemoryContext DatabaseListCxt = NULL; /* Pointer to my own WorkerInfo, valid on each worker */ *************** AutoVacLauncherMain(int argc, char *argv *** 508,514 **** /* don't leave dangling pointers to freed memory */ DatabaseListCxt = NULL; ! DatabaseList = NULL; /* * Make sure pgstat also considers our stat data as gone. Note: we --- 512,518 ---- /* don't leave dangling pointers to freed memory */ DatabaseListCxt = NULL; ! dlist_init(&DatabaseList); /* * Make sure pgstat also considers our stat data as gone. Note: we *************** AutoVacLauncherMain(int argc, char *argv *** 576,582 **** struct timeval nap; TimestampTz current_time = 0; bool can_launch; ! Dlelem *elem; int rc; /* --- 580,586 ---- struct timeval nap; TimestampTz current_time = 0; bool can_launch; ! avl_dbase *avdb; int rc; /* *************** AutoVacLauncherMain(int argc, char *argv *** 738,757 **** /* We're OK to start a new worker */ ! elem = DLGetTail(DatabaseList); ! if (elem != NULL) ! { ! avl_dbase *avdb = DLE_VAL(elem); ! ! /* ! * launch a worker if next_worker is right now or it is in the ! * past ! */ ! if (TimestampDifferenceExceeds(avdb->adl_next_worker, ! current_time, 0)) ! launch_worker(current_time); ! } ! else { /* * Special case when the list is empty: start a worker right away. --- 742,748 ---- /* We're OK to start a new worker */ ! if (dlist_is_empty(&DatabaseList)) { /* * Special case when the list is empty: start a worker right away. *************** AutoVacLauncherMain(int argc, char *argv *** 763,768 **** --- 754,776 ---- */ launch_worker(current_time); } + else + { + /* + * because rebuild_database_list constructs a list with most + * distant adl_next_worker first, we obtain our database from the + * tail of the list. + */ + avdb = dlist_tail_element(avl_dbase, adl_node, &DatabaseList); + + /* + * launch a worker if next_worker is right now or it is in the + * past + */ + if (TimestampDifferenceExceeds(avdb->adl_next_worker, + current_time, 0)) + launch_worker(current_time); + } } /* Normal exit from the autovac launcher is here */ *************** AutoVacLauncherMain(int argc, char *argv *** 783,789 **** static void launcher_determine_sleep(bool canlaunch, bool recursing, struct timeval * nap) { ! Dlelem *elem; /* * We sleep until the next scheduled vacuum. We trust that when the --- 791,797 ---- static void launcher_determine_sleep(bool canlaunch, bool recursing, struct timeval * nap) { ! avl_dbase *avdb; /* * We sleep until the next scheduled vacuum. We trust that when the *************** launcher_determine_sleep(bool canlaunch, *** 796,809 **** nap->tv_sec = autovacuum_naptime; nap->tv_usec = 0; } ! else if ((elem = DLGetTail(DatabaseList)) != NULL) { - avl_dbase *avdb = DLE_VAL(elem); TimestampTz current_time = GetCurrentTimestamp(); TimestampTz next_wakeup; long secs; int usecs; next_wakeup = avdb->adl_next_worker; TimestampDifference(current_time, next_wakeup, &secs, &usecs); --- 804,818 ---- nap->tv_sec = autovacuum_naptime; nap->tv_usec = 0; } ! else if (!dlist_is_empty(&DatabaseList)) { TimestampTz current_time = GetCurrentTimestamp(); TimestampTz next_wakeup; long secs; int usecs; + avdb = dlist_tail_element(avl_dbase, adl_node, &DatabaseList); + next_wakeup = avdb->adl_next_worker; TimestampDifference(current_time, next_wakeup, &secs, &usecs); *************** rebuild_database_list(Oid newdb) *** 867,872 **** --- 876,882 ---- int score; int nelems; HTAB *dbhash; + dlist_iter iter; /* use fresh stats */ autovac_refresh_stats(); *************** rebuild_database_list(Oid newdb) *** 927,962 **** } /* Now insert the databases from the existing list */ ! if (DatabaseList != NULL) { ! Dlelem *elem; ! ! elem = DLGetHead(DatabaseList); ! while (elem != NULL) ! { ! avl_dbase *avdb = DLE_VAL(elem); ! avl_dbase *db; ! bool found; ! PgStat_StatDBEntry *entry; ! ! elem = DLGetSucc(elem); ! /* ! * skip databases with no stat entries -- in particular, this gets ! * rid of dropped databases ! */ ! entry = pgstat_fetch_stat_dbentry(avdb->adl_datid); ! if (entry == NULL) ! continue; ! db = hash_search(dbhash, &(avdb->adl_datid), HASH_ENTER, &found); ! if (!found) ! { ! /* hash_search already filled in the key */ ! db->adl_score = score++; ! /* next_worker is filled in later */ ! } } } --- 937,964 ---- } /* Now insert the databases from the existing list */ ! dlist_foreach(iter, &DatabaseList) { ! avl_dbase *avdb = dlist_container(avl_dbase, adl_node, iter.cur); ! avl_dbase *db; ! bool found; ! PgStat_StatDBEntry *entry; ! /* ! * skip databases with no stat entries -- in particular, this gets ! * rid of dropped databases ! */ ! entry = pgstat_fetch_stat_dbentry(avdb->adl_datid); ! if (entry == NULL) ! continue; ! db = hash_search(dbhash, &(avdb->adl_datid), HASH_ENTER, &found); ! if (!found) ! { ! /* hash_search already filled in the key */ ! db->adl_score = score++; ! /* next_worker is filled in later */ } } *************** rebuild_database_list(Oid newdb) *** 987,993 **** /* from here on, the allocated memory belongs to the new list */ MemoryContextSwitchTo(newcxt); ! DatabaseList = DLNewList(); if (nelems > 0) { --- 989,995 ---- /* from here on, the allocated memory belongs to the new list */ MemoryContextSwitchTo(newcxt); ! dlist_init(&DatabaseList); if (nelems > 0) { *************** rebuild_database_list(Oid newdb) *** 1029,1043 **** for (i = 0; i < nelems; i++) { avl_dbase *db = &(dbary[i]); - Dlelem *elem; current_time = TimestampTzPlusMilliseconds(current_time, millis_increment); db->adl_next_worker = current_time; - elem = DLNewElem(db); /* later elements should go closer to the head of the list */ ! DLAddHead(DatabaseList, elem); } } --- 1031,1043 ---- for (i = 0; i < nelems; i++) { avl_dbase *db = &(dbary[i]); current_time = TimestampTzPlusMilliseconds(current_time, millis_increment); db->adl_next_worker = current_time; /* later elements should go closer to the head of the list */ ! dlist_push_head(&DatabaseList, &db->adl_node); } } *************** do_start_worker(void) *** 1147,1153 **** foreach(cell, dblist) { avw_dbase *tmp = lfirst(cell); ! Dlelem *elem; /* Check to see if this one is at risk of wraparound */ if (TransactionIdPrecedes(tmp->adw_frozenxid, xidForceLimit)) --- 1147,1153 ---- foreach(cell, dblist) { avw_dbase *tmp = lfirst(cell); ! dlist_iter iter; /* Check to see if this one is at risk of wraparound */ if (TransactionIdPrecedes(tmp->adw_frozenxid, xidForceLimit)) *************** do_start_worker(void) *** 1179,1189 **** * autovacuum time yet. */ skipit = false; - elem = DatabaseList ? DLGetTail(DatabaseList) : NULL; ! while (elem != NULL) { ! avl_dbase *dbp = DLE_VAL(elem); if (dbp->adl_datid == tmp->adw_datid) { --- 1179,1188 ---- * autovacuum time yet. */ skipit = false; ! dlist_reverse_foreach(iter, &DatabaseList) { ! avl_dbase *dbp = dlist_container(avl_dbase, adl_node, iter.cur); if (dbp->adl_datid == tmp->adw_datid) { *************** do_start_worker(void) *** 1200,1206 **** break; } - elem = DLGetPred(elem); } if (skipit) continue; --- 1199,1204 ---- *************** static void *** 1274,1295 **** launch_worker(TimestampTz now) { Oid dbid; ! Dlelem *elem; dbid = do_start_worker(); if (OidIsValid(dbid)) { /* * Walk the database list and update the corresponding entry. If the * database is not on the list, we'll recreate the list. */ ! elem = (DatabaseList == NULL) ? NULL : DLGetHead(DatabaseList); ! while (elem != NULL) { ! avl_dbase *avdb = DLE_VAL(elem); if (avdb->adl_datid == dbid) { /* * add autovacuum_naptime seconds to the current time, and use * that as the new "next_worker" field for this database. --- 1272,1296 ---- launch_worker(TimestampTz now) { Oid dbid; ! dlist_iter iter; dbid = do_start_worker(); if (OidIsValid(dbid)) { + bool found = false; + /* * Walk the database list and update the corresponding entry. If the * database is not on the list, we'll recreate the list. */ ! dlist_foreach(iter, &DatabaseList) { ! avl_dbase *avdb = dlist_container(avl_dbase, adl_node, iter.cur); if (avdb->adl_datid == dbid) { + found = true; + /* * add autovacuum_naptime seconds to the current time, and use * that as the new "next_worker" field for this database. *************** launch_worker(TimestampTz now) *** 1297,1306 **** avdb->adl_next_worker = TimestampTzPlusMilliseconds(now, autovacuum_naptime * 1000); ! DLMoveToFront(elem); break; } - elem = DLGetSucc(elem); } /* --- 1298,1306 ---- avdb->adl_next_worker = TimestampTzPlusMilliseconds(now, autovacuum_naptime * 1000); ! dlist_move_head(&DatabaseList, iter.cur); break; } } /* *************** launch_worker(TimestampTz now) *** 1310,1316 **** * pgstat entry, but this is not a problem because we don't want to * schedule workers regularly into those in any case. */ ! if (elem == NULL) rebuild_database_list(dbid); } } --- 1310,1316 ---- * pgstat entry, but this is not a problem because we don't want to * schedule workers regularly into those in any case. */ ! if (!found) rebuild_database_list(dbid); } } diff src/backend/postmaster/postmaster.c index dff4c71..7060a1f *** a/src/backend/postmaster/postmaster.c --- b/src/backend/postmaster/postmaster.c *************** *** 95,101 **** #include "access/xlog.h" #include "bootstrap/bootstrap.h" #include "catalog/pg_control.h" ! #include "lib/dllist.h" #include "libpq/auth.h" #include "libpq/ip.h" #include "libpq/libpq.h" --- 95,101 ---- #include "access/xlog.h" #include "bootstrap/bootstrap.h" #include "catalog/pg_control.h" ! #include "lib/ilist.h" #include "libpq/auth.h" #include "libpq/ip.h" #include "libpq/libpq.h" *************** typedef struct bkend *** 146,155 **** int child_slot; /* PMChildSlot for this backend, if any */ bool is_autovacuum; /* is it an autovacuum process? */ bool dead_end; /* is it going to send an error and quit? */ ! Dlelem elem; /* list link in BackendList */ } Backend; ! static Dllist *BackendList; #ifdef EXEC_BACKEND static Backend *ShmemBackendArray; --- 146,155 ---- int child_slot; /* PMChildSlot for this backend, if any */ bool is_autovacuum; /* is it an autovacuum process? */ bool dead_end; /* is it going to send an error and quit? */ ! dlist_node elem; /* list link in BackendList */ } Backend; ! static dlist_head BackendList = DLIST_STATIC_INIT(BackendList); #ifdef EXEC_BACKEND static Backend *ShmemBackendArray; *************** static Backend *ShmemBackendArray; *** 157,164 **** --- 157,166 ---- /* The socket number we are listening for connections on */ int PostPortNumber; + /* The directory names for Unix socket(s) */ char *Unix_socket_directories; + /* The TCP listen address(es) */ char *ListenAddresses; *************** PostmasterMain(int argc, char *argv[]) *** 1028,1038 **** set_stack_base(); /* - * Initialize the list of active backends. - */ - BackendList = DLNewList(); - - /* * Initialize pipe (or process handle on Windows) that allows children to * wake up from sleep on postmaster death. */ --- 1030,1035 ---- *************** processCancelRequest(Port *port, void *p *** 1872,1878 **** Backend *bp; #ifndef EXEC_BACKEND ! Dlelem *curr; #else int i; #endif --- 1869,1875 ---- Backend *bp; #ifndef EXEC_BACKEND ! dlist_iter iter; #else int i; #endif *************** processCancelRequest(Port *port, void *p *** 1886,1894 **** * duplicate array in shared memory. */ #ifndef EXEC_BACKEND ! for (curr = DLGetHead(BackendList); curr; curr = DLGetSucc(curr)) { ! bp = (Backend *) DLE_VAL(curr); #else for (i = MaxLivePostmasterChildren() - 1; i >= 0; i--) { --- 1883,1891 ---- * duplicate array in shared memory. */ #ifndef EXEC_BACKEND ! dlist_foreach(iter, &BackendList) { ! bp = dlist_container(Backend, elem, iter.cur); #else for (i = MaxLivePostmasterChildren() - 1; i >= 0; i--) { *************** static void *** 2648,2654 **** CleanupBackend(int pid, int exitstatus) /* child's exit status. */ { ! Dlelem *curr; LogChildExit(DEBUG2, _("server process"), pid, exitstatus); --- 2645,2651 ---- CleanupBackend(int pid, int exitstatus) /* child's exit status. */ { ! dlist_mutable_iter iter; LogChildExit(DEBUG2, _("server process"), pid, exitstatus); *************** CleanupBackend(int pid, *** 2680,2688 **** return; } ! for (curr = DLGetHead(BackendList); curr; curr = DLGetSucc(curr)) { ! Backend *bp = (Backend *) DLE_VAL(curr); if (bp->pid == pid) { --- 2677,2685 ---- return; } ! dlist_foreach_modify(iter, &BackendList) { ! Backend *bp = dlist_container(Backend, elem, iter.cur); if (bp->pid == pid) { *************** CleanupBackend(int pid, *** 2701,2707 **** ShmemBackendArrayRemove(bp); #endif } ! DLRemove(curr); free(bp); break; } --- 2698,2704 ---- ShmemBackendArrayRemove(bp); #endif } ! dlist_delete(&BackendList, iter.cur); free(bp); break; } *************** CleanupBackend(int pid, *** 2718,2725 **** static void HandleChildCrash(int pid, int exitstatus, const char *procname) { ! Dlelem *curr, ! *next; Backend *bp; /* --- 2715,2721 ---- static void HandleChildCrash(int pid, int exitstatus, const char *procname) { ! dlist_mutable_iter iter; Backend *bp; /* *************** HandleChildCrash(int pid, int exitstatus *** 2734,2743 **** } /* Process regular backends */ ! for (curr = DLGetHead(BackendList); curr; curr = next) { ! next = DLGetSucc(curr); ! bp = (Backend *) DLE_VAL(curr); if (bp->pid == pid) { /* --- 2730,2739 ---- } /* Process regular backends */ ! dlist_foreach_modify(iter, &BackendList) { ! bp = dlist_container(Backend, elem, iter.cur); ! if (bp->pid == pid) { /* *************** HandleChildCrash(int pid, int exitstatus *** 2750,2756 **** ShmemBackendArrayRemove(bp); #endif } ! DLRemove(curr); free(bp); /* Keep looping so we can signal remaining backends */ } --- 2746,2752 ---- ShmemBackendArrayRemove(bp); #endif } ! dlist_delete(&BackendList, iter.cur); free(bp); /* Keep looping so we can signal remaining backends */ } *************** PostmasterStateMachine(void) *** 3113,3119 **** * normal state transition leading up to PM_WAIT_DEAD_END, or during * FatalError processing. */ ! if (DLGetHead(BackendList) == NULL && PgArchPID == 0 && PgStatPID == 0) { /* These other guys should be dead already */ --- 3109,3115 ---- * normal state transition leading up to PM_WAIT_DEAD_END, or during * FatalError processing. */ ! if (dlist_is_empty(&BackendList) && PgArchPID == 0 && PgStatPID == 0) { /* These other guys should be dead already */ *************** signal_child(pid_t pid, int signal) *** 3239,3250 **** static bool SignalSomeChildren(int signal, int target) { ! Dlelem *curr; bool signaled = false; ! for (curr = DLGetHead(BackendList); curr; curr = DLGetSucc(curr)) { ! Backend *bp = (Backend *) DLE_VAL(curr); if (bp->dead_end) continue; --- 3235,3246 ---- static bool SignalSomeChildren(int signal, int target) { ! dlist_iter iter; bool signaled = false; ! dlist_foreach(iter, &BackendList) { ! Backend *bp = dlist_container(Backend, elem, iter.cur); if (bp->dead_end) continue; *************** BackendStartup(Port *port) *** 3382,3389 **** */ bn->pid = pid; bn->is_autovacuum = false; ! DLInitElem(&bn->elem, bn); ! DLAddHead(BackendList, &bn->elem); #ifdef EXEC_BACKEND if (!bn->dead_end) ShmemBackendArrayAdd(bn); --- 3378,3385 ---- */ bn->pid = pid; bn->is_autovacuum = false; ! dlist_push_head(&BackendList, &bn->elem); ! #ifdef EXEC_BACKEND if (!bn->dead_end) ShmemBackendArrayAdd(bn); *************** PostmasterRandom(void) *** 4498,4509 **** static int CountChildren(int target) { ! Dlelem *curr; int cnt = 0; ! for (curr = DLGetHead(BackendList); curr; curr = DLGetSucc(curr)) { ! Backend *bp = (Backend *) DLE_VAL(curr); if (bp->dead_end) continue; --- 4494,4505 ---- static int CountChildren(int target) { ! dlist_iter iter; int cnt = 0; ! dlist_foreach(iter, &BackendList) { ! Backend *bp = dlist_container(Backend, elem, iter.cur); if (bp->dead_end) continue; *************** StartAutovacuumWorker(void) *** 4682,4689 **** if (bn->pid > 0) { bn->is_autovacuum = true; ! DLInitElem(&bn->elem, bn); ! DLAddHead(BackendList, &bn->elem); #ifdef EXEC_BACKEND ShmemBackendArrayAdd(bn); #endif --- 4678,4684 ---- if (bn->pid > 0) { bn->is_autovacuum = true; ! dlist_push_head(&BackendList, &bn->elem); #ifdef EXEC_BACKEND ShmemBackendArrayAdd(bn); #endif diff src/backend/utils/cache/catcache.c index d6f6b1c..230ddf4 *** a/src/backend/utils/cache/catcache.c --- b/src/backend/utils/cache/catcache.c *************** CatalogCacheComputeTupleHashValue(CatCac *** 291,297 **** static void CatCachePrintStats(int code, Datum arg) { ! CatCache *cache; long cc_searches = 0; long cc_hits = 0; long cc_neg_hits = 0; --- 291,297 ---- static void CatCachePrintStats(int code, Datum arg) { ! slist_iter iter; long cc_searches = 0; long cc_hits = 0; long cc_neg_hits = 0; *************** CatCachePrintStats(int code, Datum arg) *** 300,307 **** long cc_lsearches = 0; long cc_lhits = 0; ! for (cache = CacheHdr->ch_caches; cache; cache = cache->cc_next) { if (cache->cc_ntup == 0 && cache->cc_searches == 0) continue; /* don't print unused caches */ elog(DEBUG2, "catcache %s/%u: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%ld loads, %ld invals, %ld lsrch, %ld lhits", --- 300,309 ---- long cc_lsearches = 0; long cc_lhits = 0; ! slist_foreach(iter, &CacheHdr->ch_caches) { + CatCache *cache = slist_container(CatCache, cc_next, iter.cur); + if (cache->cc_ntup == 0 && cache->cc_searches == 0) continue; /* don't print unused caches */ elog(DEBUG2, "catcache %s/%u: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%ld loads, %ld invals, %ld lsrch, %ld lhits", *************** CatCacheRemoveCTup(CatCache *cache, CatC *** 368,375 **** return; /* nothing left to do */ } ! /* delink from linked list */ ! DLRemove(&ct->cache_elem); /* free associated tuple data */ if (ct->tuple.t_data != NULL) --- 370,376 ---- return; /* nothing left to do */ } ! dlist_delete(ct->cache_bucket, &ct->cache_elem); /* free associated tuple data */ if (ct->tuple.t_data != NULL) *************** CatCacheRemoveCList(CatCache *cache, Cat *** 412,418 **** } /* delink from linked list */ ! DLRemove(&cl->cache_elem); /* free associated tuple data */ if (cl->tuple.t_data != NULL) --- 413,419 ---- } /* delink from linked list */ ! dlist_delete(&cache->cc_lists, &cl->cache_elem); /* free associated tuple data */ if (cl->tuple.t_data != NULL) *************** CatCacheRemoveCList(CatCache *cache, Cat *** 442,459 **** void CatalogCacheIdInvalidate(int cacheId, uint32 hashValue) { ! CatCache *ccp; CACHE1_elog(DEBUG2, "CatalogCacheIdInvalidate: called"); /* * inspect caches to find the proper cache */ ! for (ccp = CacheHdr->ch_caches; ccp; ccp = ccp->cc_next) { Index hashIndex; ! Dlelem *elt, ! *nextelt; if (cacheId != ccp->id) continue; --- 443,460 ---- void CatalogCacheIdInvalidate(int cacheId, uint32 hashValue) { ! slist_iter cache_iter; CACHE1_elog(DEBUG2, "CatalogCacheIdInvalidate: called"); /* * inspect caches to find the proper cache */ ! slist_foreach(cache_iter, &CacheHdr->ch_caches) { Index hashIndex; ! dlist_mutable_iter iter; ! CatCache *ccp = slist_container(CatCache, cc_next, cache_iter.cur); if (cacheId != ccp->id) continue; *************** CatalogCacheIdInvalidate(int cacheId, ui *** 468,478 **** * Invalidate *all* CatCLists in this cache; it's too hard to tell * which searches might still be correct, so just zap 'em all. */ ! for (elt = DLGetHead(&ccp->cc_lists); elt; elt = nextelt) { ! CatCList *cl = (CatCList *) DLE_VAL(elt); ! ! nextelt = DLGetSucc(elt); if (cl->refcount > 0) cl->dead = true; --- 469,477 ---- * Invalidate *all* CatCLists in this cache; it's too hard to tell * which searches might still be correct, so just zap 'em all. */ ! dlist_foreach_modify(iter, &ccp->cc_lists) { ! CatCList *cl = dlist_container(CatCList, cache_elem, iter.cur); if (cl->refcount > 0) cl->dead = true; *************** CatalogCacheIdInvalidate(int cacheId, ui *** 484,495 **** * inspect the proper hash bucket for tuple matches */ hashIndex = HASH_INDEX(hashValue, ccp->cc_nbuckets); ! ! for (elt = DLGetHead(&ccp->cc_bucket[hashIndex]); elt; elt = nextelt) { ! CatCTup *ct = (CatCTup *) DLE_VAL(elt); ! ! nextelt = DLGetSucc(elt); if (hashValue == ct->hash_value) { --- 483,491 ---- * inspect the proper hash bucket for tuple matches */ hashIndex = HASH_INDEX(hashValue, ccp->cc_nbuckets); ! dlist_foreach_modify(iter, &ccp->cc_bucket[hashIndex]) { ! CatCTup *ct = dlist_container(CatCTup, cache_elem, iter.cur); if (hashValue == ct->hash_value) { *************** AtEOXact_CatCache(bool isCommit) *** 557,573 **** #ifdef USE_ASSERT_CHECKING if (assert_enabled) { ! CatCache *ccp; ! for (ccp = CacheHdr->ch_caches; ccp; ccp = ccp->cc_next) { ! Dlelem *elt; int i; /* Check CatCLists */ ! for (elt = DLGetHead(&ccp->cc_lists); elt; elt = DLGetSucc(elt)) { ! CatCList *cl = (CatCList *) DLE_VAL(elt); Assert(cl->cl_magic == CL_MAGIC); Assert(cl->refcount == 0); --- 553,570 ---- #ifdef USE_ASSERT_CHECKING if (assert_enabled) { ! slist_iter cache_iter; ! slist_foreach(cache_iter, &(CacheHdr->ch_caches)) { ! CatCache *ccp = slist_container(CatCache, cc_next, cache_iter.cur); ! dlist_iter iter; int i; /* Check CatCLists */ ! dlist_foreach(iter, &ccp->cc_lists) { ! CatCList *cl = dlist_container(CatCList, cache_elem, iter.cur); Assert(cl->cl_magic == CL_MAGIC); Assert(cl->refcount == 0); *************** AtEOXact_CatCache(bool isCommit) *** 577,587 **** /* Check individual tuples */ for (i = 0; i < ccp->cc_nbuckets; i++) { ! for (elt = DLGetHead(&ccp->cc_bucket[i]); ! elt; ! elt = DLGetSucc(elt)) { ! CatCTup *ct = (CatCTup *) DLE_VAL(elt); Assert(ct->ct_magic == CT_MAGIC); Assert(ct->refcount == 0); --- 574,584 ---- /* Check individual tuples */ for (i = 0; i < ccp->cc_nbuckets; i++) { ! dlist_head *bucket = &ccp->cc_bucket[i]; ! ! dlist_foreach(iter, bucket) { ! CatCTup *ct = dlist_container(CatCTup, cache_elem, iter.cur); Assert(ct->ct_magic == CT_MAGIC); Assert(ct->refcount == 0); *************** AtEOXact_CatCache(bool isCommit) *** 604,619 **** static void ResetCatalogCache(CatCache *cache) { ! Dlelem *elt, ! *nextelt; int i; /* Remove each list in this cache, or at least mark it dead */ ! for (elt = DLGetHead(&cache->cc_lists); elt; elt = nextelt) { ! CatCList *cl = (CatCList *) DLE_VAL(elt); ! ! nextelt = DLGetSucc(elt); if (cl->refcount > 0) cl->dead = true; --- 601,613 ---- static void ResetCatalogCache(CatCache *cache) { ! dlist_mutable_iter iter; int i; /* Remove each list in this cache, or at least mark it dead */ ! dlist_foreach_modify(iter, &cache->cc_lists) { ! CatCList *cl = dlist_container(CatCList, cache_elem, iter.cur); if (cl->refcount > 0) cl->dead = true; *************** ResetCatalogCache(CatCache *cache) *** 624,634 **** /* Remove each tuple in this cache, or at least mark it dead */ for (i = 0; i < cache->cc_nbuckets; i++) { ! for (elt = DLGetHead(&cache->cc_bucket[i]); elt; elt = nextelt) ! { ! CatCTup *ct = (CatCTup *) DLE_VAL(elt); ! nextelt = DLGetSucc(elt); if (ct->refcount > 0 || (ct->c_list && ct->c_list->refcount > 0)) --- 618,628 ---- /* Remove each tuple in this cache, or at least mark it dead */ for (i = 0; i < cache->cc_nbuckets; i++) { ! dlist_head *bucket = &cache->cc_bucket[i]; ! dlist_foreach_modify(iter, bucket) ! { ! CatCTup *ct = dlist_container(CatCTup, cache_elem, iter.cur); if (ct->refcount > 0 || (ct->c_list && ct->c_list->refcount > 0)) *************** ResetCatalogCache(CatCache *cache) *** 654,665 **** void ResetCatalogCaches(void) { ! CatCache *cache; CACHE1_elog(DEBUG2, "ResetCatalogCaches called"); ! for (cache = CacheHdr->ch_caches; cache; cache = cache->cc_next) ResetCatalogCache(cache); CACHE1_elog(DEBUG2, "end of ResetCatalogCaches call"); } --- 648,663 ---- void ResetCatalogCaches(void) { ! slist_iter iter; CACHE1_elog(DEBUG2, "ResetCatalogCaches called"); ! slist_foreach(iter, &CacheHdr->ch_caches) ! { ! CatCache *cache = slist_container(CatCache, cc_next, iter.cur); ! ResetCatalogCache(cache); + } CACHE1_elog(DEBUG2, "end of ResetCatalogCaches call"); } *************** ResetCatalogCaches(void) *** 680,691 **** void CatalogCacheFlushCatalog(Oid catId) { ! CatCache *cache; CACHE2_elog(DEBUG2, "CatalogCacheFlushCatalog called for %u", catId); ! for (cache = CacheHdr->ch_caches; cache; cache = cache->cc_next) { /* Does this cache store tuples of the target catalog? */ if (cache->cc_reloid == catId) { --- 678,691 ---- void CatalogCacheFlushCatalog(Oid catId) { ! slist_iter iter; CACHE2_elog(DEBUG2, "CatalogCacheFlushCatalog called for %u", catId); ! slist_foreach(iter, &(CacheHdr->ch_caches)) { + CatCache *cache = slist_container(CatCache, cc_next, iter.cur); + /* Does this cache store tuples of the target catalog? */ if (cache->cc_reloid == catId) { *************** InitCatCache(int id, *** 760,766 **** if (CacheHdr == NULL) { CacheHdr = (CatCacheHeader *) palloc(sizeof(CatCacheHeader)); ! CacheHdr->ch_caches = NULL; CacheHdr->ch_ntup = 0; #ifdef CATCACHE_STATS /* set up to dump stats at backend exit */ --- 760,766 ---- if (CacheHdr == NULL) { CacheHdr = (CatCacheHeader *) palloc(sizeof(CatCacheHeader)); ! slist_init(&CacheHdr->ch_caches); CacheHdr->ch_ntup = 0; #ifdef CATCACHE_STATS /* set up to dump stats at backend exit */ *************** InitCatCache(int id, *** 770,779 **** /* * allocate a new cache structure - * - * Note: we assume zeroing initializes the Dllist headers correctly */ ! cp = (CatCache *) palloc0(sizeof(CatCache) + nbuckets * sizeof(Dllist)); /* * initialize the cache's relation information for the relation --- 770,777 ---- /* * allocate a new cache structure */ ! cp = (CatCache *) palloc0(sizeof(CatCache) + nbuckets * sizeof(dlist_node)); /* * initialize the cache's relation information for the relation *************** InitCatCache(int id, *** 792,797 **** --- 790,800 ---- for (i = 0; i < nkeys; ++i) cp->cc_key[i] = key[i]; + dlist_init(&cp->cc_lists); + + for (i = 0; i < nbuckets; i++) + dlist_init(&cp->cc_bucket[i]); + /* * new cache is initialized as far as we can go for now. print some * debugging information, if appropriate. *************** InitCatCache(int id, *** 801,808 **** /* * add completed cache to top of group header's list */ ! cp->cc_next = CacheHdr->ch_caches; ! CacheHdr->ch_caches = cp; /* * back to the old context before we return... --- 804,810 ---- /* * add completed cache to top of group header's list */ ! slist_push_head(&CacheHdr->ch_caches, &cp->cc_next); /* * back to the old context before we return... *************** SearchCatCache(CatCache *cache, *** 1060,1066 **** ScanKeyData cur_skey[CATCACHE_MAXKEYS]; uint32 hashValue; Index hashIndex; ! Dlelem *elt; CatCTup *ct; Relation relation; SysScanDesc scandesc; --- 1062,1069 ---- ScanKeyData cur_skey[CATCACHE_MAXKEYS]; uint32 hashValue; Index hashIndex; ! dlist_mutable_iter iter; ! dlist_head *bucket; CatCTup *ct; Relation relation; SysScanDesc scandesc; *************** SearchCatCache(CatCache *cache, *** 1094,1106 **** /* * scan the hash bucket until we find a match or exhaust our tuples */ ! for (elt = DLGetHead(&cache->cc_bucket[hashIndex]); ! elt; ! elt = DLGetSucc(elt)) { bool res; ! ct = (CatCTup *) DLE_VAL(elt); if (ct->dead) continue; /* ignore dead entries */ --- 1097,1109 ---- /* * scan the hash bucket until we find a match or exhaust our tuples */ ! bucket = &cache->cc_bucket[hashIndex]; ! ! dlist_foreach_modify(iter, bucket) { bool res; ! ct = dlist_container(CatCTup, cache_elem, iter.cur); if (ct->dead) continue; /* ignore dead entries */ *************** SearchCatCache(CatCache *cache, *** 1125,1131 **** * most frequently accessed elements in any hashbucket will tend to be * near the front of the hashbucket's list.) */ ! DLMoveToFront(&ct->cache_elem); /* * If it's a positive entry, bump its refcount and return it. If it's --- 1128,1134 ---- * most frequently accessed elements in any hashbucket will tend to be * near the front of the hashbucket's list.) */ ! dlist_move_head(bucket, &ct->cache_elem); /* * If it's a positive entry, bump its refcount and return it. If it's *************** SearchCatCacheList(CatCache *cache, *** 1340,1346 **** { ScanKeyData cur_skey[CATCACHE_MAXKEYS]; uint32 lHashValue; ! Dlelem *elt; CatCList *cl; CatCTup *ct; List *volatile ctlist; --- 1343,1349 ---- { ScanKeyData cur_skey[CATCACHE_MAXKEYS]; uint32 lHashValue; ! dlist_iter iter; CatCList *cl; CatCTup *ct; List *volatile ctlist; *************** SearchCatCacheList(CatCache *cache, *** 1382,1394 **** /* * scan the items until we find a match or exhaust our list */ ! for (elt = DLGetHead(&cache->cc_lists); ! elt; ! elt = DLGetSucc(elt)) { bool res; ! cl = (CatCList *) DLE_VAL(elt); if (cl->dead) continue; /* ignore dead entries */ --- 1385,1395 ---- /* * scan the items until we find a match or exhaust our list */ ! dlist_foreach(iter, &cache->cc_lists) { bool res; ! cl = dlist_container(CatCList, cache_elem, iter.cur); if (cl->dead) continue; /* ignore dead entries */ *************** SearchCatCacheList(CatCache *cache, *** 1416,1422 **** * since there's no point in that unless they are searched for * individually.) */ ! DLMoveToFront(&cl->cache_elem); /* Bump the list's refcount and return it */ ResourceOwnerEnlargeCatCacheListRefs(CurrentResourceOwner); --- 1417,1423 ---- * since there's no point in that unless they are searched for * individually.) */ ! dlist_move_head(&cache->cc_lists, &cl->cache_elem); /* Bump the list's refcount and return it */ ResourceOwnerEnlargeCatCacheListRefs(CurrentResourceOwner); *************** SearchCatCacheList(CatCache *cache, *** 1468,1473 **** --- 1469,1476 ---- { uint32 hashValue; Index hashIndex; + bool found = false; + dlist_head *bucket; /* * See if there's an entry for this tuple already. *************** SearchCatCacheList(CatCache *cache, *** 1476,1486 **** hashValue = CatalogCacheComputeTupleHashValue(cache, ntp); hashIndex = HASH_INDEX(hashValue, cache->cc_nbuckets); ! for (elt = DLGetHead(&cache->cc_bucket[hashIndex]); ! elt; ! elt = DLGetSucc(elt)) { ! ct = (CatCTup *) DLE_VAL(elt); if (ct->dead || ct->negative) continue; /* ignore dead and negative entries */ --- 1479,1488 ---- hashValue = CatalogCacheComputeTupleHashValue(cache, ntp); hashIndex = HASH_INDEX(hashValue, cache->cc_nbuckets); ! bucket = &cache->cc_bucket[hashIndex]; ! dlist_foreach(iter, bucket) { ! ct = dlist_container(CatCTup, cache_elem, iter.cur); if (ct->dead || ct->negative) continue; /* ignore dead and negative entries */ *************** SearchCatCacheList(CatCache *cache, *** 1498,1507 **** if (ct->c_list) continue; break; /* A-OK */ } ! if (elt == NULL) { /* We didn't find a usable entry, so make a new one */ ct = CatalogCacheCreateEntry(cache, ntp, --- 1500,1510 ---- if (ct->c_list) continue; + found = true; break; /* A-OK */ } ! if (!found) { /* We didn't find a usable entry, so make a new one */ ct = CatalogCacheCreateEntry(cache, ntp, *************** SearchCatCacheList(CatCache *cache, *** 1564,1570 **** cl->cl_magic = CL_MAGIC; cl->my_cache = cache; - DLInitElem(&cl->cache_elem, cl); cl->refcount = 0; /* for the moment */ cl->dead = false; cl->ordered = ordered; --- 1567,1572 ---- *************** SearchCatCacheList(CatCache *cache, *** 1587,1593 **** } Assert(i == nmembers); ! DLAddHead(&cache->cc_lists, &cl->cache_elem); /* Finally, bump the list's refcount and return it */ cl->refcount++; --- 1589,1595 ---- } Assert(i == nmembers); ! dlist_push_head(&cache->cc_lists, &cl->cache_elem); /* Finally, bump the list's refcount and return it */ cl->refcount++; *************** CatalogCacheCreateEntry(CatCache *cache, *** 1664,1677 **** */ ct->ct_magic = CT_MAGIC; ct->my_cache = cache; ! DLInitElem(&ct->cache_elem, (void *) ct); ct->c_list = NULL; ct->refcount = 0; /* for the moment */ ct->dead = false; ct->negative = negative; ct->hash_value = hashValue; ! DLAddHead(&cache->cc_bucket[hashIndex], &ct->cache_elem); cache->cc_ntup++; CacheHdr->ch_ntup++; --- 1666,1680 ---- */ ct->ct_magic = CT_MAGIC; ct->my_cache = cache; ! ct->cache_bucket = &cache->cc_bucket[hashIndex]; ! ct->c_list = NULL; ct->refcount = 0; /* for the moment */ ct->dead = false; ct->negative = negative; ct->hash_value = hashValue; ! dlist_push_head(ct->cache_bucket, &ct->cache_elem); cache->cc_ntup++; CacheHdr->ch_ntup++; *************** PrepareToInvalidateCacheTuple(Relation r *** 1785,1791 **** HeapTuple newtuple, void (*function) (int, uint32, Oid)) { ! CatCache *ccp; Oid reloid; CACHE1_elog(DEBUG2, "PrepareToInvalidateCacheTuple: called"); --- 1788,1794 ---- HeapTuple newtuple, void (*function) (int, uint32, Oid)) { ! slist_iter iter; Oid reloid; CACHE1_elog(DEBUG2, "PrepareToInvalidateCacheTuple: called"); *************** PrepareToInvalidateCacheTuple(Relation r *** 1808,1817 **** * ---------------- */ ! for (ccp = CacheHdr->ch_caches; ccp; ccp = ccp->cc_next) { uint32 hashvalue; Oid dbid; if (ccp->cc_reloid != reloid) continue; --- 1811,1821 ---- * ---------------- */ ! slist_foreach(iter, &(CacheHdr->ch_caches)) { uint32 hashvalue; Oid dbid; + CatCache *ccp = slist_container(CatCache, cc_next, iter.cur); if (ccp->cc_reloid != reloid) continue; diff src/include/lib/dllist.h new file mode . index 25ed64c..e69de29 *** a/src/include/lib/dllist.h --- b/src/include/lib/dllist.h *************** *** 1,85 **** - /*------------------------------------------------------------------------- - * - * dllist.h - * simple doubly linked list primitives - * the elements of the list are void* so the lists can contain anything - * Dlelem can only be in one list at a time - * - * - * Here's a small example of how to use Dllists: - * - * Dllist *lst; - * Dlelem *elt; - * void *in_stuff; -- stuff to stick in the list - * void *out_stuff - * - * lst = DLNewList(); -- make a new dllist - * DLAddHead(lst, DLNewElem(in_stuff)); -- add a new element to the list - * with in_stuff as the value - * ... - * elt = DLGetHead(lst); -- retrieve the head element - * out_stuff = (void*)DLE_VAL(elt); -- get the stuff out - * DLRemove(elt); -- removes the element from its list - * DLFreeElem(elt); -- free the element since we don't - * use it anymore - * - * - * It is also possible to use Dllist objects that are embedded in larger - * structures instead of being separately malloc'd. To do this, use - * DLInitElem() to initialize a Dllist field within a larger object. - * Don't forget to DLRemove() each field from its list (if any) before - * freeing the larger object! - * - * - * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * src/include/lib/dllist.h - * - *------------------------------------------------------------------------- - */ - - #ifndef DLLIST_H - #define DLLIST_H - - struct Dllist; - struct Dlelem; - - typedef struct Dlelem - { - struct Dlelem *dle_next; /* next element */ - struct Dlelem *dle_prev; /* previous element */ - void *dle_val; /* value of the element */ - struct Dllist *dle_list; /* what list this element is in */ - } Dlelem; - - typedef struct Dllist - { - Dlelem *dll_head; - Dlelem *dll_tail; - } Dllist; - - extern Dllist *DLNewList(void); /* allocate and initialize a list header */ - extern void DLInitList(Dllist *list); /* init a header alloced by caller */ - extern void DLFreeList(Dllist *list); /* free up a list and all the nodes in - * it */ - extern Dlelem *DLNewElem(void *val); - extern void DLInitElem(Dlelem *e, void *val); - extern void DLFreeElem(Dlelem *e); - extern void DLRemove(Dlelem *e); /* removes node from list */ - extern void DLAddHead(Dllist *list, Dlelem *node); - extern void DLAddTail(Dllist *list, Dlelem *node); - 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 */ - - /* These are macros for speed */ - #define DLGetHead(list) ((list)->dll_head) - #define DLGetTail(list) ((list)->dll_tail) - #define DLGetSucc(elem) ((elem)->dle_next) - #define DLGetPred(elem) ((elem)->dle_prev) - #define DLGetListHdr(elem) ((elem)->dle_list) - - #define DLE_VAL(elem) ((elem)->dle_val) - - #endif /* DLLIST_H */ --- 0 ---- diff src/include/lib/ilist.h new file mode 100644 index ...9bc97dc *** a/src/include/lib/ilist.h --- b/src/include/lib/ilist.h *************** *** 0 **** --- 1,760 ---- + /*------------------------------------------------------------------------- + * + * ilist.h + * integrated/inline doubly- and singly-linked lists + * + * This implementation is as efficient as possible: the lists don't have + * any memory management overhead, because the list pointers are embedded + * within some larger structure. + + * Also, the circular lists are always circularly linked, even when empty; this + * enables many manipulations to be done without branches, which is beneficial + * performance-wise. + * + * NOTES: + * + * This is intended to be used in situations where memory for a struct and its + * contents already needs to be allocated and the overhead of allocating extra + * list cells for every list element is noticeable. The API for singly/doubly + * linked lists is identical as far as capabilities of both allow. + * + * // A oversimplified example demonstrating how this can be used: + * + * #include "lib/ilist.h" + * + * // Lets assume we want to store information about the tables contained in a + * // database. + * + * // Define struct for the databases including a list header that will be used + * // to access the nodes in the list later on. + * typedef struct my_database + * { + * char* datname; + * dlist_head tables; + * ... + * } my_database; + * + * // Define struct for the tables. Note the list_node element which stores + * // information about prev/next list nodes. + * typedef struct my_table + * { + * char* tablename; + * dlist_node list_node; + * perm_t permissions; + * ... + * } value_in_a_list; + * + * // create a database + * my_database *db = create_database(); + * + * // and a few tables + * dlist_push_head(&db->tables, &create_table(db, "a")->list_node); + * ... + * dlist_push_head(&db->tables, &create_table(db, "b")->list_node); + * ... + * ... + * // to iterate over the table we allocate an iterator element to store + * // information about the current position + * dlist_iter iter; + * + * dlist_foreach (iter, &db->tables) + * { + * // inside an *_foreach the iterator's .cur field can be used to access + * // the current element + * // iter.cur points to a 'dlist_node', but we want the actual table + * // information, use dlist_container to convert + * my_table *tbl = dlist_container(my_table, list_node, iter->cur); + * elog(NOTICE, 'we have a table: %s in database %s', + * val->tablename, db->datname); + * } + * + * // while a simple iteration is useful we sometimes also want to manipulate + * // the list while iterating. Say, we want to delete all tables! + * + * // declare an iterator that allows some list manipulations + * dlist_mutable_iter miter; + * + * // iterate + * dlist_foreach_modify(miter, &db->tables) + * { + * my_table *tbl = dlist_container(my_table, list_node, iter->cur); + * // unlink the current table from the linked list + * dlist_delete(&db->tables, iter->cur); + * // as ilists never manage memory, we can freely access the table + * drop_table(db, tbl); + * } + * + * // Note that none of the dlist_* functions did do any memory + * // management. They just manipulated externally managed memory. + * + * + * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/include/lib/ilist.h + *------------------------------------------------------------------------- + */ + #ifndef ILIST_H + #define ILIST_H + + /* + * enable for extra debugging. This is rather expensive, so it's not enabled by + * default even with --enable-cassert. + */ + /* #define ILIST_DEBUG */ + + /* + * Node of a doubly linked list. + * + * Embed this in structs that need to be part of a doubly linked list. + */ + typedef struct dlist_node dlist_node; + struct dlist_node + { + dlist_node *prev; + dlist_node *next; + }; + + /* + * Head of a doubly linked list. + * + * Lists are internally *always* circularly linked, even when empty. Circular + * lists have the advantage of not needing any branches in the most common list + * manipulations. + */ + typedef struct dlist_head + { + /* + * head->next either points to the first element of the list or to &head + * if empty. + * + * head->prev either points to the last element of the list or to &head if + * empty. + */ + dlist_node head; + } dlist_head; + + + /* + * Doubly linked list iterator. + * + * Used as state in dlist_foreach() and dlist_reverse_foreach(). To get the + * current element of the iteration use the 'cur' member. + * + * Iterations using this are *not* allowed to change the list while iterating! + * + * NB: We use an extra type for this to make it possible to avoid multiple + * evaluations of arguments in the dlist_foreach() macro. + */ + typedef struct dlist_iter + { + dlist_node *end; /* last node we iterate to */ + dlist_node *cur; /* current element */ + } dlist_iter; + + /* + * Doubly linked list iterator allowing some modifications while iterating + * + * Used as state in dlist_foreach_modify(). To get the current element of the + * iteration use the 'cur' member. + * + * Iterations using this are only allowed to change the list *at the current + * point of iteration*. It is fine to delete the current node, but it is *not* + * fine to modify other nodes. + * + * NB: We need a separate type for mutable iterations to avoid having to pass + * in two iterators or some other state variable as we need to store the + * '->next' node of the current node so it can be deleted or modified by the + * user. + */ + typedef struct dlist_mutable_iter + { + dlist_node *end; /* last node we iterate to */ + dlist_node *cur; /* current element */ + dlist_node *next; /* next node we iterate to, so we can delete + * cur */ + } dlist_mutable_iter; + + /* + * Node of a singly linked list. + * + * Embed this in structs that need to be part of a singly linked list. + */ + typedef struct slist_node slist_node; + struct slist_node + { + slist_node *next; + }; + + /* + * Head of a singly linked list. + * + * Singly linked lists are *not* circularly linked (how could they be?) in + * contrast to the doubly linked lists. As no pointer to the last list element + * and to the previous node needs to be maintained this doesn't incur any + * additional branches in the usual manipulations. + */ + typedef struct slist_head + { + slist_node head; + } slist_head; + + /* + * Singly linked list iterator + * + * Used in slist_foreach(). To get the current element of the iteration use the + * 'cur' member. + * + * Do *not* manipulate the list while iterating! + * + * NB: this wouldn't really need to be an extra struct, we could use a + * slist_node * directly. For consistency reasons with dlist_*iter and + * slist_mutable_iter we still use a separate type. + */ + typedef struct slist_iter + { + slist_node *cur; + } slist_iter; + + /* + * Singly linked list iterator allowing some modifications while iterating + * + * Used in slist_foreach_modify. + * + * Iterations using this are allowed to remove the current node and to add more + * nodes to the beginning of the list. + */ + typedef struct slist_mutable_iter + { + slist_node *cur; + slist_node *next; + } slist_mutable_iter; + + + /* + * We take quite some pain to allow this 'module' to be used on compilers + * without usable 'static inline' support. If configure detects its not + * available all the inline functions will be defined in ilist.c instead by + * #define'ing ILIST_USE_DEFINITION there. + */ + #ifdef USE_INLINE + #define INLINE_IF_POSSIBLE static inline + #else + /* hide inline declarations from compiler */ + #define INLINE_IF_POSSIBLE + + /* Prototypes for functions we want to be inlined if possible */ + extern void dlist_init(dlist_head *head); + extern bool dlist_is_empty(dlist_head *head); + extern void dlist_push_head(dlist_head *head, dlist_node *node); + extern void dlist_push_tail(dlist_head *head, dlist_node *node); + extern void dlist_insert_after(dlist_head *head, + dlist_node *after, dlist_node *node); + extern void dlist_insert_before(dlist_head *head, + dlist_node *before, dlist_node *node); + extern void dlist_delete(dlist_head *head, dlist_node *node); + extern dlist_node *dlist_pop_head_node(dlist_head *head); + extern void dlist_move_head(dlist_head *head, dlist_node *node); + extern bool dlist_has_next(dlist_head *head, dlist_node *node); + extern bool dlist_has_prev(dlist_head *head, dlist_node *node); + extern dlist_node *dlist_next_node(dlist_head *head, dlist_node *node); + extern dlist_node *dlist_prev_node(dlist_head *head, dlist_node *node); + extern dlist_node *dlist_head_node(dlist_head *head); + extern dlist_node *dlist_tail_node(dlist_head *head); + + /* dlist macro support functions */ + extern void *dlist_tail_element_off(dlist_head *head, size_t off); + extern void *dlist_head_element_off(dlist_head *head, size_t off); + + extern void slist_init(slist_head *head); + extern bool slist_is_empty(slist_head *head); + extern slist_node *slist_head_node(slist_head *head); + extern void slist_push_head(slist_head *head, slist_node *node); + extern slist_node *slist_pop_head_node(slist_head *head); + extern void slist_insert_after(slist_head *head, + slist_node *after, slist_node *node); + extern bool slist_has_next(slist_head *head, slist_node *node); + extern slist_node *slist_next_node(slist_head *head, slist_node *node); + + /* slist macro support function */ + extern void *slist_head_element_off(slist_head *head, size_t off); + #endif /* !USE_INLINE */ + + /* These functions are too big to be inline, so they are in the C file always */ + + /* Attention: O(n) */ + extern void slist_delete(slist_head *head, slist_node *node); + + #ifdef ILIST_DEBUG + extern void dlist_check(dlist_head *head); + extern void slist_check(slist_head *head); + #else + /* + * These seemingly useless casts to void are here to keep the compiler quiet + * about the argument being unused in many functions in a non-debug compile, + * in which functions the only point of passing the list head pointer is to be + * able to run these checks. + */ + #define dlist_check(head) (void) (head) + #define slist_check(head) (void) (head) + #endif /* ILIST_DEBUG */ + + #define DLIST_STATIC_INIT(name) {{&name.head, &name.head}} + #define SLIST_STATIC_INIT(name) {{NULL}} + + /* + * The following function definitions are only used if inlining is supported by + * the compiler, or when included from a file that explicitly declares + * ILIST_USE_DEFINITION. + */ + #if defined(USE_INLINE) || defined(ILIST_DEFINE_FUNCTIONS) + + /* + * Initialize the head of a list. Previous state will be thrown away without + * any cleanup. + */ + INLINE_IF_POSSIBLE void + dlist_init(dlist_head *head) + { + head->head.next = head->head.prev = &head->head; + + dlist_check(head); + } + + /* + * Insert a node at the beginning of the list. + */ + INLINE_IF_POSSIBLE void + dlist_push_head(dlist_head *head, dlist_node *node) + { + node->next = head->head.next; + node->prev = &head->head; + node->next->prev = node; + head->head.next = node; + + dlist_check(head); + } + + /* + * Inserts a node at the end of the list. + */ + INLINE_IF_POSSIBLE void + dlist_push_tail(dlist_head *head, dlist_node *node) + { + node->next = &head->head; + node->prev = head->head.prev; + node->prev->next = node; + head->head.prev = node; + + dlist_check(head); + } + + /* + * Insert a node after another *in the same list* + */ + INLINE_IF_POSSIBLE void + dlist_insert_after(dlist_head *head, dlist_node *after, + dlist_node *node) + { + dlist_check(head); + /* XXX: assert 'after' is in 'head'? */ + + node->prev = after; + node->next = after->next; + after->next = node; + node->next->prev = node; + + dlist_check(head); + } + + /* + * Insert a node before another *in the same list* + */ + INLINE_IF_POSSIBLE void + dlist_insert_before(dlist_head *head, dlist_node *before, + dlist_node *node) + { + dlist_check(head); + /* XXX: assert 'after' is in 'head'? */ + + node->prev = before->prev; + node->next = before; + before->prev = node; + node->prev->next = node; + + dlist_check(head); + } + + /* + * Delete 'node' from list. + * + * It is not allowed to delete a 'node' which is is not in the list 'head' + */ + INLINE_IF_POSSIBLE void + dlist_delete(dlist_head *head, dlist_node *node) + { + dlist_check(head); + + node->prev->next = node->next; + node->next->prev = node->prev; + + dlist_check(head); + } + + /* + * Delete and return the first node from a list. + * + * Undefined behaviour when the list is empty, check with dlist_is_empty if + * necessary. + */ + INLINE_IF_POSSIBLE dlist_node * + dlist_pop_head_node(dlist_head *head) + { + dlist_node *ret; + + Assert(&head->head != head->head.next); + + ret = head->head.next; + dlist_delete(head, head->head.next); + return ret; + } + + /* + * Move element from any position in the list to the head position in the same + * list. + * + * Undefined behaviour if 'node' is not already part of the list. + */ + INLINE_IF_POSSIBLE void + dlist_move_head(dlist_head *head, dlist_node *node) + { + /* fast path if it's already at the head */ + if (&head->head == node) + return; + + dlist_delete(head, node); + dlist_push_head(head, node); + + dlist_check(head); + } + + /* + * Check whether the passed node is the last element in the list. + */ + INLINE_IF_POSSIBLE bool + dlist_has_next(dlist_head *head, dlist_node *node) + { + return node->next != &head->head; + } + + /* + * Check whether the passed node is the first element in the list. + */ + INLINE_IF_POSSIBLE bool + dlist_has_prev(dlist_head *head, dlist_node *node) + { + return node->prev != &head->head; + } + + /* + * Return the next node in the list. + * + * Undefined bheaviour when no next node exists, use dlist_has_next to make + * sure. + */ + INLINE_IF_POSSIBLE dlist_node * + dlist_next_node(dlist_head *head, dlist_node *node) + { + Assert(dlist_has_next(head, node)); + return node->next; + } + + /* + * Return previous node if there is one, NULL otherwise + * + * Undefined bheaviour when no prev node exists, use dlist_has_prev to make + * sure. + */ + INLINE_IF_POSSIBLE dlist_node * + dlist_prev_node(dlist_head *head, dlist_node *node) + { + Assert(dlist_has_prev(head, node)); + return node->prev; + } + + /* + * Return whether the list is empty. + */ + INLINE_IF_POSSIBLE bool + dlist_is_empty(dlist_head *head) + { + return head->head.next == &(head->head); + } + + /* internal support function */ + INLINE_IF_POSSIBLE void * + dlist_head_element_off(dlist_head *head, size_t off) + { + Assert(!dlist_is_empty(head)); + return (char *) head->head.next - off; + } + + /* + * Return the first node in the list. + * + * Use dlist_is_empty to make sure the list is not empty if not sure. + */ + INLINE_IF_POSSIBLE dlist_node * + dlist_head_node(dlist_head *head) + { + return dlist_head_element_off(head, 0); + } + + /* internal support function */ + INLINE_IF_POSSIBLE void * + dlist_tail_element_off(dlist_head *head, size_t off) + { + Assert(!dlist_is_empty(head)); + return (char *) head->head.prev - off; + } + + /* + * Return the last node in the list. + * + * Use dlist_is_empty to make sure the list is not empty if not sure. + */ + INLINE_IF_POSSIBLE dlist_node * + dlist_tail_node(dlist_head *head) + { + return dlist_tail_element_off(head, 0); + } + #endif /* defined(USE_INLINE) || + * defined(ILIST_DEFINE_FUNCTIONS) */ + + /* + * Return the containing struct of 'type' where 'membername' is the dlist_node + * pointed at by 'ptr'. + * + * This is used to convert a dlist_node* returned by some list + * navigation/manipulation back to its content. + * + * Note that AssertVariableIsOfTypeMacro is a compile time only check, so we + * don't have multiple evaluation dangers here. + */ + #define dlist_container(type, membername, ptr) \ + (AssertVariableIsOfTypeMacro(ptr, dlist_node *), \ + AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \ + ((type *)((char *)(ptr) - offsetof(type, membername))) \ + ) + /* + * Return the value of first element in the list. + * + * The list may not be empty. + * + * Note that AssertVariableIsOfTypeMacro is a compile time only check, so we + * don't have multiple evaluation dangers here. + */ + #define dlist_head_element(type, membername, ptr) \ + (AssertVariableIsOfTypeMacro(((type*) NULL)->membername, dlist_node), \ + ((type *)dlist_get_head_off(ptr, offsetof(type, membername)))) + + /* + * Return the value of first element in the list. + * + * The list may not be empty. + * + * Note that AssertVariableIsOfTypeMacro is a compile time only check, so we + * don't have multiple evaluation dangers here. + */ + #define dlist_tail_element(type, membername, ptr) \ + (AssertVariableIsOfTypeMacro(((type*) NULL)->membername, dlist_node), \ + ((type *)dlist_tail_element_off(ptr, offsetof(type, membername)))) + + /* + * Iterate through the list pointed at by 'ptr' storing the state in 'iter'. + * + * Access the current element with iter.cur. + * + * It is *not* allowed to manipulate the list during iteration. + */ + #define dlist_foreach(iter, ptr) \ + AssertVariableIsOfType(iter, dlist_iter); \ + AssertVariableIsOfType(ptr, dlist_head *); \ + for (iter.end = &(ptr)->head, iter.cur = iter.end->next; \ + iter.cur != iter.end; \ + iter.cur = iter.cur->next) + + + /* + * Iterate through the list pointed at by 'ptr' storing the state in 'iter'. + * + * Access the current element with iter.cur. + * + * It is allowed to delete the current element from the list. Every other + * manipulation can lead to corruption. + */ + #define dlist_foreach_modify(iter, ptr) \ + AssertVariableIsOfType(iter, dlist_mutable_iter); \ + AssertVariableIsOfType(ptr, dlist_head *); \ + for (iter.end = &(ptr)->head, iter.cur = iter.end->next, \ + iter.next = iter.cur->next; \ + iter.cur != iter.end; \ + iter.cur = iter.next, iter.next = iter.cur->next) + + /* + * Iterate through the list in reverse order. + * + * It is *not* allowed to manipulate the list during iteration. + */ + #define dlist_reverse_foreach(iter, ptr) \ + AssertVariableIsOfType(iter, dlist_iter); \ + AssertVariableIsOfType(ptr, dlist_head *); \ + for (iter.end = &(ptr)->head, iter.cur = iter.end->prev; \ + iter.cur != iter.end; \ + iter.cur = iter.cur->prev) + + #if defined(USE_INLINE) || defined(ILIST_DEFINE_FUNCTIONS) + + /* + * Initialize a singly linked list. + */ + INLINE_IF_POSSIBLE void + slist_init(slist_head *head) + { + head->head.next = NULL; + + slist_check(head); + } + + /* + * Is the list empty? + */ + INLINE_IF_POSSIBLE bool + slist_is_empty(slist_head *head) + { + slist_check(head); + + return head->head.next == NULL; + } + + /* internal support function */ + INLINE_IF_POSSIBLE void * + slist_head_element_off(slist_head *head, size_t off) + { + Assert(!slist_is_empty(head)); + return (char *) head->head.next - off; + } + + /* + * Push 'node' as the new first node in the list, pushing the original head to + * the second position. + */ + INLINE_IF_POSSIBLE void + slist_push_head(slist_head *head, slist_node *node) + { + node->next = head->head.next; + head->head.next = node; + + slist_check(head); + } + + /* + * Remove and return the first node in the list + * + * Undefined behaviour if the list is empty. + */ + INLINE_IF_POSSIBLE slist_node * + slist_pop_head_node(slist_head *head) + { + slist_node *node; + + Assert(!slist_is_empty(head)); + + node = head->head.next; + head->head.next = head->head.next->next; + + slist_check(head); + + return node; + } + + /* + * Insert a new node after another one + * + * Undefined behaviour if 'after' is not part of the list already. + */ + INLINE_IF_POSSIBLE void + slist_insert_after(slist_head *head, slist_node *after, + slist_node *node) + { + node->next = after->next; + after->next = node; + + slist_check(head); + } + + /* + * Return whether 'node' has a following node + */ + INLINE_IF_POSSIBLE bool + slist_has_next(slist_head *head, + slist_node *node) + { + slist_check(head); + + return node->next != NULL; + } + #endif /*-- defined(USE_INLINE || ILIST_DEFINE_FUNCTIONS) --*/ + + /* + * Return the containing struct of 'type' where 'membername' is the slist_node + * pointed at by 'ptr'. + * + * This is used to convert a slist_node* returned by some list + * navigation/manipulation back to its content. + * + * Note that AssertVariableIsOfTypeMacro is a compile time only check, so we + * don't have multiple evaluation dangers here. + */ + #define slist_container(type, membername, ptr) \ + (AssertVariableIsOfTypeMacro(ptr, slist_node *), \ + AssertVariableIsOfTypeMacro(((type*)NULL)->membername, slist_node), \ + ((type *)((char *)(ptr) - offsetof(type, membername))) \ + ) + /* + * Return the value of first element in the list. + */ + #define slist_head_element(type, membername, ptr) \ + (AssertVariableIsOfTypeMacro(((type*)NULL)->membername, slist_node), \ + slist_head_element_off(ptr, offsetoff(type, membername))) + + /* + * Iterate through the list 'ptr' using the iterator 'iter'. + * + * It is *not* allowed to manipulate the list during iteration. + */ + #define slist_foreach(iter, ptr) \ + AssertVariableIsOfType(iter, slist_iter); \ + AssertVariableIsOfType(ptr, slist_head *); \ + for (iter.cur = (ptr)->head.next; \ + iter.cur != NULL; \ + iter.cur = iter.cur->next) + + /* + * Iterate through the list 'ptr' using the iterator 'iter' allowing some + * modifications. + * + * It is allowed to delete the current element from the list and add new nodes + * before the current position. Every other manipulation can lead to + * corruption. + */ + #define slist_foreach_modify(iter, ptr) \ + AssertVariableIsOfType(iter, slist_mutable_iter); \ + AssertVariableIsOfType(ptr, slist_head *); \ + for (iter.cur = (ptr)->head.next, \ + iter.next = iter.cur ? iter.cur->next : NULL; \ + iter.cur != NULL; \ + iter.cur = iter.next, iter.next = iter.next ? iter.next->next : NULL) + + #endif /* ILIST_H */ diff src/include/utils/catcache.h index d91700a..cc6dab2 *** a/src/include/utils/catcache.h --- b/src/include/utils/catcache.h *************** *** 22,28 **** #include "access/htup.h" #include "access/skey.h" ! #include "lib/dllist.h" #include "utils/relcache.h" /* --- 22,28 ---- #include "access/htup.h" #include "access/skey.h" ! #include "lib/ilist.h" #include "utils/relcache.h" /* *************** *** 37,43 **** typedef struct catcache { int id; /* cache identifier --- see syscache.h */ ! struct catcache *cc_next; /* link to next catcache */ const char *cc_relname; /* name of relation the tuples come from */ Oid cc_reloid; /* OID of relation the tuples come from */ Oid cc_indexoid; /* OID of index matching cache keys */ --- 37,43 ---- typedef struct catcache { int id; /* cache identifier --- see syscache.h */ ! slist_node cc_next; /* list link */ const char *cc_relname; /* name of relation the tuples come from */ Oid cc_reloid; /* OID of relation the tuples come from */ Oid cc_indexoid; /* OID of index matching cache keys */ *************** typedef struct catcache *** 51,57 **** ScanKeyData cc_skey[CATCACHE_MAXKEYS]; /* precomputed key info for * heap scans */ bool cc_isname[CATCACHE_MAXKEYS]; /* flag "name" key columns */ ! Dllist cc_lists; /* list of CatCList structs */ #ifdef CATCACHE_STATS long cc_searches; /* total # searches against this cache */ long cc_hits; /* # of matches against existing entry */ --- 51,57 ---- ScanKeyData cc_skey[CATCACHE_MAXKEYS]; /* precomputed key info for * heap scans */ bool cc_isname[CATCACHE_MAXKEYS]; /* flag "name" key columns */ ! dlist_head cc_lists; /* list of CatCList structs */ #ifdef CATCACHE_STATS long cc_searches; /* total # searches against this cache */ long cc_hits; /* # of matches against existing entry */ *************** typedef struct catcache *** 66,72 **** long cc_lsearches; /* total # list-searches */ long cc_lhits; /* # of matches against existing lists */ #endif ! Dllist cc_bucket[1]; /* hash buckets --- VARIABLE LENGTH ARRAY */ } CatCache; /* VARIABLE LENGTH STRUCT */ --- 66,72 ---- long cc_lsearches; /* total # list-searches */ long cc_lhits; /* # of matches against existing lists */ #endif ! dlist_head cc_bucket[1]; /* hash buckets --- VARIABLE LENGTH ARRAY */ } CatCache; /* VARIABLE LENGTH STRUCT */ *************** typedef struct catctup *** 77,87 **** CatCache *my_cache; /* link to owning catcache */ /* ! * Each tuple in a cache is a member of a Dllist that stores the elements ! * of its hash bucket. We keep each Dllist in LRU order to speed repeated * lookups. */ ! Dlelem cache_elem; /* list member of per-bucket list */ /* * The tuple may also be a member of at most one CatCList. (If a single --- 77,88 ---- CatCache *my_cache; /* link to owning catcache */ /* ! * Each tuple in a cache is a member of a dlist that stores the elements ! * of its hash bucket. We keep each dlist in LRU order to speed repeated * lookups. */ ! dlist_node cache_elem; /* list member of per-bucket list */ ! dlist_head *cache_bucket; /* containing bucket dlist */ /* * The tuple may also be a member of at most one CatCList. (If a single *************** typedef struct catclist *** 139,145 **** * might not be true during bootstrap or recovery operations. (namespace.c * is able to save some cycles when it is true.) */ ! Dlelem cache_elem; /* list member of per-catcache list */ int refcount; /* number of active references */ bool dead; /* dead but not yet removed? */ bool ordered; /* members listed in index order? */ --- 140,146 ---- * might not be true during bootstrap or recovery operations. (namespace.c * is able to save some cycles when it is true.) */ ! dlist_node cache_elem; /* list member of per-catcache list */ int refcount; /* number of active references */ bool dead; /* dead but not yet removed? */ bool ordered; /* members listed in index order? */ *************** typedef struct catclist *** 153,159 **** typedef struct catcacheheader { ! CatCache *ch_caches; /* head of list of CatCache structs */ int ch_ntup; /* # of tuples in all caches */ } CatCacheHeader; --- 154,160 ---- typedef struct catcacheheader { ! slist_head ch_caches; /* head of list of CatCache structs */ int ch_ntup; /* # of tuples in all caches */ } CatCacheHeader;