From 7b52cc13af4e85f1ca2deb6b6c77de9c95ea0dcf Mon Sep 17 00:00:00 2001
From: scuri <scuri>
Date: Fri, 17 Oct 2008 06:10:33 +0000
Subject: First commit - moving from LuaForge to SourceForge

---
 src/pdflib/pdcore/pc_contain.c | 518 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 518 insertions(+)
 create mode 100644 src/pdflib/pdcore/pc_contain.c

(limited to 'src/pdflib/pdcore/pc_contain.c')

diff --git a/src/pdflib/pdcore/pc_contain.c b/src/pdflib/pdcore/pc_contain.c
new file mode 100644
index 0000000..6a3cdfc
--- /dev/null
+++ b/src/pdflib/pdcore/pc_contain.c
@@ -0,0 +1,518 @@
+/*---------------------------------------------------------------------------*
+ |              PDFlib - A library for generating PDF on the fly             |
+ +---------------------------------------------------------------------------+
+ | Copyright (c) 1997-2006 Thomas Merz and PDFlib GmbH. All rights reserved. |
+ +---------------------------------------------------------------------------+
+ |                                                                           |
+ |    This software is subject to the PDFlib license. It is NOT in the       |
+ |    public domain. Extended versions and commercial licenses are           |
+ |    available, please check http://www.pdflib.com.                         |
+ |                                                                           |
+ *---------------------------------------------------------------------------*/
+
+/* $Id: pc_contain.c,v 1.1 2008/10/17 06:10:43 scuri Exp $
+ *
+ * PDFlib generic container classes
+ *
+ */
+
+#include "pc_util.h"
+#include "pc_contain.h"
+
+
+/**************************** avl tree class ****************************/
+
+typedef struct avl_node_s avl_node;
+
+struct avl_node_s
+{
+    const char *name;
+    int		balance;
+    avl_node *	left;
+    avl_node *	right;
+};
+
+#undef	COMMENT
+#ifdef	COMMENT
+
+before single rotate right; after insertion of X.
+
+                       root(-2)
+
+                    /            \
+
+               lc(-1)           +------+
+                                | rc   |
+              /      \          |      |
+                                |      |
+        +------+    +------+    |      |
+        | llc  |    | rlc  |    | n    |
+        |      |    |      |    +------+
+        |      |    |      |
+        |      |    |      |
+        | n    |    | n    |
+        +------+    +------+
+
+            |
+
+            X
+
+
+after single rotate right.
+
+                  lc(0)
+
+               /        \
+
+        +------+          root(0)
+        | llc  |
+        |      |        /         \
+        |      |
+        |      |    +------+    +------+
+        | n    |    | rlc  |    | rc   |
+        +------+    |      |    |      |
+                    |      |    |      |
+            |       |      |    |      |
+                    | n    |    | n    |
+            X       +------+    +------+
+
+
+
+before double rotate right; after insertion of X/Y.
+
+                             root(-2)
+
+                       /                  \
+
+                lc(+1)                      +------+
+                                            | rc   |
+              /        \                    |      |
+                                            |      |
+        +------+         rlc(-1/+1)         |      |
+        | llc  |                            |      |
+        |      |        /         \         |      |
+        |      |                            |      |
+        |      |    +------+    +------+    | n    |
+        |      |    | lrlc |    | rrlc |    +------+
+        |      |    |      |    |      |
+        |      |    |      |    |      |
+        | n    |    | n-1  |    | n-1  |
+        +------+    +------+    +------+
+
+                        |           |
+
+			X           Y
+
+
+after double rotate right:
+
+                          rlc(0)
+
+                      /            \
+
+              lc(0/-1)               root(+1/0)
+
+              /      \                /      \
+
+        +------+    +------+    +------+    +------+
+        | llc  |    | lrlc |    | rrlc |    | rc   |
+        |      |    |      |    |      |    |      |
+        |      |    |      |    |      |    |      |
+        |      |    | n-1  |    | n-1  |    |      |
+        |      |    +------+    +------+    |      |
+        |      |                            |      |
+        |      |        |           |       |      |
+        | n    |                            | n    |
+        +------+        X           Y       +------+
+
+
+avl_node *
+avl_insert(avl_node *root, const char *name, pdc_bool *change_parent_balance)
+{
+    pdc_bool change_balance = pdc_false;
+
+    if (root == 0)
+    {
+	avl_node *result = (avl_node *) malloc(sizeof (avl_node));
+
+	result->name = name;
+	result->balance = 0;
+	result->left = (avl_node *) 0;
+	result->right = (avl_node *) 0;
+	*change_parent_balance = pdc_true;
+	return result;
+    }
+
+    if (strcmp(name, root->name) < 0)
+    {
+	root->left = avl_insert(root->left, name, &change_balance);
+
+	if (change_balance && --root->balance < 0)
+	{
+	    if (root->balance == -1)
+	    {
+		*change_parent_balance = pdc_true;
+	    }
+	    else				/* root->balance == -2 */
+	    {
+		avl_node *lc = root->left;	/* left child */
+		avl_node *rlc = lc->right;	/* right of left child */
+
+		if (lc->balance == -1)		/* single rotate right */
+		{
+		    root->left = rlc;
+		    lc->right = root;
+		    lc->balance = root->balance = 0;
+		    return lc;
+		}
+		else				/* double rotate right */
+		{
+		    root->balance = (rlc->balance == -1) ? +1 : 0;
+		    lc->balance   = (rlc->balance == +1) ? -1 : 0;
+		    rlc->balance  = 0;
+		    lc->right	= rlc->left;
+		    rlc->left	= lc;
+		    root->left	= rlc->right;
+		    rlc->right	= root;
+		    return rlc;
+		}
+	    }
+	}
+    }
+    else
+    {
+	root->right = avl_insert(root->right, name, &change_balance);
+
+	if (change_balance && ++root->balance > 0)
+	{
+	    if (root->balance == +1)
+	    {
+		*change_parent_balance = pdc_true;
+	    }
+	    else				/* root->balance == +2 */
+	    {
+		avl_node *rc = root->right;	/* right child */
+		avl_node *lrc = rc->left;	/* left of right child */
+
+		if (rc->balance == +1)		/* single rotate left */
+		{
+		    root->right = lrc;
+		    rc->left = root;
+		    rc->balance = root->balance = 0;
+		    return rc;
+		}
+		else				/* double rotate left */
+		{
+		    root->balance = (lrc->balance == +1) ? -1 : 0;
+		    rc->balance   = (lrc->balance == -1) ? +1 : 0;
+		    lrc->balance  = 0;
+		    rc->left	= lrc->right;
+		    lrc->right	= rc;
+		    root->right	= lrc->left;
+		    lrc->left	= root;
+		    return lrc;
+		}
+	    }
+	}
+    }
+
+    return root;
+}
+
+#endif	/* COMMENT */
+
+/***************************** vector class *****************************/
+
+struct pdc_vtr_s
+{
+    pdc_core *	pdc;
+
+    pdc_ced	ced;		/* container entry descriptor		*/
+    void *	context;	/* client context			*/
+
+    char **	ctab;		/* chunk table				*/
+    int		ctab_size;	/* current # of slots			*/
+    int		ctab_incr;
+    int		chunk_size;	/* # of items per chunk			*/
+    int		size;		/* current # of items total		*/
+};
+
+
+static const pdc_vtr_parms vtr_dflt_parms =
+{
+    0,				/* init_size				*/
+    100,			/* chunk_size				*/
+    10				/* ctab_incr				*/
+};
+
+void
+pdc_vtr_dflt_parms(pdc_vtr_parms *vp)
+{
+    *vp = vtr_dflt_parms;
+}
+
+
+static void
+pdc_vtr_grow_ctab(pdc_vtr *v, int new_size)
+{
+    static const char fn[] = "pdc_vtr_grow_ctab";
+
+    int i;
+
+    v->ctab = (char **)
+	pdc_realloc(v->pdc, v->ctab, (size_t) (new_size * sizeof (char *)), fn);
+
+    for (i = v->ctab_size; i < new_size; ++i)
+	v->ctab[i] = (char *) 0;
+
+    v->ctab_size = new_size;
+} /* pdc_vtr_grow_ctab */
+
+
+pdc_vtr *
+pdc_vtr_new(
+    pdc_core *pdc,
+    const pdc_ced *ced,
+    void *context,
+    const pdc_vtr_parms *parms)
+{
+    static const char fn[] = "pdc_vtr_new";
+
+    pdc_vtr *v = (pdc_vtr *) pdc_malloc(pdc, sizeof (pdc_vtr), fn);
+
+    if (!parms)
+	parms = &vtr_dflt_parms;
+
+    v->pdc = pdc;
+    v->ced = *ced;
+    v->context = context ? context : pdc;
+
+    v->ctab = (char **) 0;
+    v->ctab_size = 0;
+    v->ctab_incr = parms->ctab_incr;
+    v->chunk_size = parms->chunk_size;
+    v->size = 0;
+
+    if (parms->init_size != 0)
+    {
+	PDC_TRY (pdc)
+	{
+	    pdc_vtr_resize(v, parms->init_size);
+	}
+	PDC_CATCH (pdc)
+	{
+	    pdc_vtr_delete(v);
+	    PDC_RETHROW(pdc);
+	}
+    }
+
+    return v;
+} /* pdc_vtr_new */
+
+
+void
+pdc_vtr_delete(pdc_vtr *v)
+{
+    int cs = v->chunk_size;
+    int i;
+
+    if (v->size != 0 && v->ced.release)
+    {
+	for (i = 0; i < v->size; ++i)
+	{
+	    v->ced.release(v->context, (void *)
+		&v->ctab[i / cs][(i % cs) * v->ced.size]);
+	}
+    }
+
+    for (i = 0; i < v->ctab_size && v->ctab[i] != (char *) 0; ++i)
+    {
+	pdc_free(v->pdc, v->ctab[i]);
+    }
+
+    if (v->ctab)
+	pdc_free(v->pdc, v->ctab);
+
+    pdc_free(v->pdc, v);
+} /* pdc_vtr_delete */
+
+
+int
+pdc_vtr_size(const pdc_vtr *v)
+{
+    return (int) v->size;
+} /* pdc_vtr_size */
+
+
+void
+pdc_vtr_resize(pdc_vtr *v, int new_size)
+{
+    static const char fn[] = "pdc_vtr_resize";
+
+    int cs = v->chunk_size;
+
+    PDC_ASSERT(v->pdc, 0 <= new_size);
+
+    if (new_size < v->size)
+    {
+	if (!v->ced.release)
+	{
+	    v->size = new_size;
+	}
+	else
+	{
+	    do
+	    {
+		--v->size;
+
+		v->ced.release(v->context, (void *)
+		    &v->ctab[v->size / cs][(v->size % cs) * v->ced.size]);
+	    } while (new_size < v->size);
+	}
+
+	/* TODO: free chunks if possible? */
+    }
+    else if (new_size > v->size)
+    {
+	int curr_slot = v->size / cs;
+	int new_ctsize = (new_size + cs - 1) / cs;
+	int i;
+
+	if (v->ctab_size < new_ctsize)
+	    pdc_vtr_grow_ctab(v, new_ctsize);
+
+	for (i = curr_slot; i < new_ctsize; ++i)
+	{
+	    if (v->ctab[i] == (char *) 0)
+	    {
+		v->ctab[i] = (char *)
+		    pdc_malloc(v->pdc, (size_t) (cs * v->ced.size), fn);
+	    }
+	}
+
+	if (v->ced.reclaim)
+	{
+	    for (i = v->size; i < new_size; ++i)
+	    {
+		v->ced.reclaim((void *) &v->ctab[i/cs][(i%cs) * v->ced.size]);
+	    }
+	}
+
+	v->size = new_size;
+    }
+} /* pdc_vtr_resize */
+
+
+void *
+pdc__vtr_at(const pdc_vtr *v, int idx)
+{
+    static const char fn[] = "pdc__vtr_at";
+
+    int cs = v->chunk_size;
+
+    if (idx < 0 || v->size <= idx)
+	pdc_error(v->pdc, PDC_E_INT_ARRIDX,
+	    pdc_errprintf(v->pdc, "%d", idx), fn, 0, 0);
+	    /* TODO: "%u" */
+
+    return (void *) (&v->ctab[idx / cs][(idx % cs) * v->ced.size]);
+} /* pdc__vtr_at */
+
+
+#if 0
+const void *
+pdc__vtr_at_c(const pdc_vtr *v, int idx)
+{
+    static const char fn[] = "pdc__vtr_at_c";
+
+    int cs = v->chunk_size;
+
+    if (idx < 0 || v->size <= idx)
+	pdc_error(v->pdc, PDC_E_INT_ARRIDX,
+	    pdc_errprintf(v->pdc, "%d", idx), fn, 0, 0);
+	    /* TODO: "%u" */
+
+    return (const void *) (&v->ctab[idx / cs][(idx % cs) * v->ced.size]);
+} /* pdc__vtr_at_c */
+#endif
+
+
+void *
+pdc__vtr_top(const pdc_vtr *v)
+{
+    int cs = v->chunk_size;
+    int idx;
+
+    if (v->size == 0)
+	return (void *) 0;
+
+    idx = v->size - 1;
+    return (void *) (&v->ctab[idx / cs][(idx % cs) * v->ced.size]);
+} /* pdc__vtr_top */
+
+
+#if 0
+const void *
+pdc__vtr_top_c(const pdc_vtr *v)
+{
+    int cs = v->chunk_size;
+    int idx;
+
+    if (v->size == 0)
+	return (void *) 0;
+
+    idx = v->size - 1;
+    return (const void *) (&v->ctab[idx / cs][(idx % cs) * v->ced.size]);
+} /* pdc__vtr_top_c */
+#endif
+
+
+void *
+pdc__vtr_push(pdc_vtr *v)
+{
+    static char fn[] = "pdc__vtr_push";
+
+    int cs = v->chunk_size;
+    int idx = v->size;
+    int slot = idx / cs;
+    char *target;
+
+    if (v->ctab_size <= slot)
+	pdc_vtr_grow_ctab(v, v->ctab_size + v->ctab_incr);
+
+    if (v->ctab[slot] == (char *) 0)
+    {
+	v->ctab[slot] = (char *)
+	    pdc_malloc(v->pdc, (size_t) (cs * v->ced.size), fn);
+    }
+
+    ++v->size;
+    target = &v->ctab[slot][(idx % cs) * v->ced.size];
+
+    if (v->ced.reclaim)
+    {
+	v->ced.reclaim((void *) target);
+    }
+
+    return (void *) target;
+} /* pdc__vtr_push */
+
+
+void
+pdc_vtr_pop(pdc_vtr *v)
+{
+    static char fn[] = "pdc_vtr_pop";
+
+    int cs = v->chunk_size;
+
+    if (v->size == 0)
+	pdc_error(v->pdc, PDC_E_INT_STACK_UNDER, fn, 0, 0, 0);
+
+    --v->size;
+
+    if (v->ced.release)
+    {
+	v->ced.release(v->context, (void *)
+	    &v->ctab[v->size / cs][(v->size % cs) * v->ced.size]);
+    }
+} /* pdc_vtr_pop */
-- 
cgit v1.2.3