Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Browse files

This commit was manufactured by cvs2svn to create tag 'REL_1_2_15'.

  • Loading branch information...
commit e4c061fea8dc7bcf408c44bd1ad8e82d76c8f5fc 2 parents d69817b + 1a552c0
cvs2svn authored
View
93 doc/adminguide/raceconditions.sgml
@@ -1,93 +0,0 @@
-<!-- $Id: raceconditions.sgml,v 1.1 2007-08-22 22:06:48 cbbrowne Exp $ -->
-<sect1 id="raceconditions"><title>Race Conditions and &slony1;</title>
-
-<indexterm><primary>race conditions</primary></indexterm>
-
-<para> No, this has nothing to do with racial harmony or lack thereof;
-the <ulink url="http://www.wikipedia.org/"> Wikipedia </ulink>
-describes it thus: <quote>A race condition or race hazard is a flaw in
-a system or process whereby the output of the process is unexpectedly
-and critically dependent on the sequence or timing of other
-events. </quote> In computing applications, race conditions arise most
-frequently in distributed or threaded applications when multiple parts
-of the application depend on some piece of shared state, and, if this
-state is not properly managed, confusion (error!) arises. More
-particularly, this usually involves situations where the state can
-change between the time it was checked and the time of use of the
-state. </para>
-
-<para> &slony1; has run into a number of race conditions during its history:
-
-<itemizedlist>
-
-<listitem><para> <xref linkend="stmtmoveset"> had, during the 1.0 and
-1.1 branches, the problem that nodes did not have any way to prevent
-them from processing <command>SYNC</command> events from the new
-origin node (which their state would cause them to consider a mere
-provider, and therefore <emphasis>not</emphasis> a source of
-replicable data) before recognizing the role change from subscriber to
-provider. </para>
-
-<para> This was fixed by introducing a new <command>ACCEPT
-SET</command> event that would be submitted by the new origin; this
-allowed subscribers to be aware of their need to wait for the
-<command> MOVE SET </command> event.</para> </listitem>
-
-<listitem><para>In a number of places, &slony1; has the SQL
-<command>lock table sl_config_lock;</command> in order to prevent race
-conditions while changing the sl_log_status sequence value. </para>
-</listitem>
-
-<listitem><para> The &lslon; option <xref
-linkend="slon-config-sync-interval-timeout"> is used to prevent a
-possible race condition in which the action sequence is bumped by the
-trigger while inserting the log row, which makes this bump is
-immediately visible to the sync thread, but where the resulting log
-rows are not visible yet. </para> </listitem>
-
-<listitem><para> The <quote>snapshot visibility</quote> approach used
-by &slony1; to determine what replicated data is to be associated with
-a specific <command>SYNC</command> avoids race conditions that would
-be associated with trying to purely use timestamps or ID ranges to
-determine what data is to be replicated. </para> </listitem>
-
-<listitem><para> In the 1.2 branch, up to version 1.2.11, which fixed
-this, <link linkend="logshipping"> log shipping </link> had a race
-condition where any time configuration is reloaded by the &lslon; (as
-takes place with a number of events, notably <xref
-linkend="stmtsubscribeset">), there was a risk of the
-<command>SYNC</command> IDs used to ensure proper ordering and
-application of log shipping archive log files being off by one.
-</para>
-
-<para> This was resolved in 1.2.11 by moving the ID number from an
-in-memory variable (susceptible to all sorts of troubles) to being
-managed, transaction-safe, in the subscriber database. </para>
-
-<para> The problem was never exposed by the <link linkend="testbed">
-test bed framework, </link> nicely demonstrating the common finding
-that race conditions are frequently highly dependent on patterns of
-data input or of application timing. </para>
-</listitem>
-
-</itemizedlist>
-
-</para>
-
-</sect1>
-
-<!-- Keep this comment at the end of the file
-Local variables:
-mode:sgml
-sgml-omittag:nil
-sgml-shorttag:t
-sgml-minimize-attributes:nil
-sgml-always-quote-attributes:t
-sgml-indent-step:1
-sgml-indent-data:t
-sgml-parent-document:"slony.sgml"
-sgml-exposed-tags:nil
-sgml-local-catalogs:("/usr/lib/sgml/catalog")
-sgml-local-ecat-files:nil
-End:
--->
View
409 src/misc/avl_tree.c
@@ -0,0 +1,409 @@
+/* ----------------------------------------------------------------------
+ * avl_tree.c
+ *
+ * AVL style self balancing tree support.
+ *
+ * Copyright (c) 2007, PostgreSQL Global Development Group
+ * Author: Jan Wieck, Afilias USA INC.
+ *
+ * $Id: avl_tree.c,v 1.2 2008-04-23 20:35:43 cbbrowne Exp $
+ * ----------------------------------------------------------------------
+ */
+
+#include "avl_tree.h"
+
+/* ----
+ * local function declarations
+ * ----
+ */
+static AVLnode *avl_makenode(void);
+static void avl_reset_node(AVLnode *node, AVLfreefunc *freefunc);
+static int avl_insertinto(AVLtree *tree, AVLnode **node,
+ void *cdata, AVLnode **result);
+static void avl_rotate_left(AVLnode **node);
+static void avl_rotate_right(AVLnode **node);
+
+
+/* ----
+ * avl_init() -
+ *
+ * Initilize an AVL tree structure.
+ *
+ * compfunc is a user supplied tri-state comparision function that compares
+ * two tree elements and returns <0, 0 or >0 (like strcmp).
+ *
+ * If freefunc is specified, it is called to free no longer used elements.
+ * Note that the element will not immediately be free'd on avl_delete(),
+ * but only on a avl_delete, avl_insert sequence using the same key.
+ * ----
+ */
+void
+avl_init(AVLtree *tree, AVLcompfunc *compfunc, AVLfreefunc *freefunc)
+{
+ tree->root = NULL;
+ tree->compfunc = compfunc;
+ tree->freefunc = freefunc;
+}
+
+
+/* ----
+ * avl_reset() -
+ *
+ * Reset an AVL tree to empty. This will call the user defined
+ * free function for all elements in the tree, destroy all nodes
+ * and declare the tree empty again.
+ * ----
+ */
+void
+avl_reset(AVLtree *tree)
+{
+ avl_reset_node(tree->root, tree->freefunc);
+ tree->root = NULL;
+}
+
+
+/* ----
+ * avl_reset_node() -
+ *
+ * avl_reset()'s workhorse.
+ * ----
+ */
+void
+avl_reset_node(AVLnode *node, AVLfreefunc *freefunc)
+{
+ if (node == NULL)
+ return;
+
+ avl_reset_node(node->lnode, freefunc);
+ avl_reset_node(node->rnode, freefunc);
+
+ if (freefunc != NULL)
+ freefunc(node->cdata);
+ free(node);
+}
+
+
+/* ----
+ * avl_insert() -
+ *
+ * Insert an element into an AVL tree. On return AVL_DATA(node) might
+ * point to an existing entry with the same key. If the caller replaces
+ * the entry, it must free the existing one since AVL will no longer
+ * keep track of it.
+ * ----
+ */
+AVLnode *
+avl_insert(AVLtree *tree, void *cdata)
+{
+ AVLnode *result;
+ int depth;
+
+ /*
+ * If this is an empty tree, create the root node.
+ */
+ if (tree->root == NULL)
+ return (tree->root = avl_makenode());
+
+ /*
+ * Traverse the tree to find the insert point.
+ */
+ result = NULL;
+ depth = avl_insertinto(tree, &(tree->root), cdata, &result);
+ return result;
+}
+
+
+/* ----
+ * avl_lookup() -
+ *
+ * Search for an existing key in the tree.
+ * ----
+ */
+AVLnode *
+avl_lookup(AVLtree *tree, void *cdata)
+{
+ AVLnode *node;
+ int cmp;
+
+ node = tree->root;
+ while (node != NULL)
+ {
+ cmp = tree->compfunc(cdata, node->cdata);
+ if (cmp == 0)
+ {
+ /*
+ * Found the node. If it is marked deleted, return NULL anyway.
+ * Otherwise return this node.
+ */
+ if (node->deleted)
+ return NULL;
+ return node;
+ }
+
+ /*
+ * Search on ...
+ */
+ if (cmp < 0)
+ node = node->lnode;
+ else
+ node = node->rnode;
+ }
+
+ /*
+ * No such element found
+ */
+ return NULL;
+}
+
+
+/* ----
+ * avl_delete() -
+ *
+ * Mark a given element as deleted. Subsequent lookups for the element
+ * will return NULL. Note that the caller should NOT free the memory
+ * of the element, as it is AVL's property altogether after the delete.
+ *
+ * avl_delete() returns 1 on success, 0 if no such element was found.
+ * ----
+ */
+int
+avl_delete(AVLtree *tree, void *cdata)
+{
+ AVLnode *node;
+
+ if ((node = avl_lookup(tree, cdata)) == NULL)
+ return 0;
+
+ node->deleted = 1;
+ return 1;
+}
+
+
+/* ----
+ * avl_insertinto() -
+ *
+ * The heart of avl_insert().
+ * ----
+ */
+static int
+avl_insertinto(AVLtree *tree, AVLnode **node,
+ void *cdata, AVLnode **result)
+{
+ int cmp;
+
+ /*
+ * Compare the node at hand with the new elements key.
+ */
+ cmp = (tree->compfunc) (cdata, (*node)->cdata);
+
+ if (cmp > 0)
+ {
+ /*
+ * New element is > than node. Insert to the right.
+ */
+ if ((*node)->rnode == NULL)
+ {
+ /*
+ * Right side of current node is empty. Create a new node there
+ * and return new maximum depth. Note that this can only be 1
+ * because otherwise this node would have been unbalanced before.
+ */
+ (*node)->rnode = *result = avl_makenode();
+ (*node)->rdepth = 1;
+ return 1;
+ }
+
+ /*
+ * Right hand node exists. Recurse into that and remember the new
+ * right hand side depth.
+ */
+ (*node)->rdepth = avl_insertinto(tree, &((*node)->rnode),
+ cdata, result) + 1;
+
+ /*
+ * A right hand side insert can unbalance this node only to the right.
+ */
+ if (AVL_BALANCE(*node) > 1)
+ {
+ if (AVL_BALANCE((*node)->rnode) > 0)
+ {
+ /*
+ * RR situation, rebalance the tree by left rotating this
+ * node.
+ */
+ avl_rotate_left(node);
+ }
+ else
+ {
+ /*
+ * RL situation, rebalance the tree by first right rotating
+ * the right hand side, then left rotating this node.
+ */
+ avl_rotate_right(&((*node)->rnode));
+ avl_rotate_left(node);
+ }
+ }
+
+ return AVL_MAXDEPTH(*node);
+ }
+ else if (cmp < 0)
+ {
+ /*
+ * New element is < than node. Insert to the left.
+ */
+ if ((*node)->lnode == NULL)
+ {
+ /*
+ * Left side of current node is empty. Create a new node there and
+ * return new maximum depth. Note that this can only be 1 because
+ * otherwise this node would have been unbalanced before.
+ */
+ (*node)->lnode = *result = avl_makenode();
+ (*node)->ldepth = 1;
+ return AVL_MAXDEPTH(*node);
+ }
+
+ /*
+ * Left hand node exists. Recurse into that and remember the new left
+ * hand side depth.
+ */
+ (*node)->ldepth = avl_insertinto(tree, &((*node)->lnode),
+ cdata, result) + 1;
+
+ /*
+ * A left hand side insert can unbalance this node only to the left.
+ */
+ if (AVL_BALANCE(*node) < -1)
+ {
+ if (AVL_BALANCE((*node)->lnode) < 0)
+ {
+ /*
+ * LL situation, rebalance the tree by right rotating this
+ * node.
+ */
+ avl_rotate_right(node);
+ }
+ else
+ {
+ /*
+ * LR situation, rebalance the tree by first left rotating the
+ * left node, then right rotating this node.
+ */
+ avl_rotate_left(&((*node)->lnode));
+ avl_rotate_right(node);
+ }
+ }
+
+ return AVL_MAXDEPTH(*node);
+ }
+ else
+ {
+ /*
+ * The new element is equal to this node. If it is marked for
+ * deletion, free the user element data now. The caller is supposed to
+ * replace it with a new element having the the key.
+ */
+ if ((*node)->deleted && tree->freefunc != NULL)
+ {
+ (tree->freefunc) ((*node)->cdata);
+ (*node)->cdata = NULL;
+ (*node)->deleted = 0;
+ }
+ *result = *node;
+ return AVL_MAXDEPTH(*node);
+ }
+}
+
+
+/* ----
+ * avl_makenode() -
+ *
+ * Create a new empty node.
+ * ----
+ */
+static AVLnode *
+avl_makenode(void)
+{
+ AVLnode *new;
+
+ new = (AVLnode *) malloc(sizeof(AVLnode));
+ memset(new, 0, sizeof(AVLnode));
+
+ return new;
+}
+
+
+/* ----
+ * avl_rotate_left() -
+ *
+ * Rebalance a node to the left.
+ * ----
+ */
+static void
+avl_rotate_left(AVLnode **node)
+{
+ AVLnode *rtmp;
+
+ /*
+ * save right node
+ */
+ rtmp = (*node)->rnode;
+
+ /*
+ * move right nodes left side to this nodes right
+ */
+ (*node)->rnode = rtmp->lnode;
+ if (rtmp->lnode != NULL)
+ (*node)->rdepth = AVL_MAXDEPTH(rtmp->lnode) + 1;
+ else
+ (*node)->rdepth = 0;
+
+ /*
+ * Move this node to right nodes left side
+ */
+ rtmp->lnode = *node;
+ rtmp->ldepth = AVL_MAXDEPTH(*node) + 1;
+
+ /*
+ * Let parent point to right node
+ */
+ *node = rtmp;
+}
+
+
+/* ----
+ * avl_rotate_right() -
+ *
+ * Rebalance a node to the right.
+ * ----
+ */
+static void
+avl_rotate_right(AVLnode **node)
+{
+ AVLnode *ltmp;
+
+ /*
+ * save left node
+ */
+ ltmp = (*node)->lnode;
+
+ /*
+ * move left nodes right side to this nodes left
+ */
+ (*node)->lnode = ltmp->rnode;
+ if (ltmp->rnode != NULL)
+ (*node)->ldepth = AVL_MAXDEPTH(ltmp->rnode) + 1;
+ else
+ (*node)->ldepth = 0;
+
+ /*
+ * Move this node to left nodes right side
+ */
+ ltmp->rnode = *node;
+ ltmp->rdepth = AVL_MAXDEPTH(*node) + 1;
+
+ /*
+ * Let parent point to left node
+ */
+ *node = ltmp;
+}
View
68 src/misc/avl_tree.h
@@ -0,0 +1,68 @@
+/* ----------------------------------------------------------------------
+ * avl_tree.h
+ *
+ * Declarations for AVL style balanced tree support.
+ *
+ * Copyright (c) 2003-2007, PostgreSQL Global Development Group
+ * Author: Jan Wieck, Afilias USA INC.
+ *
+ * $Id: avl_tree.h,v 1.2 2008-04-23 20:35:43 cbbrowne Exp $
+ * ----------------------------------------------------------------------
+ */
+
+#ifndef _AVL_TREE_H_INCLUDED_
+#define _AVL_TREE_H_INCLUDED_
+
+/* ----
+ * Callback function type declarations
+ * ----
+ */
+typedef int (AVLcompfunc) (void *, void *);
+typedef void (AVLfreefunc) (void *);
+
+
+/* ----
+ * Data structures
+ * ----
+ */
+typedef struct AVLnode_s
+{
+ struct AVLnode_s *lnode,
+ *rnode;
+ int ldepth,
+ rdepth;
+ void *cdata;
+ int deleted;
+} AVLnode;
+
+typedef struct AVLtree_s
+{
+ AVLnode *root;
+ AVLcompfunc *compfunc;
+ AVLfreefunc *freefunc;
+} AVLtree;
+
+/* ----
+ * Macros
+ * ----
+ */
+#define AVL_DATA(n) (n)->cdata
+#define AVL_SETDATA(n,p) ((n)->cdata = (p))
+#define AVL_MAXDEPTH(n) (((n)->ldepth > (n)->rdepth) ? (n)->ldepth : (n)->rdepth)
+#define AVL_BALANCE(n) ((n)->rdepth - (n)->ldepth)
+
+#define AVL_INITIALIZER(cmp,free) {NULL, (cmp), (free)}
+
+
+/* ----
+ * Public functions
+ * ----
+ */
+void avl_init(AVLtree *tree, AVLcompfunc *compfunc,
+ AVLfreefunc *freefunc);
+void avl_reset(AVLtree *tree);
+AVLnode *avl_insert(AVLtree *tree, void *cdata);
+AVLnode *avl_lookup(AVLtree *tree, void *cdata);
+int avl_delete(AVLtree *tree, void *cdata);
+
+#endif /* _AVL_TREE_H_INCLUDED_ */
Please sign in to comment.
Something went wrong with that request. Please try again.