#define GAVL_UNBALANCED_SUPPORT
/* function to compare fields of two items */
-typedef int gavl_cmp_fnc_t(const void *a, const void *b);
+typedef int gavl_cmp_fnc_t(const void *a, const void *b) UL_ATTR_REENTRANT;
/**
* struct gavl_node - Structure Representing Node of Generic AVL Tree
gavl_node_t *
gavl_prev_node(const gavl_node_t *node);
+#if !defined(SDCC) && !defined(__SDCC)
+
int
gavl_is_empty(const gavl_root_t *root);
return (void*)(p+root->key_offs);
}
+#endif /*SDCC*/
+
int
gavl_balance_one(gavl_node_t **subtree);
/*===========================================================*/
/* iterators for generic GAVL type */
+#if !defined(SDCC) && !defined(__SDCC)
+
typedef struct {
gavl_root_t *container;
gavl_node_t *node;
}
static inline int
-gavl_find_it(gavl_root_t *container, void *key, gavl_it_t *it)
+gavl_find_it(gavl_root_t *container, const void *key, gavl_it_t *it)
{
it->container=container;
return (it->node=gavl_find_first_node(container, key))!=0;
}
static inline int
-gavl_find_first_it(gavl_root_t *container, void *key, gavl_it_t *it)
+gavl_find_first_it(gavl_root_t *container, const void *key, gavl_it_t *it)
{
it->container=container;
return (it->node=gavl_find_first_node(container, key))!=0;
}
static inline int
-gavl_find_after_it(gavl_root_t *container, void *key, gavl_it_t *it)
+gavl_find_after_it(gavl_root_t *container, const void *key, gavl_it_t *it)
{
it->container=container;
return (it->node=gavl_find_after_node(container, key))!=0;
#define gavl_generic_for_each_cut(item_t, root, ptr) \
for(;(ptr=(item_t*)gavl_cut_first(root));)
+#endif /*SDCC*/
+
/*===========================================================*/
/* basic types compare functions */
-int gavl_cmp_int(const void *a, const void *b);
-int gavl_cmp_long(const void *a, const void *b);
-int gavl_cmp_ptr(const void *a, const void *b);
+int gavl_cmp_int(const void *a, const void *b) UL_ATTR_REENTRANT;
+int gavl_cmp_long(const void *a, const void *b) UL_ATTR_REENTRANT;
+int gavl_cmp_ptr(const void *a, const void *b) UL_ATTR_REENTRANT;
/*===========================================================*/
/* More functions useful for partially balanced trees */
int cust_cmp_fnc(cust_key_t *a, cust_key_t *b) */
/* Declaration of new custom tree with internal node */
-#define GAVL_CUST_NODE_INT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
+#define GAVL_CUST_NODE_INT_DEC_SCOPE(cust_scope, cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
cust_root_node, cust_item_node, cust_item_key, cust_cmp_fnc) \
\
static inline cust_item_t * \
cust_prefix##_node2key(const cust_root_t *root, gavl_node_t *node)\
{ return &(cust_prefix##_node2item(root, node)->cust_item_key);}\
\
-void cust_prefix##_init_root_field(cust_root_t *root);\
-int cust_prefix##_search_node(const cust_root_t *root, cust_key_t *key, gavl_node_t **nodep);\
-cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t *key);\
-cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t *key);\
-cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t *key);\
-int cust_prefix##_insert(cust_root_t *root, cust_item_t *item);\
-int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node);\
-int cust_prefix##_delete(cust_root_t *root, cust_item_t *item);\
-gavl_node_t *cust_prefix##_first_node(const cust_root_t *root);\
-gavl_node_t *cust_prefix##_last_node(const cust_root_t *root);\
+cust_scope void cust_prefix##_init_root_field(cust_root_t *root);\
+cust_scope int cust_prefix##_search_node(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep);\
+cust_scope cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t const *key);\
+cust_scope cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t const *key);\
+cust_scope cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t const *key);\
+cust_scope int cust_prefix##_insert(cust_root_t *root, cust_item_t *item);\
+cust_scope int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node);\
+cust_scope int cust_prefix##_delete(cust_root_t *root, cust_item_t *item);\
+cust_scope gavl_node_t *cust_prefix##_first_node(const cust_root_t *root);\
+cust_scope gavl_node_t *cust_prefix##_last_node(const cust_root_t *root);\
\
static inline void \
cust_prefix##_init_detached(cust_item_t *item){\
/*** Iterators ***/\
UL_ITBASE_SORT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t)
+#define GAVL_CUST_NODE_INT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
+ cust_root_node, cust_item_node, cust_item_key, cust_cmp_fnc) \
+ GAVL_CUST_NODE_INT_DEC_SCOPE(extern, cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
+ cust_root_node, cust_item_node, cust_item_key, cust_cmp_fnc)
+
#define gavl_cust_for_each(cust_prefix, root, ptr) \
for(ptr=cust_prefix##_first(root);ptr;ptr=cust_prefix##_next((root),ptr))
root->cust_root_node=NULL;\
}\
\
-int cust_prefix##_search_node(const cust_root_t *root, cust_key_t *key, gavl_node_t **nodep)\
+int cust_prefix##_search_node(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep)\
{\
int cmp=1;\
gavl_node_t *n, *p;\
return cmp;\
}\
\
-cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t *key)\
+cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t const *key)\
{\
gavl_node_t *node;\
if(cust_prefix##_search_node(root, key, &node))\
return cust_prefix##_node2item(root,node);\
}\
\
-cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t *key)\
+cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t const *key)\
{\
return cust_prefix##_find(root, key);\
}\
\
-cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t *key)\
+cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t const *key)\
{\
gavl_node_t *node;\
if(cust_prefix##_search_node(root, key, &node)<=0){\
\
int cust_prefix##_delete(cust_root_t *root, cust_item_t *item)\
{\
- int ret;\
gavl_node_t *n, *p;\
if(!item) return -1;\
/*if(cust_prefix##_search_node(root, &item->cust_item_key, &n))*/\
for(p=n; p->parent; p=p->parent);\
if(p!=root->cust_root_node)\
return -1;\
- ret=gavl_delete_primitive(&root->cust_root_node, n);\
- return 1;\
+ return gavl_delete_primitive(&root->cust_root_node, n);\
}\
\
gavl_node_t *cust_prefix##_first_node(const cust_root_t *root)\
#endif
/* Declaration of tree with first/last enhanced speed functions with internal node */
-#define GAVL_FLES_INT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
+#define GAVL_FLES_INT_DEC_SCOPE(cust_scope, cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
\
static inline cust_item_t * \
cust_prefix##_node2key(const cust_root_t *root, gavl_node_t *node)\
{ return &(cust_prefix##_node2item(root, node)->cust_item_key);}\
\
-void cust_prefix##_init_root_field(cust_root_t *root);\
-int cust_prefix##_search_node(const cust_root_t *root, cust_key_t *key, gavl_node_t **nodep);\
-cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t *key);\
-cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t *key);\
-cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t *key);\
-int cust_prefix##_insert(cust_root_t *root, cust_item_t *item);\
-cust_item_t *cust_prefix##_cut_first(cust_root_t *root);\
-int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node);\
-int cust_prefix##_delete(cust_root_t *root, cust_item_t *item);\
+cust_scope void cust_prefix##_init_root_field(cust_root_t *root);\
+cust_scope int cust_prefix##_search_node(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep);\
+cust_scope cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t const *key);\
+cust_scope cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t const *key);\
+cust_scope cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t const *key);\
+cust_scope int cust_prefix##_insert(cust_root_t *root, cust_item_t *item);\
+cust_scope cust_item_t *cust_prefix##_cut_first(cust_root_t *root);\
+cust_scope int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node);\
+cust_scope int cust_prefix##_delete(cust_root_t *root, cust_item_t *item);\
\
static inline void \
cust_prefix##_init_detached(cust_item_t *item){\
/*** Iterators ***/\
UL_ITBASE_SORT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t)
+#define GAVL_FLES_INT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
+ cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
+ GAVL_FLES_INT_DEC_SCOPE(extern, cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
+ cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc)
/**
* GAVL_FLES_INT_IMP - Implementation of new custom tree with fast first/last functions
root->cust_root_field.count=0;\
}\
\
-int cust_prefix##_search_node4(const cust_root_t *root, cust_key_t *key, gavl_node_t **nodep, int mode)\
+int cust_prefix##_search_node4(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep, int mode)\
{\
int cmp=1;\
gavl_node_t *n, *p;\
return cmp;\
}\
\
-int cust_prefix##_search_node(const cust_root_t *root, cust_key_t *key, gavl_node_t **nodep)\
+int cust_prefix##_search_node(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep)\
{\
return cust_prefix##_search_node4(root, key, nodep, 0);\
}\
\
-cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t *key)\
+cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t const *key)\
{\
gavl_node_t *node;\
if(cust_prefix##_search_node4(root, key, &node, 0))\
return cust_prefix##_node2item(root,node);\
}\
\
-cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t *key)\
+cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t const *key)\
{\
gavl_node_t *n;\
if(cust_prefix##_search_node4(root, key, &n, GAVL_FFIRST))\
return cust_prefix##_node2item(root,n);\
}\
\
-cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t *key)\
+cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t const *key)\
{\
gavl_node_t *node;\
if(cust_prefix##_search_node4(root, key, &node, GAVL_FAFTER)<=0){\
\
int cust_prefix##_delete(cust_root_t *root, cust_item_t *item)\
{\
- int ret;\
gavl_node_t *n, *p;\
if(!item) return -1;\
n=&item->cust_item_node;\
for(p=n; p->parent; p=p->parent);\
if(p!=root->cust_root_node)\
return -1;\
- ret=gavl_delete_primitive(&root->cust_root_node, n);\
- return 1;\
+ return gavl_delete_primitive(&root->cust_root_node, n);\
}\
\
gavl_node_t *cust_prefix##_first_node(const cust_root_t *root)\
#define inline _inline
#endif
+#if !defined(UL_BUILD_BUG_ON_MSG_LINE) && defined(__OPTIMIZE__) && \
+ ((__GNUC__ * 1000 + __GNUC_MINOR__) >= 4004)
+#define UL_BUILD_BUG_ON_MSG_LINE_EXP1(condition, msg, line) \
+({ \
+ if (!!(condition)) { \
+ void compile_time_bug_on_line_ ## line (void) __attribute__((error(msg))); \
+ compile_time_bug_on_line_ ## line (); \
+ } \
+})
+#define UL_BUILD_BUG_ON_MSG_LINE(condition, msg, line) \
+ UL_BUILD_BUG_ON_MSG_LINE_EXP1(condition, msg, line)
+#endif /*UL_BUILD_BUG_ON_MSG for GCC*/
+
+#ifndef UL_BUILD_BUG_ON_MSG_LINE
+#define UL_BUILD_BUG_ON_MSG_LINE(condition, msg, line) \
+ ((void)sizeof(char[1 - 2*!!(condition)]))
+#endif /*UL_BUILD_BUG_ON_MSG*/
+
+#ifndef UL_BUILD_BUG_ON_MSG
+#define UL_BUILD_BUG_ON_MSG(condition, msg) \
+ UL_BUILD_BUG_ON_MSG_LINE(condition, msg, __LINE__)
+#endif /*UL_BUILD_BUG_ON_MSG*/
+
+#ifndef UL_BUILD_BUG_ON
+#define UL_BUILD_BUG_ON(condition) \
+ UL_BUILD_BUG_ON_MSG(condition, "Build time check " #condition " failed")
+#endif /*UL_BUILD_BUG_ON*/
+
+#if !defined(UL_OFFSETOF) && defined(__GNUC__) && __GNUC__ >= 4
+#define UL_OFFSETOF(_type, _member) __builtin_offsetof(_type, _member)
+#endif /*UL_OFFSETOF*/
+
#ifndef UL_OFFSETOF
/* offset of structure field */
#define UL_OFFSETOF(_type,_member) \
#endif /*__GNUC__*/
#endif /*UL_CONTAINEROF*/
+#ifndef UL_NOPSTATEMENT
+#define UL_NOPSTATEMENT do { } while(0)
+#endif
+
#ifndef ul_cyclic_gt
#define ul_cyclic_gt(x,y) \
((sizeof(x)>=sizeof(long long))&&(sizeof(y)>=sizeof(long long))? \
- (long long)((long long)(x)-(long long)(y))>0: \
+ (long long)((unsigned long long)(x)-(unsigned long long)(y))>0: \
(sizeof(x)>=sizeof(long))&&(sizeof(y)>=sizeof(long))? \
- (long)((long)(x)-(long)(y))>0: /* x,y casts to suppress warnings only*/ \
- (sizeof(x)>=sizeof(int))&&(sizeof(y)>=sizeof(int))?(int)((x)-(y))>0: \
- (sizeof(x)>=sizeof(short))&&(sizeof(y)>=sizeof(short))?(short)((x)-(y))>0: \
- (signed char)((x)-(y))>0 \
+ (long)((unsigned long)(x)-(unsigned long)(y))>0: \
+ (sizeof(x)>=sizeof(int))&&(sizeof(y)>=sizeof(int))? \
+ (int)((unsigned int)(x)-(unsigned int)(y))>0: \
+ (sizeof(x)>=sizeof(short))&&(sizeof(y)>=sizeof(short))? \
+ (short)((unsigned short)(x)-(unsigned short)(y))>0: \
+ (signed char)((unsigned char)(x)-(unsigned char)(y))>0 \
)
#endif /*ul_cyclic_gt*/
#ifndef ul_cyclic_ge
#define ul_cyclic_ge(x,y) \
((sizeof(x)>=sizeof(long long))&&(sizeof(y)>=sizeof(long long))? \
- (long long)((long long)(x)-(long long)(y))>=0: \
+ (long long)((unsigned long long)(x)-(unsigned long long)(y))>=0: \
(sizeof(x)>=sizeof(long))&&(sizeof(y)>=sizeof(long))? \
- (long)((long)(x)-(long)(y))>=0: /* x,y casts to suppress warnings only*/ \
- (sizeof(x)>=sizeof(int))&&(sizeof(y)>=sizeof(int))?(int)((x)-(y))>=0: \
- (sizeof(x)>=sizeof(short))&&(sizeof(y)>=sizeof(short))?(short)((x)-(y))>=0: \
- (signed char)((x)-(y))>=0 \
+ (long)((unsigned long)(x)-(unsigned long)(y))>=0: \
+ (sizeof(x)>=sizeof(int))&&(sizeof(y)>=sizeof(int))? \
+ (int)((unsigned int)(x)-(unsigned int)(y))>=0: \
+ (sizeof(x)>=sizeof(short))&&(sizeof(y)>=sizeof(short))? \
+ (short)((unsigned short)(x)-(unsigned short)(y))>=0: \
+ (signed char)((unsigned char)(x)-(unsigned char)(y))>=0 \
)
#endif /*ul_cyclic_ge*/
__attribute__((const))
#define UL_ATTR_UNUSED \
__attribute__((unused))
+#define UL_ATTR_CONSTRUCTOR \
+ __attribute__((constructor))
+#define UL_ATTR_DESCRUCTOR \
+ __attribute__((destructor))
+#define UL_ATTR_ALWAYS_INLINE \
+ __attribute__((always_inline))
+#define UL_ATTR_WEAK \
+ __attribute__((weak))
#endif /*UL_ATTR_UNUSED*/
#else /* !__GNUC__ */
#ifndef UL_ATTR_UNUSED
#define UL_ATTR_NORETURN
#define UL_ATTR_CONST
#define UL_ATTR_UNUSED
+#define UL_ATTR_CONSTRUCTOR
+#define UL_ATTR_DESCRUCTOR
+#define UL_ATTR_ALWAYS_INLINE
+#define UL_ATTR_WEAK
#endif /*UL_ATTR_UNUSED*/
#endif /* !__GNUC__ */
+#ifndef UL_ATTR_REENTRANT
+#if (!defined(SDCC) && !defined(__SDCC)) || defined(SDCC_z80) || defined(__SDCC_z80)
+ #define UL_ATTR_REENTRANT
+#else
+ #define UL_ATTR_REENTRANT __reentrant
+#endif
+#endif /*UL_ATTR_REENTRANT*/
+
+/* The cast idea based on libHX by Jan Engelhardt */
+#define UL_TYPEOF_REFX(ref_asterisks, ptr_type) \
+ typeof(ref_asterisks(union { int z; typeof(ptr_type) x; }){0}.x)
+
+#ifdef __GNUC__
+#define UL_CAST_UNQX(ref_asterisks, new_type, expr) ({ \
+ UL_BUILD_BUG_ON_MSG(!__builtin_types_compatible_p\
+ (UL_TYPEOF_REFX(ref_asterisks, expr), \
+ UL_TYPEOF_REFX(ref_asterisks,new_type)), \
+ "Qualifiers stripping cast to incompatible type"); \
+ (new_type)(expr); \
+})
+#else /*__GNUC__*/
+#define UL_CAST_UNQX(ref_asterisks, new_type, expr) ((new_type)(expr))
+#endif /*__GNUC__*/
+
+#define UL_CAST_UNQ1(new_type, expr) \
+ UL_CAST_UNQX(*, new_type, expr)
+
+#define UL_CAST_UNQ2(new_type, expr) \
+ UL_CAST_UNQX(**, new_type, expr)
+
+#define UL_CAST_UNQ3(new_type, expr) \
+ UL_CAST_UNQX(**, new_type, expr)
+
#ifdef __cplusplus
} /* extern "C"*/
#endif
--- /dev/null
+#ifndef _UL_UTMALLOC_H
+#define _UL_UTMALLOC_H
+
+#if !defined(__RTL__)&&!defined(__KERNEL__)
+
+#include <malloc.h>
+
+#else /*__RTL__ or __KERNEL__*/
+
+#ifdef UL_WITH_RTL_MALLOC
+#include <rtl_malloc.h>
+#define malloc rt_malloc
+#define free rt_free
+#define realloc rt_realloc
+#endif /*UL_WITH_RTL_MALLOC*/
+
+#endif /*__RTL__ or __KERNEL__*/
+
+#endif /*_UL_UTMALLOC_H*/
*******************************************************************/
-#include <orte_all.h>
-//#include <string.h>
-//#include "ul_utmalloc.h"
-
+#include <string.h>
+#include "ul_utmalloc.h"
#include "ul_gavl.h"
int
break;
}
}
- if(mode&GAVL_FAFTER){
+ if((mode&GAVL_FAFTER)&&!(mode&GAVL_FCMP)){
if(cmp<=0)
if(p) p=gavl_next_node(p);
*nodep=p;
(mode|GAVL_FCMP), &where);
if((mode!=GAVL_FAFTER) && !cmp) return -1;
if(root->node_offs<0){
- n2add=MALLOC(sizeof(gavl_node_t)+sizeof(void*));
+ n2add=malloc(sizeof(gavl_node_t)+sizeof(void*));
if(!n2add) return -1;
*(void**)(n2add+1)=item;
} else {
/* delete_primitive called directly for speedup */
ret=gavl_delete_primitive(&root->root_node, n);
if(root->node_offs<0)
- FREE(n);
+ free(n);
return ret;
}
/*===========================================================*/
/* basic types compare functions */
-int gavl_cmp_int(const void *a, const void *b)
+int gavl_cmp_int(const void *a, const void *b) UL_ATTR_REENTRANT
{
if (*(int*)a>*(int*)b) return 1;
if (*(int*)a<*(int*)b) return -1;
return 0;
}
-int gavl_cmp_long(const void *a, const void *b)
+int gavl_cmp_long(const void *a, const void *b) UL_ATTR_REENTRANT
{
if (*(long*)a>*(long*)b) return 1;
if (*(long*)a<*(long*)b) return -1;
return 0;
}
-int gavl_cmp_ptr(const void *a, const void *b)
+int gavl_cmp_ptr(const void *a, const void *b) UL_ATTR_REENTRANT
{
if (*(void**)a>*(void**)b) return 1;
if (*(void**)a<*(void**)b) return -1;
return NULL;
item=gavl_node2item(root,n);
if(root->node_offs<0)
- FREE(n);
+ free(n);
return item;
}
*******************************************************************/
-//#include <string.h>
-#include <orte_all.h>
+#include <string.h>
#include "ul_gavl.h"
int
}
}
+#if defined(SDCC) || defined(__SDCC)
+#pragma save
+#pragma nogcse
+#endif /*SDCC*/
/**
* gavl_balance_one - Balance One Node to Enhance Balance Factor
* @subtree: pointer to pointer to node for which balance is enhanced
/*printf("#%d",ret);*/
return(ret);
}
+#if defined(SDCC) || defined(__SDCC)
+#pragma restore
+#endif /*SDCC*/
/**
* gavl_insert_primitive_at - Low Lewel Routine to Insert Node into Tree