From a972dbb9bd731a439d009bd51e36981c41a06232 Mon Sep 17 00:00:00 2001
From: scuri <scuri>
Date: Tue, 20 Oct 2009 18:12:26 +0000
Subject: *** empty log message ***

---
 src/pdflib/pdcore/pc_contain.c | 499 ++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 494 insertions(+), 5 deletions(-)

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

diff --git a/src/pdflib/pdcore/pc_contain.c b/src/pdflib/pdcore/pc_contain.c
index 6a3cdfc..ca752f0 100644
--- a/src/pdflib/pdcore/pc_contain.c
+++ b/src/pdflib/pdcore/pc_contain.c
@@ -10,7 +10,7 @@
  |                                                                           |
  *---------------------------------------------------------------------------*/
 
-/* $Id: pc_contain.c,v 1.1 2008/10/17 06:10:43 scuri Exp $
+/* $Id: pc_contain.c,v 1.2 2009/10/20 18:12:26 scuri Exp $
  *
  * PDFlib generic container classes
  *
@@ -221,7 +221,186 @@ avl_insert(avl_node *root, const char *name, pdc_bool *change_parent_balance)
 
 #endif	/* COMMENT */
 
-/***************************** vector class *****************************/
+
+/*************************** bit vector class ***************************/
+
+struct pdc_bvtr_s
+{
+    pdc_core *	pdc;
+
+    char **	ctab;		/* chunk table				*/
+    int		ctab_size;	/* current # of slots			*/
+    int		ctab_incr;
+    int		chunk_size;	/* # of bytes per chunk			*/
+    int		size;		/* current # of bytes total		*/
+    char	init_char;	/* 0x00 or 0xFF				*/
+};
+
+
+static const pdc_bvtr_parms bvtr_dflt_parms =
+{
+    0,				/* initial number of bits		*/
+    pdc_false,			/* initial bit value			*/
+    1000,			/* number of bytes per chunk		*/
+    10				/* chunk table increment		*/
+};
+
+
+void pdc_bvtr_dflt_parms(pdc_bvtr_parms *vp)
+{
+    *vp = bvtr_dflt_parms;
+}
+
+
+pdc_bvtr *pdc_bvtr_new(pdc_core *pdc, const pdc_bvtr_parms *parms)
+{
+    static const char fn[] = "pdc_bvtr_new";
+
+    pdc_bvtr *v = (pdc_bvtr *) pdc_malloc(pdc, sizeof (pdc_bvtr), fn);
+
+    if (!parms)
+	parms = &bvtr_dflt_parms;
+
+    v->pdc = pdc;
+
+    v->ctab = (char **) 0;
+    v->ctab_size = 0;
+    v->ctab_incr = parms->ctab_incr;
+    v->chunk_size = parms->chunk_size;
+    v->size = 0;
+    v->init_char = parms->init_value ? 0xFF : 0x00;
+
+    if (parms->init_n_bits != 0)
+    {
+	PDC_TRY (pdc)
+	{
+	    pdc_bvtr_resize(v, parms->init_n_bits);
+	}
+	PDC_CATCH (pdc)
+	{
+	    pdc_bvtr_delete(v);
+	    PDC_RETHROW(pdc);
+	}
+    }
+
+    return v;
+} /* pdc_bvtr_new */
+
+
+void pdc_bvtr_delete(pdc_bvtr *v)
+{
+    int i;
+
+    for (i = 0; i < v->ctab_size && v->ctab[i]; ++i)
+    {
+	pdc_free(v->pdc, v->ctab[i]);
+    }
+
+    if (v->ctab)
+	pdc_free(v->pdc, v->ctab);
+
+    pdc_free(v->pdc, v);
+} /* pdc_bvtr_delete */
+
+
+void
+pdc_bvtr_resize(pdc_bvtr *v, int n_bits)
+{
+    static const char fn[] = "pdc_bvtr_resize";
+
+    int cs = v->chunk_size;
+    int new_size = (n_bits + 7) / 8;
+    int new_ctsize = (new_size + cs - 1) / cs;	/* TODO: ctab_incr? */
+    int i;
+
+    PDC_ASSERT(v->pdc, 0 <= n_bits);
+
+    if (new_size < v->size)
+    {
+	if (new_ctsize < v->ctab_size)
+	{
+	    for (i = new_ctsize; i < v->ctab_size; ++i)
+	    {
+		pdc_free(v->pdc, v->ctab[i]);
+	    }
+	}
+
+	v->ctab_size = new_ctsize;
+	v->size = new_ctsize * cs;
+    }
+    else if (new_size > v->size)
+    {
+	v->ctab = (char **) pdc_realloc(v->pdc, v->ctab,
+				(size_t) (new_ctsize * sizeof (char *)), fn);
+
+	for (i = v->size / cs; i < new_ctsize; ++i)
+	{
+	    int k;
+
+	    v->ctab[i] = (char *) pdc_malloc(v->pdc, (size_t) cs, fn);
+
+	    for (k = 0; k < cs; ++k)
+	    {
+		v->ctab[i][k] = v->init_char;
+	    }
+	}
+
+	v->ctab_size = new_ctsize;
+	v->size = new_ctsize * cs;
+    }
+} /* pdc_vtr_resize */
+
+
+pdc_bool
+pdc_bvtr_getbit(const pdc_bvtr *v, int n)
+{
+    static const char fn[] = "pdc_bvtr_getbit";
+
+    int cs = v->chunk_size;
+    int idx = n / 8;
+    int bit = 1 << (n % 8);
+
+    if (idx < 0 || v->size <= idx)
+	pdc_error(v->pdc, PDC_E_INT_ARRIDX,
+	    pdc_errprintf(v->pdc, "%d", n), fn, 0, 0);
+
+    return (v->ctab[idx / cs][idx % cs] & bit) != 0;
+} /* pdc_bvtr_getbit */
+
+
+void pdc_bvtr_setbit(const pdc_bvtr *v, int n)
+{
+    static const char fn[] = "pdc_bvtr_setbit";
+
+    int cs = v->chunk_size;
+    int idx = n / 8;
+    int bit = 1 << (n % 8);
+
+    if (idx < 0 || v->size <= idx)
+	pdc_error(v->pdc, PDC_E_INT_ARRIDX,
+	    pdc_errprintf(v->pdc, "%d", n), fn, 0, 0);
+
+    v->ctab[idx / cs][idx % cs] |= bit;
+} /* pdc_bvtr_setbit */
+
+
+void pdc_bvtr_clrbit(const pdc_bvtr *v, int n)
+{
+    static const char fn[] = "pdc_bvtr_clrbit";
+
+    int cs = v->chunk_size;
+    int idx = n / 8;
+    int bit = 1 << (n % 8);
+
+    if (idx < 0 || v->size <= idx)
+	pdc_error(v->pdc, PDC_E_INT_ARRIDX,
+	    pdc_errprintf(v->pdc, "%d", n), fn, 0, 0);
+
+    v->ctab[idx / cs][idx % cs] &= ~bit;
+} /* pdc_bvtr_clrbit */
+
+
+/*********************** stack type vector class ************************/
 
 struct pdc_vtr_s
 {
@@ -242,7 +421,7 @@ static const pdc_vtr_parms vtr_dflt_parms =
 {
     0,				/* init_size				*/
     100,			/* chunk_size				*/
-    10				/* ctab_incr				*/
+    10,				/* ctab_incr				*/
 };
 
 void
@@ -413,7 +592,6 @@ pdc__vtr_at(const pdc_vtr *v, int idx)
     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 */
@@ -430,7 +608,6 @@ pdc__vtr_at_c(const pdc_vtr *v, int idx)
     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 */
@@ -516,3 +693,315 @@ pdc_vtr_pop(pdc_vtr *v)
 	    &v->ctab[v->size / cs][(v->size % cs) * v->ced.size]);
     }
 } /* pdc_vtr_pop */
