heimdal Extra files required for merge up to current heimdal

10 files changed, 1806 insertions, 0 deletions

diff --git a/source4/heimdal/base/array.c b/source4/heimdal/base/array.c
new file mode 100644
index 0000000000..7b0d77b1cc
--- /dev/null
+++ b/source4/heimdal/base/array.c
@@ -0,0 +1,234 @@
+/*
+ * Copyright (c) 2010 Kungliga Tekniska Högskolan
+ * (Royal Institute of Technology, Stockholm, Sweden).
+ * All rights reserved.
+ *
+ * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of the Institute nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include "baselocl.h"
+
+/*
+ *
+ */
+
+struct heim_array_data {
+    size_t len;
+    heim_object_t *val;
+};
+
+static void
+array_dealloc(heim_object_t ptr)
+{
+    heim_array_t array = ptr;
+    size_t n;
+    for (n = 0; n < array->len; n++)
+	heim_release(array->val[n]);
+    free(array->val);
+}
+
+struct heim_type_data array_object = {
+    HEIM_TID_ARRAY,
+    "dict-object",
+    NULL,
+    array_dealloc,
+    NULL,
+    NULL,
+    NULL
+};
+
+/**
+ * Allocate an array
+ *
+ * @return A new allocated array, free with heim_release()
+ */
+
+heim_array_t
+heim_array_create(void)
+{
+    heim_array_t array;
+
+    array = _heim_alloc_object(&array_object, sizeof(*array));
+    if (array == NULL)
+	return NULL;
+
+    array->val = NULL;
+    array->len = 0;
+
+    return array;
+}
+
+/**
+ * Get type id of an dict
+ *
+ * @return the type id
+ */
+
+heim_tid_t
+heim_array_get_type_id(void)
+{
+    return HEIM_TID_ARRAY;
+}
+
+/**
+ * Append object to array
+ *
+ * @param array array to add too
+ * @param object the object to add
+ *
+ * @return zero if added, errno otherwise
+ */
+
+int
+heim_array_append_value(heim_array_t array, heim_object_t object)
+{
+    heim_object_t *ptr;
+
+    ptr = realloc(array->val, (array->len + 1) * sizeof(array->val[0]));
+    if (ptr == NULL)
+	return ENOMEM;
+    array->val = ptr;
+    array->val[array->len++] = heim_retain(object);
+
+    return 0;
+}
+
+/**
+ * Iterate over all objects in array
+ *
+ * @param array array to iterate over
+ * @param fn function to call on each object
+ * @param ctx context passed to fn
+ */
+
+void
+heim_array_iterate_f(heim_array_t array, heim_array_iterator_f_t fn, void *ctx)
+{
+    size_t n;
+    for (n = 0; n < array->len; n++)
+	fn(array->val[n], ctx);
+}
+
+#ifdef __BLOCKS__
+/**
+ * Iterate over all objects in array
+ *
+ * @param array array to iterate over
+ * @param fn block to call on each object
+ */
+
+void
+heim_array_iterate(heim_array_t array, void (^fn)(heim_object_t))
+{
+    size_t n;
+    for (n = 0; n < array->len; n++)
+	fn(array->val[n]);
+}
+#endif
+
+/**
+ * Get length of array
+ *
+ * @param array array to get length of
+ *
+ * @return length of array
+ */
+
+size_t
+heim_array_get_length(heim_array_t array)
+{
+    return array->len;
+}
+
+/**
+ * Copy value of array
+ *
+ * @param array array copy object from
+ * @param idx index of object, 0 based, must be smaller then
+ *        heim_array_get_length()
+ *
+ * @return a retained copy of the object
+ */
+
+heim_object_t
+heim_array_copy_value(heim_array_t array, size_t idx)
+{
+    if (idx >= array->len)
+	heim_abort("index too large");
+    return heim_retain(array->val[idx]);
+}
+
+/**
+ * Delete value at idx
+ *
+ * @param array the array to modify
+ * @param idx the key to delete
+ */
+
+void
+heim_array_delete_value(heim_array_t array, size_t idx)
+{
+    heim_object_t obj;
+    if (idx >= array->len)
+	heim_abort("index too large");
+    obj = array->val[idx];
+
+    array->len--;
+
+    if (idx < array->len)
+	memmove(&array->val[idx], &array->val[idx + 1],
+		(array->len - idx) * sizeof(array->val[0]));
+
+    heim_release(obj);
+}
+
+#ifdef __BLOCKS__
+/**
+ * Get value at idx
+ *
+ * @param array the array to modify
+ * @param idx the key to delete
+ */
+
+void
+heim_array_filter(heim_array_t array, bool (^block)(heim_object_t))
+{
+    size_t n = 0;
+
+    while (n < array->len) {
+	if (block(array->val[n])) {
+	    heim_array_delete_value(array, n);
+	} else {
+	    n++;
+	}
+    }
+}
+
+#endif /* __BLOCKS__ */
diff --git a/source4/heimdal/base/baselocl.h b/source4/heimdal/base/baselocl.h
new file mode 100644
index 0000000000..3932378b2d
--- /dev/null
+++ b/source4/heimdal/base/baselocl.h
@@ -0,0 +1,90 @@
+/*
+ * Copyright (c) 2010 Kungliga Tekniska Högskolan
+ * (Royal Institute of Technology, Stockholm, Sweden).
+ * All rights reserved.
+ *
+ * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of the Institute nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <limits.h>
+#include <unistd.h>
+
+#include "config.h"
+
+#include "heimqueue.h"
+#include "heim_threads.h"
+#include "heimbase.h"
+#include "heimbasepriv.h"
+
+#ifdef HAVE_DISPATCH_DISPATCH_H
+#include <dispatch/dispatch.h>
+#endif
+
+#ifdef __GNUC__
+#define heim_base_atomic_inc(x) __sync_add_and_fetch((x), 1)
+#define heim_base_atomic_dec(x) __sync_sub_and_fetch((x), 1)
+#define heim_base_atomic_type	unsigned int
+#define heim_base_atomic_max    UINT_MAX
+
+#define heim_base_exchange_pointer(t,v) __sync_lock_test_and_set((t), (v))
+
+#elif 0 /* windows */
+
+#define heim_base_exchange_pointer(t,v) InterlockedExchangePointer((t),(v))
+
+#else
+#error "provide atomic integer operations for your compiler"
+#endif
+
+/* tagged strings/object/XXX */
+#define heim_base_is_tagged(x) (((uintptr_t)(x)) & 0x3)
+
+#define heim_base_is_tagged_string(x) ((((uintptr_t)(x)) & 0x3) == 2)
+#define heim_base_make_tagged_string_ptr(x) ((heim_object_t)(((uintptr_t)(x)) | 2))
+#define heim_base_tagged_string_ptr(x) ((char *)(((uintptr_t)(x)) & (~3)))
+
+
+#define heim_base_is_tagged_object(x) ((((uintptr_t)(x)) & 0x3) == 1)
+#define heim_base_make_tagged_object(x, tid) \
+    ((heim_object_t)((((uintptr_t)(x)) << 5) | ((tid) << 2) | 0x1))
+#define heim_base_tagged_object_tid(x) ((((uintptr_t)(x)) & 0x1f) >> 2)
+#define heim_base_tagged_object_value(x) (((uintptr_t)(x)) >> 5)
+
+/*
+ *
+ */
+
+#undef HEIMDAL_NORETURN_ATTRIBUTE
+#define HEIMDAL_NORETURN_ATTRIBUTE
+#undef HEIMDAL_PRINTF_ATTRIBUTE
+#define HEIMDAL_PRINTF_ATTRIBUTE(x)
diff --git a/source4/heimdal/base/bool.c b/source4/heimdal/base/bool.c
new file mode 100644
index 0000000000..72edcc71ed
--- /dev/null
+++ b/source4/heimdal/base/bool.c
@@ -0,0 +1,58 @@
+/*
+ * Copyright (c) 2010 Kungliga Tekniska Högskolan
+ * (Royal Institute of Technology, Stockholm, Sweden).
+ * All rights reserved.
+ *
+ * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of the Institute nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include "baselocl.h"
+
+struct heim_type_data _heim_bool_object = {
+    HEIM_TID_BOOL,
+    "bool-object",
+    NULL,
+    NULL,
+    NULL,
+    NULL,
+    NULL
+};
+
+heim_bool_t
+heim_bool_create(int val)
+{
+    return heim_base_make_tagged_object(!!val, HEIM_TID_BOOL);
+}
+
+int
+heim_bool_val(heim_bool_t ptr)
+{
+    return heim_base_tagged_object_value(ptr);
+}
diff --git a/source4/heimdal/base/dict.c b/source4/heimdal/base/dict.c
new file mode 100644
index 0000000000..2eb57aa938
--- /dev/null
+++ b/source4/heimdal/base/dict.c
@@ -0,0 +1,282 @@
+/*
+ * Copyright (c) 2002, 1997 Kungliga Tekniska Högskolan
+ * (Royal Institute of Technology, Stockholm, Sweden).
+ * All rights reserved.
+ *
+ * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of the Institute nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include "baselocl.h"
+
+struct hashentry {
+    struct hashentry **prev;
+    struct hashentry *next;
+    heim_object_t key;
+    heim_object_t value;
+};
+
+struct heim_dict_data {
+    size_t size;
+    struct hashentry **tab;
+};
+
+static void
+dict_dealloc(void *ptr)
+{
+    heim_dict_t dict = ptr;
+    struct hashentry **h, *g, *i;
+
+    for (h = dict->tab; h < &dict->tab[dict->size]; ++h) {
+	for (g = h[0]; g; g = i) {
+	    i = g->next;
+	    heim_release(g->key);
+	    heim_release(g->value);
+	    free(g);
+	}
+    }
+    free(dict->tab);
+}
+
+struct heim_type_data dict_object = {
+    HEIM_TID_DICT,
+    "dict-object",
+    NULL,
+    dict_dealloc,
+    NULL,
+    NULL,
+    NULL
+};
+
+static size_t
+isprime(size_t p)
+{
+    int q, i;
+
+    for(i = 2 ; i < p; i++) {
+	q = p / i;
+
+	if (i * q == p)
+	    return 0;
+	if (i * i > p)
+	    return 1;
+    }
+    return 1;
+}
+
+static size_t
+findprime(size_t p)
+{
+    if (p % 2 == 0)
+	p++;
+
+    while (isprime(p) == 0)
+	p += 2;
+
+    return p;
+}
+
+/**
+ * Allocate an array
+ *
+ * @return A new allocated array, free with heim_release()
+ */
+
+heim_dict_t
+heim_dict_create(size_t size)
+{
+    heim_dict_t dict;
+
+    dict = _heim_alloc_object(&dict_object, sizeof(*dict));
+
+    dict->size = findprime(size);
+    if (dict->size == 0) {
+	heim_release(dict);
+	return NULL;
+    }
+
+    dict->tab = calloc(dict->size, sizeof(dict->tab[0]));
+    if (dict->tab == NULL) {
+	dict->size = 0;
+	heim_release(dict);
+	return NULL;
+    }
+
+    return dict;
+}
+
+/**
+ * Get type id of an dict
+ *
+ * @return the type id
+ */
+
+heim_tid_t
+heim_dict_get_type_id(void)
+{
+    return HEIM_TID_DICT;
+}
+
+/* Intern search function */
+
+static struct hashentry *
+_search(heim_dict_t dict, heim_object_t ptr)
+{
+    unsigned long v = heim_get_hash(ptr);
+    struct hashentry *p;
+
+    for (p = dict->tab[v % dict->size]; p != NULL; p = p->next)
+	if (heim_cmp(ptr, p->key) == 0)
+	    return p;
+
+    return NULL;
+}
+
+/**
+ * Search for element in hash table
+ *
+ * @value dict the dict to search in
+ * @value key the key to search for
+ *
+ * @return a retained copy of the value for key or NULL if not found
+ */
+
+heim_object_t
+heim_dict_copy_value(heim_dict_t dict, heim_object_t key)
+{
+    struct hashentry *p;
+    p = _search(dict, key);
+    if (p == NULL)
+	return NULL;
+
+    return heim_retain(p->value);
+}
+
+/**
+ * Add key and value to dict
+ *
+ * @value dict the dict to add too
+ * @value key the key to add
+ * @value value the value to add
+ *
+ * @return 0 if added, errno if not
+ */
+
+int
+heim_dict_add_value(heim_dict_t dict, heim_object_t key, heim_object_t value)
+{
+    struct hashentry **tabptr, *h;
+
+    h = _search(dict, key);
+    if (h) {
+	heim_release(h->value);
+	h->value = heim_retain(value);
+    } else {
+	unsigned long v;
+
+	h = malloc(sizeof(*h));
+	if (h == NULL)
+	    return ENOMEM;
+
+	h->key = heim_retain(key);
+	h->value = heim_retain(value);
+
+	v = heim_get_hash(key);
+
+	tabptr = &dict->tab[v % dict->size];
+	h->next = *tabptr;
+	*tabptr = h;
+	h->prev = tabptr;
+	if (h->next)
+	    h->next->prev = &h->next;
+    }
+
+    return 0;
+}
+
+/**
+ * Delete element with key key
+ *
+ * @value dict the dict to delete from
+ * @value key the key to delete
+ */
+
+void
+heim_dict_delete_key(heim_dict_t dict, heim_object_t key)
+{
+    struct hashentry *h = _search(dict, key);
+
+    if (h == NULL)
+	return;
+
+    heim_release(h->key);
+    heim_release(h->value);
+
+    if ((*(h->prev) = h->next) != NULL)
+	h->next->prev = h->prev;
+
+    free(h);
+}
+
+/**
+ * Do something for each element
+ *
+ * @value dict the dict to interate over
+ * @value func the function to search for
+ * @value arg argument to func
+ */
+
+void
+heim_dict_iterate_f(heim_dict_t dict, heim_dict_iterator_f_t func, void *arg)
+{
+    struct hashentry **h, *g;
+
+    for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
+	for (g = *h; g; g = g->next)
+	    func(g->key, g->value, arg);
+}
+
+#ifdef __BLOCKS__
+/**
+ * Do something for each element
+ *
+ * @value dict the dict to interate over
+ * @value func the function to search for
+ */
+
+void
+heim_dict_iterate(heim_dict_t dict, void (^func)(heim_object_t, heim_object_t))
+{
+    struct hashentry **h, *g;
+
+    for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
+	for (g = *h; g; g = g->next)
+	    func(g->key, g->value);
+}
+#endif
diff --git a/source4/heimdal/base/heimbase.c b/source4/heimdal/base/heimbase.c
new file mode 100644
index 0000000000..a6caad2baf
--- /dev/null
+++ b/source4/heimdal/base/heimbase.c
@@ -0,0 +1,559 @@
+/*
+ * Copyright (c) 2010 Kungliga Tekniska Högskolan
+ * (Royal Institute of Technology, Stockholm, Sweden).
+ * All rights reserved.
+ *
+ * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of the Institute nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include "baselocl.h"
+#include <syslog.h>
+
+static heim_base_atomic_type tidglobal = HEIM_TID_USER;
+
+struct heim_base {
+    heim_type_t isa;
+    heim_base_atomic_type ref_cnt;
+    HEIM_TAILQ_ENTRY(heim_base) autorel;
+    heim_auto_release_t autorelpool;
+    uintptr_t isaextra[3];
+};
+
+/* specialized version of base */
+struct heim_base_mem {
+    heim_type_t isa;
+    heim_base_atomic_type ref_cnt;
+    HEIM_TAILQ_ENTRY(heim_base) autorel;
+    heim_auto_release_t autorelpool;
+    const char *name;
+    void (*dealloc)(void *);
+    uintptr_t isaextra[1];
+};
+
+#define PTR2BASE(ptr) (((struct heim_base *)ptr) - 1)
+#define BASE2PTR(ptr) ((void *)(((struct heim_base *)ptr) + 1))
+
+/*
+ * Auto release structure
+ */
+
+struct heim_auto_release {
+    HEIM_TAILQ_HEAD(, heim_base) pool;
+    HEIMDAL_MUTEX pool_mutex;
+    struct heim_auto_release *parent;
+};
+
+
+/**
+ * Retain object
+ *
+ * @param object to be released, NULL is ok
+ *
+ * @return the same object as passed in
+ */
+
+void *
+heim_retain(void *ptr)
+{
+    struct heim_base *p = PTR2BASE(ptr);
+
+    if (ptr == NULL || heim_base_is_tagged(ptr))
+	return ptr;
+
+    if (p->ref_cnt == heim_base_atomic_max)
+	return ptr;
+
+    if ((heim_base_atomic_inc(&p->ref_cnt) - 1) == 0)
+	heim_abort("resurection");
+    return ptr;
+}
+
+/**
+ * Release object, free is reference count reaches zero
+ *
+ * @param object to be released
+ */
+
+void
+heim_release(void *ptr)
+{
+    heim_base_atomic_type old;
+    struct heim_base *p = PTR2BASE(ptr);
+
+    if (ptr == NULL || heim_base_is_tagged(ptr))
+	return;
+
+    if (p->ref_cnt == heim_base_atomic_max)
+	return;
+
+    old = heim_base_atomic_dec(&p->ref_cnt) + 1;
+
+    if (old > 1)
+	return;
+
+    if (old == 1) {
+	heim_auto_release_t ar = p->autorelpool;
+	/* remove from autorel pool list */
+	if (ar) {
+	    p->autorelpool = NULL;
+	    HEIMDAL_MUTEX_lock(&ar->pool_mutex);
+	    HEIM_TAILQ_REMOVE(&ar->pool, p, autorel);
+	    HEIMDAL_MUTEX_unlock(&ar->pool_mutex);
+	}
+	if (p->isa->dealloc)
+	    p->isa->dealloc(ptr);
+	free(p);
+    } else
+	heim_abort("over release");
+}
+
+static heim_type_t tagged_isa[9] = {
+    &_heim_number_object,
+    &_heim_null_object,
+    &_heim_bool_object,
+
+    NULL,
+    NULL,
+    NULL,
+
+    NULL,
+    NULL,
+    NULL
+};
+
+heim_type_t
+_heim_get_isa(heim_object_t ptr)
+{
+    struct heim_base *p;
+    if (heim_base_is_tagged(ptr)) {
+	if (heim_base_is_tagged_object(ptr))
+	    return tagged_isa[heim_base_tagged_object_tid(ptr)];
+	if (heim_base_is_tagged_string(ptr))
+	    return &_heim_string_object;
+	heim_abort("not a supported tagged type");
+    }
+    p = PTR2BASE(ptr);
+    return p->isa;
+}
+
+/**
+ * Get type ID of object
+ *
+ * @param object object to get type id of
+ *
+ * @return type id of object
+ */
+
+heim_tid_t
+heim_get_tid(heim_object_t ptr)
+{
+    heim_type_t isa = _heim_get_isa(ptr);
+    return isa->tid;
+}
+
+/**
+ * Get hash value of object
+ *
+ * @param object object to get hash value for
+ *
+ * @return a hash value
+ */
+
+unsigned long
+heim_get_hash(heim_object_t ptr)
+{
+    heim_type_t isa = _heim_get_isa(ptr);
+    if (isa->hash)
+	return isa->hash(ptr);
+    return (unsigned long)ptr;
+}
+
+/**
+ * Compare two objects, returns 0 if equal, can use used for qsort()
+ * and friends.
+ *
+ * @param a first object to compare
+ * @param b first object to compare
+ *
+ * @return 0 if objects are equal
+ */
+
+int
+heim_cmp(heim_object_t a, heim_object_t b)
+{
+    heim_tid_t ta, tb;
+    heim_type_t isa;
+
+    ta = heim_get_tid(a);
+    tb = heim_get_tid(b);
+
+    if (ta != tb)
+	return ta - tb;
+
+    isa = _heim_get_isa(a);
+
+    if (isa->cmp)
+	return isa->cmp(a, b);
+
+    return (uintptr_t)a - (uintptr_t)b;
+}
+
+/*
+ * Private - allocates an memory object
+ */
+
+static void
+memory_dealloc(void *ptr)
+{
+    struct heim_base_mem *p = (struct heim_base_mem *)PTR2BASE(ptr);
+    if (p->dealloc)
+	p->dealloc(ptr);
+}
+
+struct heim_type_data memory_object = {
+    HEIM_TID_MEMORY,
+    "memory-object",
+    NULL,
+    memory_dealloc,
+    NULL,
+    NULL,
+    NULL
+};
+
+void *
+heim_alloc(size_t size, const char *name, heim_type_dealloc dealloc)
+{
+    /* XXX use posix_memalign */
+
+    struct heim_base_mem *p = calloc(1, size + sizeof(*p));
+    if (p == NULL)
+	return NULL;
+    p->isa = &memory_object;
+    p->ref_cnt = 1;
+    p->name = name;
+    p->dealloc = dealloc;
+    return BASE2PTR(p);
+}
+
+heim_type_t
+_heim_create_type(const char *name,
+		  heim_type_init init,
+		  heim_type_dealloc dealloc,
+		  heim_type_copy copy,
+		  heim_type_cmp cmp,
+		  heim_type_hash hash)
+{
+    heim_type_t type;
+
+    type = calloc(1, sizeof(*type));
+    if (type == NULL)
+	return NULL;
+
+    type->tid = heim_base_atomic_inc(&tidglobal);
+    type->name = name;
+    type->init = init;
+    type->dealloc = dealloc;
+    type->copy = copy;
+    type->cmp = cmp;
+    type->hash = hash;
+
+    return type;
+}
+
+heim_object_t
+_heim_alloc_object(heim_type_t type, size_t size)
+{
+    /* XXX should use posix_memalign */
+    struct heim_base *p = calloc(1, size + sizeof(*p));
+    if (p == NULL)
+	return NULL;
+    p->isa = type;
+    p->ref_cnt = 1;
+
+    return BASE2PTR(p);
+}
+
+heim_tid_t
+_heim_type_get_tid(heim_type_t type)
+{
+    return type->tid;
+}
+
+/**
+ * Call func once and only once
+ *
+ * @param once pointer to a heim_base_once_t
+ * @param ctx context passed to func
+ * @param func function to be called
+ */
+
+void
+heim_base_once_f(heim_base_once_t *once, void *ctx, void (*func)(void *))
+{
+#ifdef HAVE_DISPATCH_DISPATCH_H
+    dispatch_once_f(once, ctx, func);
+#else
+    static HEIMDAL_MUTEX mutex = HEIMDAL_MUTEX_INITIALIZER;
+    HEIMDAL_MUTEX_lock(&mutex);
+    if (*once == 0) {
+	*once = 1;
+	HEIMDAL_MUTEX_unlock(&mutex);
+	func(ctx);
+	HEIMDAL_MUTEX_lock(&mutex);
+	*once = 2;
+	HEIMDAL_MUTEX_unlock(&mutex);
+    } else if (*once == 2) {
+	HEIMDAL_MUTEX_unlock(&mutex);
+    } else {
+	HEIMDAL_MUTEX_unlock(&mutex);
+	while (1) {
+	    struct timeval tv = { 0, 1000 };
+	    HEIMDAL_MUTEX_lock(&mutex);
+	    if (*once == 2)
+		break;
+	    HEIMDAL_MUTEX_unlock(&mutex);
+	}
+	HEIMDAL_MUTEX_unlock(&mutex);
+    }
+#endif
+}
+
+/**
+ * Abort and log the failure (using syslog)
+ */
+
+void
+heim_abort(const char *fmt, ...)
+{
+    va_list ap;
+    va_start(ap, fmt);
+    heim_abortv(fmt, ap);
+    va_end(ap);
+}
+
+/**
+ * Abort and log the failure (using syslog)
+ */
+
+void
+heim_abortv(const char *fmt, va_list ap)
+{
+    char *str = NULL;
+    int ret;
+
+    ret = vasprintf(&str, fmt, ap);
+    if (ret > 0 && str) {
+	syslog(LOG_ERR, "heim_abort: %s", str);
+    }
+    abort();
+}
+
+/*
+ *
+ */
+
+static int ar_created = 0;
+static HEIMDAL_thread_key ar_key;
+
+struct ar_tls {
+    struct heim_auto_release *head;
+    struct heim_auto_release *current;
+    HEIMDAL_MUTEX tls_mutex;
+};
+
+static void
+ar_tls_delete(void *ptr)
+{
+    struct ar_tls *tls = ptr;
+    if (tls->head)
+	heim_release(tls->head);
+    free(tls);
+}
+
+static void
+init_ar_tls(void *ptr)
+{
+    int ret;
+    HEIMDAL_key_create(&ar_key, ar_tls_delete, ret);
+    if (ret == 0)
+	ar_created = 1;
+}
+
+static struct ar_tls *
+autorel_tls(void)
+{
+    static heim_base_once_t once = HEIM_BASE_ONCE_INIT;
+    struct ar_tls *arp;
+    int ret;
+
+    heim_base_once_f(&once, NULL, init_ar_tls);
+    if (!ar_created)
+	return NULL;
+
+    arp = HEIMDAL_getspecific(ar_key);
+    if (arp == NULL) {
+
+	arp = calloc(1, sizeof(*arp));
+	if (arp == NULL)
+	    return NULL;
+	HEIMDAL_setspecific(ar_key, arp, ret);
+	if (ret) {
+	    free(arp);
+	    return NULL;
+	}
+    }
+    return arp;
+
+}
+
+static void
+autorel_dealloc(void *ptr)
+{
+    heim_auto_release_t ar = ptr;
+    struct ar_tls *tls;
+
+    tls = autorel_tls();
+    if (tls == NULL)
+	heim_abort("autorelease pool released on thread w/o autorelease inited");
+
+    heim_auto_release_drain(ar);
+
+    if (!HEIM_TAILQ_EMPTY(&ar->pool))
+	heim_abort("pool not empty after draining");
+
+    HEIMDAL_MUTEX_lock(&tls->tls_mutex);
+    if (tls->current != ptr)
+	heim_abort("autorelease not releaseing top pool");
+
+    if (tls->current != tls->head)
+	tls->current = ar->parent;
+    HEIMDAL_MUTEX_unlock(&tls->tls_mutex);
+}
+
+static int
+autorel_cmp(void *a, void *b)
+{
+    return (a == b);
+}
+
+static unsigned long
+autorel_hash(void *ptr)
+{
+    return (unsigned long)ptr;
+}
+
+
+static struct heim_type_data _heim_autorel_object = {
+    HEIM_TID_AUTORELEASE,
+    "autorelease-pool",
+    NULL,
+    autorel_dealloc,
+    NULL,
+    autorel_cmp,
+    autorel_hash
+};
+
+/**
+ *
+ */
+
+heim_auto_release_t
+heim_auto_release_create(void)
+{
+    struct ar_tls *tls = autorel_tls();
+    heim_auto_release_t ar;
+
+    if (tls == NULL)
+	heim_abort("Failed to create/get autorelease head");
+
+    ar = _heim_alloc_object(&_heim_autorel_object, sizeof(struct heim_auto_release));
+    if (ar) {
+	HEIMDAL_MUTEX_lock(&tls->tls_mutex);
+	if (tls->head == NULL)
+	    tls->head = ar;
+	ar->parent = tls->current;
+	tls->current = ar;
+	HEIMDAL_MUTEX_unlock(&tls->tls_mutex);
+    }
+
+    return ar;
+}
+
+/**
+ * Mark the current object as a
+ */
+
+void
+heim_auto_release(heim_object_t ptr)
+{
+    struct heim_base *p = PTR2BASE(ptr);
+    struct ar_tls *tls = autorel_tls();
+    heim_auto_release_t ar;
+
+    if (ptr == NULL || heim_base_is_tagged(ptr))
+	return;
+
+    /* drop from old pool */
+    if ((ar = p->autorelpool) != NULL) {
+	HEIMDAL_MUTEX_lock(&ar->pool_mutex);
+	HEIM_TAILQ_REMOVE(&ar->pool, p, autorel);
+	p->autorelpool = NULL;
+	HEIMDAL_MUTEX_unlock(&ar->pool_mutex);
+    }
+
+    if (tls == NULL || (ar = tls->current) == NULL)
+	heim_abort("no auto relase pool in place, would leak");
+
+    HEIMDAL_MUTEX_lock(&ar->pool_mutex);
+    HEIM_TAILQ_INSERT_HEAD(&ar->pool, p, autorel);
+    p->autorelpool = ar;
+    HEIMDAL_MUTEX_unlock(&ar->pool_mutex);
+}
+
+/**
+ *
+ */
+
+void
+heim_auto_release_drain(heim_auto_release_t autorel)
+{
+    heim_object_t obj;
+
+    /* release all elements on the tail queue */
+
+    HEIMDAL_MUTEX_lock(&autorel->pool_mutex);
+    while(!HEIM_TAILQ_EMPTY(&autorel->pool)) {
+	obj = HEIM_TAILQ_FIRST(&autorel->pool);
+	HEIMDAL_MUTEX_unlock(&autorel->pool_mutex);
+	heim_release(BASE2PTR(obj));
+	HEIMDAL_MUTEX_lock(&autorel->pool_mutex);
+    }
+    HEIMDAL_MUTEX_unlock(&autorel->pool_mutex);
+}
diff --git a/source4/heimdal/base/heimbasepriv.h b/source4/heimdal/base/heimbasepriv.h
new file mode 100644
index 0000000000..772962548f
--- /dev/null
+++ b/source4/heimdal/base/heimbasepriv.h
@@ -0,0 +1,91 @@
+/*
+ * Copyright (c) 2010 Kungliga Tekniska Högskolan
+ * (Royal Institute of Technology, Stockholm, Sweden).
+ * All rights reserved.
+ *
+ * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of the Institute nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+typedef void (*heim_type_init)(void *);
+typedef heim_object_t (*heim_type_copy)(void *);
+typedef int (*heim_type_cmp)(void *, void *);
+typedef unsigned long (*heim_type_hash)(void *);
+
+typedef struct heim_type_data *heim_type_t;
+
+enum {
+    HEIM_TID_NUMBER = 0,
+    HEIM_TID_NULL = 1,
+    HEIM_TID_BOOL = 2,
+    HEIM_TID_TAGGED_UNUSED2 = 3,
+    HEIM_TID_TAGGED_UNUSED3 = 4,
+    HEIM_TID_TAGGED_UNUSED4 = 5,
+    HEIM_TID_TAGGED_UNUSED5 = 6,
+    HEIM_TID_TAGGED_UNUSED6 = 7,
+    HEIM_TID_MEMORY = 128,
+    HEIM_TID_ARRAY = 129,
+    HEIM_TID_DICT = 130,
+    HEIM_TID_STRING = 131,
+    HEIM_TID_AUTORELEASE = 132,
+    HEIM_TID_USER = 255
+
+};
+
+struct heim_type_data {
+    heim_tid_t tid;
+    const char *name;
+    heim_type_init init;
+    heim_type_dealloc dealloc;
+    heim_type_copy copy;
+    heim_type_cmp cmp;
+    heim_type_hash hash;
+};
+
+heim_type_t _heim_get_isa(heim_object_t);
+
+heim_type_t
+_heim_create_type(const char *name,
+		  heim_type_init init,
+		  heim_type_dealloc dealloc,
+		  heim_type_copy copy,
+		  heim_type_cmp cmp,
+		  heim_type_hash hash);
+
+heim_object_t
+_heim_alloc_object(heim_type_t type, size_t size);
+
+heim_tid_t
+_heim_type_get_tid(heim_type_t type);
+
+/* tagged tid */
+extern struct heim_type_data _heim_null_object;
+extern struct heim_type_data _heim_bool_object;
+extern struct heim_type_data _heim_number_object;
+extern struct heim_type_data _heim_string_object;
diff --git a/source4/heimdal/base/heimqueue.h b/source4/heimdal/base/heimqueue.h
new file mode 100644
index 0000000000..423a684787
--- /dev/null
+++ b/source4/heimdal/base/heimqueue.h
@@ -0,0 +1,167 @@
+/*	$NetBSD: queue.h,v 1.38 2004/04/18 14:12:05 lukem Exp $	*/
+/*	$Id$ */
+
+/*
+ * Copyright (c) 1991, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *	@(#)queue.h	8.5 (Berkeley) 8/20/94
+ */
+
+#ifndef	_HEIM_QUEUE_H_
+#define	_HEIM_QUEUE_H_
+
+/*
+ * Tail queue definitions.
+ */
+#define	HEIM_TAILQ_HEAD(name, type)					\
+struct name {								\
+	struct type *tqh_first;	/* first element */			\
+	struct type **tqh_last;	/* addr of last next element */		\
+}
+
+#define	HEIM_TAILQ_HEAD_INITIALIZER(head)				\
+	{ NULL, &(head).tqh_first }
+#define	HEIM_TAILQ_ENTRY(type)						\
+struct {								\
+	struct type *tqe_next;	/* next element */			\
+	struct type **tqe_prev;	/* address of previous next element */	\
+}
+
+/*
+ * Tail queue functions.
+ */
+#if defined(_KERNEL) && defined(QUEUEDEBUG)
+#define	QUEUEDEBUG_HEIM_TAILQ_INSERT_HEAD(head, elm, field)		\
+	if ((head)->tqh_first &&					\
+	    (head)->tqh_first->field.tqe_prev != &(head)->tqh_first)	\
+		panic("HEIM_TAILQ_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
+#define	QUEUEDEBUG_HEIM_TAILQ_INSERT_TAIL(head, elm, field)		\
+	if (*(head)->tqh_last != NULL)					\
+		panic("HEIM_TAILQ_INSERT_TAIL %p %s:%d", (head), __FILE__, __LINE__);
+#define	QUEUEDEBUG_HEIM_TAILQ_OP(elm, field)				\
+	if ((elm)->field.tqe_next &&					\
+	    (elm)->field.tqe_next->field.tqe_prev !=			\
+	    &(elm)->field.tqe_next)					\
+		panic("HEIM_TAILQ_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
+	if (*(elm)->field.tqe_prev != (elm))				\
+		panic("HEIM_TAILQ_* back %p %s:%d", (elm), __FILE__, __LINE__);
+#define	QUEUEDEBUG_HEIM_TAILQ_PREREMOVE(head, elm, field)		\
+	if ((elm)->field.tqe_next == NULL &&				\
+	    (head)->tqh_last != &(elm)->field.tqe_next)			\
+		panic("HEIM_TAILQ_PREREMOVE head %p elm %p %s:%d",	\
+		      (head), (elm), __FILE__, __LINE__);
+#define	QUEUEDEBUG_HEIM_TAILQ_POSTREMOVE(elm, field)			\
+	(elm)->field.tqe_next = (void *)1L;				\
+	(elm)->field.tqe_prev = (void *)1L;
+#else
+#define	QUEUEDEBUG_HEIM_TAILQ_INSERT_HEAD(head, elm, field)
+#define	QUEUEDEBUG_HEIM_TAILQ_INSERT_TAIL(head, elm, field)
+#define	QUEUEDEBUG_HEIM_TAILQ_OP(elm, field)
+#define	QUEUEDEBUG_HEIM_TAILQ_PREREMOVE(head, elm, field)
+#define	QUEUEDEBUG_HEIM_TAILQ_POSTREMOVE(elm, field)
+#endif
+
+#define	HEIM_TAILQ_INIT(head) do {					\
+	(head)->tqh_first = NULL;					\
+	(head)->tqh_last = &(head)->tqh_first;				\
+} while (/*CONSTCOND*/0)
+
+#define	HEIM_TAILQ_INSERT_HEAD(head, elm, field) do {			\
+	QUEUEDEBUG_HEIM_TAILQ_INSERT_HEAD((head), (elm), field)		\
+	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
+		(head)->tqh_first->field.tqe_prev =			\
+		    &(elm)->field.tqe_next;				\
+	else								\
+		(head)->tqh_last = &(elm)->field.tqe_next;		\
+	(head)->tqh_first = (elm);					\
+	(elm)->field.tqe_prev = &(head)->tqh_first;			\
+} while (/*CONSTCOND*/0)
+
+#define	HEIM_TAILQ_INSERT_TAIL(head, elm, field) do {			\
+	QUEUEDEBUG_HEIM_TAILQ_INSERT_TAIL((head), (elm), field)		\
+	(elm)->field.tqe_next = NULL;					\
+	(elm)->field.tqe_prev = (head)->tqh_last;			\
+	*(head)->tqh_last = (elm);					\
+	(head)->tqh_last = &(elm)->field.tqe_next;			\
+} while (/*CONSTCOND*/0)
+
+#define	HEIM_TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
+	QUEUEDEBUG_HEIM_TAILQ_OP((listelm), field)			\
+	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
+		(elm)->field.tqe_next->field.tqe_prev = 		\
+		    &(elm)->field.tqe_next;				\
+	else								\
+		(head)->tqh_last = &(elm)->field.tqe_next;		\
+	(listelm)->field.tqe_next = (elm);				\
+	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
+} while (/*CONSTCOND*/0)
+
+#define	HEIM_TAILQ_INSERT_BEFORE(listelm, elm, field) do {		\
+	QUEUEDEBUG_HEIM_TAILQ_OP((listelm), field)			\
+	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
+	(elm)->field.tqe_next = (listelm);				\
+	*(listelm)->field.tqe_prev = (elm);				\
+	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
+} while (/*CONSTCOND*/0)
+
+#define	HEIM_TAILQ_REMOVE(head, elm, field) do {			\
+	QUEUEDEBUG_HEIM_TAILQ_PREREMOVE((head), (elm), field)		\
+	QUEUEDEBUG_HEIM_TAILQ_OP((elm), field)				\
+	if (((elm)->field.tqe_next) != NULL)				\
+		(elm)->field.tqe_next->field.tqe_prev = 		\
+		    (elm)->field.tqe_prev;				\
+	else								\
+		(head)->tqh_last = (elm)->field.tqe_prev;		\
+	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
+	QUEUEDEBUG_HEIM_TAILQ_POSTREMOVE((elm), field);			\
+} while (/*CONSTCOND*/0)
+
+#define	HEIM_TAILQ_FOREACH(var, head, field)				\
+	for ((var) = ((head)->tqh_first);				\
+		(var);							\
+		(var) = ((var)->field.tqe_next))
+
+#define	HEIM_TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
+	for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \
+		(var);							\
+		(var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
+
+/*
+ * Tail queue access methods.
+ */
+#define	HEIM_TAILQ_EMPTY(head)		((head)->tqh_first == NULL)
+#define	HEIM_TAILQ_FIRST(head)		((head)->tqh_first)
+#define	HEIM_TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
+
+#define	HEIM_TAILQ_LAST(head, headname) \
+	(*(((struct headname *)((head)->tqh_last))->tqh_last))
+#define	HEIM_TAILQ_PREV(elm, headname, field) \
+	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
+
+
+#endif	/* !_HEIM_QUEUE_H_ */
diff --git a/source4/heimdal/base/null.c b/source4/heimdal/base/null.c
new file mode 100644
index 0000000000..66731aad26
--- /dev/null
+++ b/source4/heimdal/base/null.c
@@ -0,0 +1,52 @@
+/*
+ * Copyright (c) 2010 Kungliga Tekniska Högskolan
+ * (Royal Institute of Technology, Stockholm, Sweden).
+ * All rights reserved.
+ *
+ * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of the Institute nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include "baselocl.h"
+
+struct heim_type_data _heim_null_object = {
+    HEIM_TID_NULL,
+    "null-object",
+    NULL,
+    NULL,
+    NULL,
+    NULL,
+    NULL
+};
+
+heim_null_t
+heim_null_create(void)
+{
+    return heim_base_make_tagged_object(0, HEIM_TID_NULL);
+}
diff --git a/source4/heimdal/base/number.c b/source4/heimdal/base/number.c
new file mode 100644
index 0000000000..72631a531c
--- /dev/null
+++ b/source4/heimdal/base/number.c
@@ -0,0 +1,127 @@
+/*
+ * Copyright (c) 2010 Kungliga Tekniska Högskolan
+ * (Royal Institute of Technology, Stockholm, Sweden).
+ * All rights reserved.
+ *
+ * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of the Institute nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include "baselocl.h"
+
+static void
+number_dealloc(void *ptr)
+{
+}
+
+static int
+number_cmp(void *a, void *b)
+{
+    int na, nb;
+
+    if (heim_base_is_tagged_object(a))
+	na = heim_base_tagged_object_value(a);
+    else
+	na = *(int *)a;
+
+    if (heim_base_is_tagged_object(b))
+	nb = heim_base_tagged_object_value(b);
+    else
+	nb = *(int *)b;
+
+    return na - nb;
+}
+
+static unsigned long
+number_hash(void *ptr)
+{
+    if (heim_base_is_tagged_object(ptr))
+	return heim_base_tagged_object_value(ptr);
+    return (unsigned long)*(int *)ptr;
+}
+
+struct heim_type_data _heim_number_object = {
+    HEIM_TID_NUMBER,
+    "number-object",
+    NULL,
+    number_dealloc,
+    NULL,
+    number_cmp,
+    number_hash
+};
+
+/**
+ * Create a number object
+ *
+ * @param the number to contain in the object
+ *
+ * @return a number object
+ */
+
+heim_number_t
+heim_number_create(int number)
+{
+    heim_number_t n;
+
+    if (number < 0xffffff && number >= 0)
+	return heim_base_make_tagged_object(number, HEIM_TID_NUMBER);
+
+    n = _heim_alloc_object(&_heim_number_object, sizeof(int));
+    if (n)
+	*((int *)n) = number;
+    return n;
+}
+
+/**
+ * Return the type ID of number objects
+ *
+ * @return type id of number objects
+ */
+
+heim_tid_t
+heim_number_get_type_id(void)
+{
+    return HEIM_TID_NUMBER;
+}
+
+/**
+ * Get the int value of the content
+ *
+ * @param number the number object to get the value from
+ *
+ * @return an int
+ */
+
+int
+heim_number_get_int(heim_number_t number)
+{
+    if (heim_base_is_tagged_object(number))
+	return heim_base_tagged_object_value(number);
+    return *(int *)number;
+}
diff --git a/source4/heimdal/base/string.c b/source4/heimdal/base/string.c
new file mode 100644
index 0000000000..414a9161fa
--- /dev/null
+++ b/source4/heimdal/base/string.c
@@ -0,0 +1,146 @@
+/*
+ * Copyright (c) 2010 Kungliga Tekniska Högskolan
+ * (Royal Institute of Technology, Stockholm, Sweden).
+ * All rights reserved.
+ *
+ * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of the Institute nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include "baselocl.h"
+#include <string.h>
+
+static void
+string_dealloc(void *ptr)
+{
+}
+
+static int
+string_cmp(void *a, void *b)
+{
+    if (heim_base_is_tagged_string(a))
+	a = heim_base_tagged_string_ptr(a);
+    if (heim_base_is_tagged_string(b))
+	b = heim_base_tagged_string_ptr(b);
+
+    return strcmp(a, b);
+}
+
+static unsigned long
+string_hash(void *ptr)
+{
+    const char *s;
+    unsigned long n;
+
+    if (heim_base_is_tagged_string(ptr))
+	s = heim_base_tagged_string_ptr(ptr);
+    else
+	s = ptr;
+
+    for (n = 0; *s; ++s)
+	n += *s;
+    return n;
+}
+
+
+struct heim_type_data _heim_string_object = {
+    HEIM_TID_STRING,
+    "string-object",
+    NULL,
+    string_dealloc,
+    NULL,
+    string_cmp,
+    string_hash
+};
+
+/**
+ * Create a string object
+ *
+ * @param string the string to create, must be an utf8 string
+ *
+ * @return string object
+ */
+
+heim_string_t
+heim_string_create(const char *string)
+{
+    size_t len = strlen(string);
+    heim_string_t s;
+
+    s = _heim_alloc_object(&_heim_string_object, len + 1);
+    if (s)
+	memcpy(s, string, len + 1);
+    return s;
+}
+
+/**
+ * Create a string object from a strings allocated in the text segment.
+ *
+ * Note that static string object wont be auto released with
+ * heim_auto_release(), the allocation policy of the string must
+ * be manged separately from the returned object. This make this
+ * function not very useful for strings in allocated from heap or
+ * stack. In that case you should use heim_string_create().
+ *
+ * @param string the string to create, must be an utf8 string
+ *
+ * @return string object
+ */
+
+heim_string_t
+heim_string_create_with_static(const char *string)
+{
+    return heim_base_make_tagged_string_ptr(string);
+}
+
+/**
+ * Return the type ID of string objects
+ *
+ * @return type id of string objects
+ */
+
+heim_tid_t
+heim_string_get_type_id(void)
+{
+    return HEIM_TID_STRING;
+}
+
+/**
+ * Get the string value of the content.
+ *
+ * @param string the string object to get the value from
+ *
+ * @return a utf8 string
+ */
+
+const char *
+heim_string_get_utf8(heim_string_t string)
+{
+    return (const char *)string;
+}