1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/core/avl.c	Sat Jul 18 19:45:19 2009 +0200
     1.3 @@ -0,0 +1,414 @@
     1.4 +/*
     1.5 + * NASPRO - NASPRO Architecture for Sound Processing
     1.6 + * Core library
     1.7 + *
     1.8 + * Copyright (C) 2007-2009  Stefano D'Angelo  <zanga.mail@gmail.com>
     1.9 + *
    1.10 + * See the COPYING file for license conditions.
    1.11 + */
    1.12 +
    1.13 +#include <stdlib.h>
    1.14 +#include <string.h>
    1.15 +
    1.16 +#include <NASPRO/core/lib.h>
    1.17 +
    1.18 +/* TODO: Nothing here is thread-safe. */
    1.19 +
    1.20 +struct avl_tree_node
    1.21 +  {
    1.22 +	size_t			 father;
    1.23 +	size_t			 left;
    1.24 +	size_t			 right;
    1.25 +	size_t			 l_height;
    1.26 +	size_t			 r_height;
    1.27 +	void			*content;
    1.28 +  };
    1.29 +
    1.30 +struct _nacore_avl_tree
    1.31 +  {
    1.32 +	size_t			 root;
    1.33 +	struct avl_tree_node	*nodes;
    1.34 +	size_t			 count;
    1.35 +
    1.36 +	int	(*content_cmp)		(void *c1, void *c2);
    1.37 +	int	(*key_cmp)		(void *content, void *key);
    1.38 +  };
    1.39 +
    1.40 +nacore_avl_tree_t
    1.41 +nacore_avl_tree_new(int (*content_cmp)	(void *c1, void *c2),
    1.42 +		    int (*key_cmp)	(void *content, void *key))
    1.43 +{
    1.44 +	nacore_avl_tree_t tree;
    1.45 +
    1.46 +	tree = malloc(sizeof(struct _nacore_avl_tree));
    1.47 +	if (tree == NULL)
    1.48 +		return NULL;
    1.49 +
    1.50 +	tree->root = 0;
    1.51 +	tree->nodes = NULL;
    1.52 +	tree->count = 0;
    1.53 +	tree->content_cmp = content_cmp;
    1.54 +	tree->key_cmp = key_cmp;
    1.55 +
    1.56 +	return tree;
    1.57 +}
    1.58 +
    1.59 +#define max(x, y)	(((x) > (y)) ? (x) : (y))
    1.60 +
    1.61 +#if 0
    1.62 +static void
    1.63 +node_dump(nacore_avl_tree_t tree, struct avl_tree_node *node)
    1.64 +{
    1.65 +	printf("  node: %lu (%p), father: %lu (%p), left: %lu (%p), right: %lu (%p), l_height: %lu, r_height: %lu\n",
    1.66 +		node - tree->nodes + 1,  node,
    1.67 +		node->father, tree->nodes + node->father - 1,
    1.68 +		node->left, tree->nodes + node->left - 1,
    1.69 +		node->right, tree->nodes + node->right - 1,
    1.70 +		node->l_height, node->r_height);
    1.71 +	if (node->left != 0)
    1.72 +		node_dump(tree, tree->nodes + node->left - 1);
    1.73 +	if (node->right != 0)
    1.74 +		node_dump(tree, tree->nodes + node->right - 1);
    1.75 +}
    1.76 +
    1.77 +static void
    1.78 +tree_dump(nacore_avl_tree_t tree)
    1.79 +{
    1.80 +	printf("Tree: %p, nodes: %lu, root: %lu (%p)\n", tree, tree->count, tree->root, tree->nodes + tree->root - 1);
    1.81 +	if (tree->root != 0)
    1.82 +	node_dump(tree, tree->nodes + tree->root - 1);
    1.83 +}
    1.84 +#endif
    1.85 +
    1.86 +static void
    1.87 +adjust_heights(nacore_avl_tree_t tree, struct avl_tree_node *p)
    1.88 +{
    1.89 +	struct avl_tree_node *p2;
    1.90 +	
    1.91 +	for (p2 = p, p = (p->father == 0) ? NULL : tree->nodes + p->father - 1;
    1.92 +	     p != NULL;
    1.93 +	     p2 = p, p = (p->father == 0) ? NULL : tree->nodes + p2->father - 1)
    1.94 +	  {
    1.95 +		if (p->left == p2 - tree->nodes + 1)
    1.96 +			p->l_height = max(p2->l_height, p2->r_height) + 1;
    1.97 +		else
    1.98 +			p->r_height = max(p2->l_height, p2->r_height) + 1;
    1.99 +	  }
   1.100 +}
   1.101 +
   1.102 +void
   1.103 +nacore_avl_tree_add(nacore_avl_tree_t tree, void *content)
   1.104 +{
   1.105 +	struct avl_tree_node *p, *tmp, *tmp2;
   1.106 +
   1.107 +	/* Allocation */
   1.108 +	tmp = realloc(tree->nodes,
   1.109 +		      (tree->count + 1) * sizeof(struct avl_tree_node));
   1.110 +	if (tmp == NULL)
   1.111 +		return;
   1.112 +
   1.113 +	tree->nodes = tmp;
   1.114 +	tmp = tree->nodes + tree->count;
   1.115 +
   1.116 +	tmp->content = content;
   1.117 +	tmp->father = 0;
   1.118 +	tmp->left = 0;
   1.119 +	tmp->right = 0;
   1.120 +	tmp->l_height = 0;
   1.121 +	tmp->r_height = 0;
   1.122 +	tree->count++;
   1.123 +
   1.124 +	/* Insertion */
   1.125 +	if (tree->root == 0)
   1.126 +	  {
   1.127 +		tree->root = 1;
   1.128 +		return;
   1.129 +	  }
   1.130 +
   1.131 +	p = tree->nodes + tree->root - 1;
   1.132 +	while (1)
   1.133 +	  {
   1.134 +		if (tree->content_cmp(content, p->content) > 0)
   1.135 +		  {
   1.136 +			if (p->right != 0)
   1.137 +				p = tree->nodes + p->right - 1;
   1.138 +			else
   1.139 +			  {
   1.140 +				p->r_height = 1;
   1.141 +				p->right = tree->count;
   1.142 +				tmp->father = p - tree->nodes + 1;
   1.143 +				adjust_heights(tree, p);
   1.144 +				break;
   1.145 +			  }
   1.146 +		  }
   1.147 +		else
   1.148 +		  {
   1.149 +			if (p->left != 0)
   1.150 +				p = tree->nodes + p->left - 1;
   1.151 +			else
   1.152 +			  {
   1.153 +				p->l_height = 1;
   1.154 +				p->left = tree->count;
   1.155 +				tmp->father = p - tree->nodes + 1;
   1.156 +				adjust_heights(tree, p);
   1.157 +				break;
   1.158 +			  }
   1.159 +		  }
   1.160 +	  }
   1.161 +
   1.162 +	/* Balancing */
   1.163 +	while (p->father != 0)
   1.164 +	  {
   1.165 +		p = tree->nodes + p->father - 1;
   1.166 +
   1.167 +		if ((p->l_height - p->r_height) == 2)
   1.168 +		  {
   1.169 +			if (tree->nodes[p->left - 1].l_height
   1.170 +			    == (p->l_height - 1))
   1.171 +			  {
   1.172 +				/* right rotation */
   1.173 +				
   1.174 +				/* p is root, tmp is pivot */
   1.175 +				tmp = tree->nodes + p->left - 1;
   1.176 +				
   1.177 +				p->left = tmp->right;
   1.178 +				tmp->right = p - tree->nodes + 1;
   1.179 +
   1.180 +				p->l_height = tmp->r_height;
   1.181 +				tmp->r_height = max(p->l_height, p->r_height)
   1.182 +						+ 1;
   1.183 +
   1.184 +				tmp->father = p->father;
   1.185 +				p->father = tmp - tree->nodes + 1;
   1.186 +
   1.187 +				if (p->left != 0)
   1.188 +					tree->nodes[p->left - 1].father =
   1.189 +						p - tree->nodes + 1;
   1.190 +
   1.191 +				if (tmp->father != 0)
   1.192 +				  {
   1.193 +					if (tree->nodes[tmp->father - 1].left
   1.194 +					    == p - tree->nodes + 1)
   1.195 +						tree->nodes[tmp->father
   1.196 +							    - 1].left =
   1.197 +							tmp - tree->nodes + 1;
   1.198 +					else
   1.199 +						tree->nodes[tmp->father
   1.200 +							    - 1].right =
   1.201 +							tmp - tree->nodes + 1;
   1.202 +				  }
   1.203 +
   1.204 +				adjust_heights(tree, p);
   1.205 +			  }
   1.206 +			else
   1.207 +			  {
   1.208 +				/* left-right rotation */
   1.209 +
   1.210 +				/* p is root's father, tmp is pivot,
   1.211 +				 * tmp2 is root */
   1.212 +				tmp = tree->nodes
   1.213 +				      + tree->nodes[p->left - 1].right - 1;
   1.214 +				tmp2 = tree->nodes + tmp->father - 1;
   1.215 +				
   1.216 +				p->left = tmp->right;
   1.217 +				tmp2->right = tmp->left;
   1.218 +				tmp->left = tmp2 - tree->nodes + 1;
   1.219 +				tmp->right = p - tree->nodes + 1;
   1.220 +
   1.221 +				p->l_height = tmp->r_height;
   1.222 +				tmp2->r_height = tmp->l_height;
   1.223 +				tmp->l_height = max(tmp2->l_height,
   1.224 +						    tmp2->r_height) + 1;
   1.225 +				tmp->r_height = max(p->l_height, p->r_height)
   1.226 +						+ 1;
   1.227 +
   1.228 +				tmp->father = p->father;
   1.229 +				p->father = tmp - tree->nodes + 1;
   1.230 +				tmp2->father = tmp - tree->nodes + 1;
   1.231 +
   1.232 +				if (tmp2->right != 0)
   1.233 +					tree->nodes[tmp2->right - 1].father =
   1.234 +						tmp2 - tree->nodes + 1;
   1.235 +				if (p->left != 0)
   1.236 +					tree->nodes[p->left - 1].father =
   1.237 +						p - tree->nodes + 1;
   1.238 +
   1.239 +				if (tmp->father != 0)
   1.240 +				  {
   1.241 +					if (tree->nodes[tmp->father - 1].left
   1.242 +					    == p - tree->nodes + 1)
   1.243 +						tree->nodes[tmp->father
   1.244 +							    - 1].left =
   1.245 +							tmp - tree->nodes + 1;
   1.246 +					else
   1.247 +						tree->nodes[tmp->father
   1.248 +							    - 1].right =
   1.249 +							tmp - tree->nodes + 1;
   1.250 +				  }
   1.251 +
   1.252 +				adjust_heights(tree, p);
   1.253 +			  }
   1.254 +		  }
   1.255 +		else if ((p->r_height - p->l_height) == 2)
   1.256 +		  {
   1.257 +			if (tree->nodes[p->right - 1].r_height
   1.258 +			    == (p->r_height - 1))
   1.259 +			  {
   1.260 +				/* left rotation */
   1.261 +
   1.262 +				/* p is root, tmp is pivot */
   1.263 +				
   1.264 +				tmp = tree->nodes + p->right - 1;
   1.265 +				
   1.266 +				p->right = tmp->left;
   1.267 +				tmp->left = p - tree->nodes + 1;
   1.268 +
   1.269 +				p->r_height = tmp->l_height;
   1.270 +				tmp->l_height = max(p->l_height, p->r_height)
   1.271 +						+ 1;
   1.272 +
   1.273 +				tmp->father = p->father;
   1.274 +				p->father = tmp - tree->nodes + 1;
   1.275 +
   1.276 +				if (p->right != 0)
   1.277 +					tree->nodes[p->right - 1].father =
   1.278 +						p - tree->nodes + 1;
   1.279 +
   1.280 +				if (tmp->father != 0)
   1.281 +				  {
   1.282 +					if (tree->nodes[tmp->father - 1].left
   1.283 +					    == p - tree->nodes + 1)
   1.284 +						tree->nodes[tmp->father
   1.285 +							    - 1].left =
   1.286 +							tmp - tree->nodes + 1;
   1.287 +					else
   1.288 +						tree->nodes[tmp->father
   1.289 +							    - 1].right =
   1.290 +							tmp - tree->nodes + 1;
   1.291 +				  }
   1.292 +
   1.293 +				adjust_heights(tree, p);
   1.294 +			  }
   1.295 +			else
   1.296 +			  {
   1.297 +				/* right-left rotation */
   1.298 +
   1.299 +				/* p is root's father, tmp is pivot,
   1.300 +				 * tmp2 is root */
   1.301 +				
   1.302 +				tmp = tree->nodes +
   1.303 +				      tree->nodes[p->right - 1].left - 1;
   1.304 +				tmp2 = tree->nodes + tmp->father - 1;
   1.305 +
   1.306 +				p->right = tmp->left;
   1.307 +				tmp2->left = tmp->right;
   1.308 +				tmp->left = p - tree->nodes + 1;
   1.309 +				tmp->right = tmp2 - tree->nodes + 1;
   1.310 +
   1.311 +				p->r_height = tmp->l_height;
   1.312 +				tmp2->l_height = tmp->r_height;
   1.313 +				tmp->l_height = max(p->l_height, p->r_height)
   1.314 +						+ 1;
   1.315 +				tmp->r_height = max(tmp2->l_height,
   1.316 +						    tmp2->r_height) + 1;
   1.317 +
   1.318 +				tmp->father = p->father;
   1.319 +				p->father = tmp - tree->nodes + 1;
   1.320 +				tmp2->father = tmp - tree->nodes + 1;
   1.321 +
   1.322 +				if (tmp2->left != 0)
   1.323 +					tree->nodes[tmp2->left - 1].father =
   1.324 +						tmp2 -tree->nodes + 1;
   1.325 +				if (p->right != 0)
   1.326 +					tree->nodes[p->right - 1].father =
   1.327 +						p -tree->nodes + 1;
   1.328 +
   1.329 +				if (tmp->father != 0)
   1.330 +				  {
   1.331 +					if (tree->nodes[tmp->father - 1].left
   1.332 +					    == p - tree->nodes + 1)
   1.333 +						tree->nodes[tmp->father
   1.334 +							    - 1].left =
   1.335 +							tmp - tree->nodes + 1;
   1.336 +					else
   1.337 +						tree->nodes[tmp->father
   1.338 +							    - 1].right =
   1.339 +							tmp - tree->nodes + 1;
   1.340 +				  }
   1.341 +
   1.342 +				adjust_heights(tree, p);
   1.343 +			  }
   1.344 +		  }
   1.345 +	  }
   1.346 +
   1.347 +	/* Fix root node */
   1.348 +	p = tree->nodes + tree->root - 1;
   1.349 +	while (p->father != 0)
   1.350 +		p = tree->nodes + p->father - 1;
   1.351 +
   1.352 +	tree->root = p - tree->nodes + 1;
   1.353 +}
   1.354 +
   1.355 +void
   1.356 +nacore_avl_tree_for_each(nacore_avl_tree_t tree,
   1.357 +			 void (*callback)(void *content, void *data),
   1.358 +			 void *data)
   1.359 +{
   1.360 +	size_t i;
   1.361 +
   1.362 +	for (i = 0; i < tree->count; i++)
   1.363 +		callback(tree->nodes[i].content, data);
   1.364 +}
   1.365 +
   1.366 +void *
   1.367 +nacore_avl_tree_find(nacore_avl_tree_t tree, void *key)
   1.368 +{
   1.369 +	struct avl_tree_node *p;
   1.370 +	int cmp;
   1.371 +	size_t next;
   1.372 +
   1.373 +	if (tree->root == 0)
   1.374 +		return NULL;
   1.375 +
   1.376 +	next = tree->root;
   1.377 +	do
   1.378 +	  {
   1.379 +		p = tree->nodes + next - 1;
   1.380 +		cmp = tree->key_cmp(p->content, key);
   1.381 +		if (cmp == 0)
   1.382 +			return p->content;
   1.383 +		if (cmp < 0)
   1.384 +			next = p->right;
   1.385 +		else
   1.386 +			next = p->left;
   1.387 +	  }
   1.388 +	while (next != 0);
   1.389 +
   1.390 +	return NULL;
   1.391 +}
   1.392 +
   1.393 +size_t
   1.394 +nacore_avl_tree_get_nodes_count(nacore_avl_tree_t tree)
   1.395 +{
   1.396 +	return tree->count;
   1.397 +}
   1.398 +
   1.399 +void
   1.400 +nacore_avl_tree_free(nacore_avl_tree_t tree)
   1.401 +{
   1.402 +	free(tree->nodes);
   1.403 +	free(tree);
   1.404 +}
   1.405 +
   1.406 +int
   1.407 +nacore_content_cmp_descriptor_by_uri(void *c1, void *c2)
   1.408 +{
   1.409 +	return strcmp(((struct nacore_descriptor *)c1)->uri,
   1.410 +		      ((struct nacore_descriptor *)c2)->uri);
   1.411 +}
   1.412 +
   1.413 +int
   1.414 +nacore_key_cmp_descriptor_by_uri(void *content, void *key)
   1.415 +{
   1.416 +	return strcmp(((struct nacore_descriptor *)content)->uri, (char *)key);
   1.417 +}

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/core/lv2api.c	Sat Jul 18 19:45:19 2009 +0200
     2.3 @@ -0,0 +1,24 @@
     2.4 +/*
     2.5 + * NASPRO - NASPRO Architecture for Sound Processing
     2.6 + * Core library
     2.7 + *
     2.8 + * Copyright (C) 2007-2009  Stefano D'Angelo  <zanga.mail@gmail.com>
     2.9 + *
    2.10 + * See the COPYING file for license conditions.
    2.11 + */
    2.12 +
    2.13 +#include <NASPRO/core/lib.h>
    2.14 +
    2.15 +void
    2.16 +nacore_lv2api_fill_desc(LV2_Descriptor *lv2_desc,
    2.17 +			struct nacore_descriptor *n_desc)
    2.18 +{
    2.19 +	lv2_desc->URI = n_desc->uri;
    2.20 +	
    2.21 +	lv2_desc->instantiate = n_desc->instantiate;
    2.22 +	lv2_desc->connect_port = n_desc->connect_port;
    2.23 +	lv2_desc->activate = n_desc->activate;
    2.24 +	lv2_desc->run = n_desc->run;
    2.25 +	lv2_desc->deactivate = n_desc->deactivate;
    2.26 +	lv2_desc->cleanup = n_desc->cleanup;
    2.27 +}

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/core/posix/env.c	Sat Jul 18 19:45:19 2009 +0200
     3.3 @@ -0,0 +1,23 @@
     3.4 +/*
     3.5 + * NASPRO - NASPRO Architecture for Sound Processing
     3.6 + * Core library
     3.7 + *
     3.8 + * Copyright (C) 2007-2009  Stefano D'Angelo  <zanga.mail@gmail.com>
     3.9 + *
    3.10 + * See the COPYING file for license conditions.
    3.11 + */
    3.12 +
    3.13 +#include <stdlib.h>
    3.14 +
    3.15 +#include <NASPRO/core/lib.h>
    3.16 +
    3.17 +char *
    3.18 +nacore_env_get_var(const char *name)
    3.19 +{
    3.20 +	return getenv(name);
    3.21 +}
    3.22 +
    3.23 +void
    3.24 +nacore_env_free_var_value(char *value)
    3.25 +{
    3.26 +}