+
+
+/************************ heap type vector class ************************/
+
+typedef struct pdc_link_s	pdc_link;
+typedef struct pdc_chunk_s	pdc_chunk;
+
+struct pdc_link_s		/* for doubly linked free items list	*/
+{
+    int		idx;
+    pdc_link *	prev;		/* previous item in free list		*/
+    pdc_link *	next;		/* next item in free list		*/
+};
+
+
+struct pdc_chunk_s
+{
+    char *	data;		/* the items in this chunk		*/
+    int		n_items;	/* number of used items in this chunk	*/
+
+    pdc_chunk *	next;		/* next chunk in free list		*/
+};
+
+
+struct pdc_hvtr_s
+{
+    pdc_core *	pdc;
+
+    pdc_ced	ced;		/* container entry descriptor		*/
+    void *	context;	/* client context			*/
+
+    pdc_chunk *	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		*/
+
+    pdc_link *	free_items;	/* first item in free items list	*/
+    pdc_link	end_items;	/* sentinel				*/
+    pdc_chunk *	free_chunks;	/* first chunk in free chunks list	*/
+    pdc_chunk	end_chunks;	/* sentinel				*/
+
+    pdc_bvtr *	free_mask;	/* bit mask of free items		*/
+};
+
+
+static const pdc_hvtr_parms hvtr_dflt_parms =
+{
+    100,			/* chunk_size				*/
+    10,				/* ctab_incr				*/
+};
+
+void
+pdc_hvtr_dflt_parms(pdc_hvtr_parms *vp)
+{
+    *vp = hvtr_dflt_parms;
+}
+
+
+pdc_hvtr *
+pdc_hvtr_new(
+    pdc_core *pdc,
+    const pdc_ced *ced,
+    void *context,
+    const pdc_hvtr_parms *parms)
+{
+    static const char fn[] = "pdc_hvtr_new";
+
+    pdc_hvtr *v = (pdc_hvtr *) pdc_malloc(pdc, sizeof (pdc_hvtr), fn);
+
+    if (!parms)
+	parms = &hvtr_dflt_parms;
+
+    v->pdc = pdc;
+    v->ced = *ced;
+    v->context = context ? context : pdc;
+
+    if (v->ced.size < sizeof (pdc_link))
+    {
+	v->ced.size = sizeof (pdc_link);
+    }
+
+    v->ctab = (pdc_chunk *) 0;
+    v->ctab_size = 0;
+    v->ctab_incr = parms->ctab_incr;
+    v->chunk_size = parms->chunk_size;
+    v->size = 0;
+
+    v->free_items = &v->end_items;
+    v->end_items.next = v->end_items.prev = &v->end_items;
+    v->free_chunks = &v->end_chunks;
+    v->free_mask = 0;
+
+    PDC_TRY (pdc)
+    {
+	pdc_bvtr_parms bvp;
+
+	pdc_bvtr_dflt_parms(&bvp);
+	bvp.init_value = pdc_true;
+	v->free_mask = pdc_bvtr_new(pdc, &bvp);
+    }
+    PDC_CATCH (pdc)
+    {
+	pdc_hvtr_delete(v);
+	PDC_RETHROW(pdc);
+    }
+
+    return v;
+} /* pdc_hvtr_new */
+
+
+void
+pdc_hvtr_delete(pdc_hvtr *v)
+{
+    int cs = v->chunk_size;
+    int i;
+
+    if (v->size != 0 && v->ced.release)
+    {
+	for (i = 0; i < v->size; ++i)
+	{
+	    if (!pdc_bvtr_getbit(v->free_mask, i))
+	    {
+		v->ced.release(v->context, (void *)
+		    &v->ctab[i / cs].data[(i % cs) * v->ced.size]);
+	    }
+	}
+    }
+
+    if (v->ctab)
+    {
+	for (i = 0; i < v->ctab_size && v->ctab[i].data != (char *) 0; ++i)
+	{
+	    pdc_free(v->pdc, v->ctab[i].data);
+	}
+
+	pdc_free(v->pdc, v->ctab);
+    }
+
+    if (v->free_mask)
+    {
+	pdc_bvtr_delete(v->free_mask);
+    }
+
+    pdc_free(v->pdc, v);
+} /* pdc_hvtr_delete */
+
+
+void
+pdc_hvtr_release_item(pdc_hvtr *v, int idx)
+{
+    static const char fn[] = "pdc_hvtr_release_item";
+
+    const int	cs = v->chunk_size;
+    pdc_chunk *	chunk = &v->ctab[idx / cs];
+    void *	item;
+    pdc_link *	link;
+
+    if (idx < 0 || v->size <= idx || pdc_bvtr_getbit(v->free_mask, idx))
+    {
+	pdc_error(v->pdc, PDC_E_INT_ARRIDX,
+	    pdc_errprintf(v->pdc, "%d", idx), fn, 0, 0);
+    }
+
+    item = &chunk->data[(idx % cs) * v->ced.size];
+
+    if (v->ced.release)
+    {
+	v->ced.release(v->context, item);
+    }
+
+    pdc_bvtr_setbit(v->free_mask, idx);
+
+    link = (pdc_link *) item;
+    link->idx = idx;
+    link->next = v->free_items;
+    link->prev = &v->end_items;
+    link->next->prev = link->prev->next = link;
+    v->free_items = link;
+
+    if (--chunk->n_items == 0)
+    {
+	for (idx = 0; idx < cs; ++idx)
+	{
+	    link = (pdc_link *) &chunk->data[idx * v->ced.size];
+
+	    link->prev->next = link->next;
+	    link->next->prev = link->prev;
+	}
+
+	pdc_free(v->pdc, chunk->data);
+	chunk->data = 0;
+	chunk->next = v->free_chunks;
+	v->free_chunks = chunk;
+    }
+} /* pdc_hvtr_release_item */
+
+
+int
+pdc_hvtr_reclaim_item(pdc_hvtr *v)
+{
+    static const char fn[] = "pdc_hvtr_reclaim_item";
+
+    pdc_link *	new_item;
+    int		idx;
+
+    if (v->free_items != &v->end_items)
+    {
+	new_item = v->free_items;
+	new_item->prev->next = new_item->next;
+	new_item->next->prev = new_item->prev;
+	v->free_items = new_item->next;
+    }
+    else
+    {
+	/* install new chunk.
+	*/
+	const int	cs = v->chunk_size;
+	const int	es = v->ced.size;
+	pdc_chunk *	new_chunk;
+	pdc_link *	link;
+	int		base;
+
+	if (v->free_chunks != &v->end_chunks)
+	{
+	    new_chunk = v->free_chunks;
+	    v->free_chunks = new_chunk->next;
+	}
+	else
+	{
+	    int new_size = v->ctab_size + v->ctab_incr;
+
+	    v->ctab = (pdc_chunk *) pdc_realloc(v->pdc, v->ctab,
+				(size_t) (new_size * sizeof (pdc_chunk)), fn);
+
+	    for (idx = v->ctab_size; idx < new_size; ++idx)
+	    {
+		v->ctab[idx].data = (char *) 0;
+		v->ctab[idx].n_items = 0;
+		v->ctab[idx].next = &v->ctab[idx + 1];
+	    }
+
+	    v->ctab[new_size - 1].next = &v->end_chunks;
+	    v->free_chunks = &v->ctab[v->ctab_size + 1];
+	    new_chunk = &v->ctab[v->ctab_size];
+	    v->ctab_size = new_size;
+	    v->size += cs * v->ctab_incr;
+	    pdc_bvtr_resize(v->free_mask, v->size);
+	}
+
+	new_chunk->data = pdc_malloc(v->pdc, cs * es, fn);
+	base = cs * (new_chunk - &v->ctab[0]);
+
+	for (idx = 1; idx < cs; ++idx)
+	{
+	    link = (pdc_link *) &new_chunk->data[idx * es];
+
+	    link->idx = base + idx;
+	    link->prev = (pdc_link *) &new_chunk->data[(idx - 1) * es];
+	    link->next = (pdc_link *) &new_chunk->data[(idx + 1) * es];
+	}
+
+	/* end of new chain:
+	*/
+	link = (pdc_link *) &new_chunk->data[(cs - 1) * es];
+	link->next = v->free_items;
+	link->next->prev = link;
+
+	/* start of new chain:
+	*/
+	link = (pdc_link *) &new_chunk->data[1 * es];
+	link->prev = &v->end_items;
+	v->free_items = v->end_items.next = link;
+
+	new_item = (pdc_link *) &new_chunk->data[0];
+	new_item->idx = base;
+    }
+
+    idx = new_item->idx;
+    pdc_bvtr_clrbit(v->free_mask, idx);
+
+    if (v->ced.reclaim)
+    {
+	v->ced.reclaim((void *) new_item);
+    }
+
+    return idx;
+} /* pdc_hvtr_reclaim_item */
+
+
+pdc_bool
+pdc_hvtr_check_idx(const pdc_hvtr *v, int idx)
+{
+    return 0 <= idx && idx < v->size && !pdc_bvtr_getbit(v->free_mask, idx);
+} /* pdc__hvtr_at */
+
+
+void *
+pdc__hvtr_at(const pdc_hvtr *v, int idx)
+{
+    static const char fn[] = "pdc__hvtr_at";
+
+    int cs = v->chunk_size;
+
+    if (idx < 0 || v->size <= idx || pdc_bvtr_getbit(v->free_mask, idx))
+    {
+	pdc_error(v->pdc, PDC_E_INT_ARRIDX,
+	    pdc_errprintf(v->pdc, "%d", idx), fn, 0, 0);
+    }
+
+    return (void *) &v->ctab[idx / cs].data[(idx % cs) * v->ced.size];
+} /* pdc__hvtr_at */
-- 
cgit v1.2.3