naspro: 4f7243a606b1 naspro-core/src/avl.c

naspro

view naspro-core/src/avl.c @ 174:4f7243a606b1

Updated copyright notices and build system

author	Stefano D'Angelo <zanga.mail@gmail.com>
date	Sat May 01 21:51:33 2010 +0300 (2010-05-01)
parents	71372f617827
children

line source

1 /*

2 * NASPRO - NASPRO Architecture for Sound Processing

3 * Core library

4 *

6 *

7 * See the COPYING file for license conditions.

8 */

10 #include <stdlib.h>

11 #include <string.h>

13 #include <NASPRO/core/lib.h>

15 struct avl_tree_node

16 {

17 size_t father;

18 size_t left;

19 size_t right;

20 size_t l_height;

21 size_t r_height;

22 void *content;

23 };

25 struct _nacore_avl_tree

26 {

27 size_t root;

28 struct avl_tree_node *nodes;

29 size_t count;

31 int (*content_cmp) (void *c1, void *c2);

32 int (*key_cmp) (void *content, void *key);

33 };

35 nacore_avl_tree_t

36 nacore_avl_tree_new(int (*content_cmp) (void *c1, void *c2),

37 int (*key_cmp) (void *content, void *key))

38 {

39 nacore_avl_tree_t tree;

41 tree = malloc(sizeof(struct _nacore_avl_tree));

42 if (tree == NULL)

43 return NULL;

45 tree->root = 0;

46 tree->nodes = NULL;

47 tree->count = 0;

48 tree->content_cmp = content_cmp;

49 tree->key_cmp = key_cmp;

51 return tree;

52 }

54 #define max(x, y) (((x) > (y)) ? (x) : (y))

56 #if 0

57 static void

58 node_dump(nacore_avl_tree_t tree, struct avl_tree_node *node)

59 {

60 printf(" node: %lu (%p), father: %lu (%p), left: %lu (%p), right: %lu (%p), l_height: %lu, r_height: %lu\n",

61 node - tree->nodes + 1, node,

62 node->father, tree->nodes + node->father - 1,

63 node->left, tree->nodes + node->left - 1,

64 node->right, tree->nodes + node->right - 1,

65 node->l_height, node->r_height);

66 if (node->left != 0)

67 node_dump(tree, tree->nodes + node->left - 1);

68 if (node->right != 0)

69 node_dump(tree, tree->nodes + node->right - 1);

70 }

72 static void

73 tree_dump(nacore_avl_tree_t tree)

74 {

75 printf("Tree: %p, nodes: %lu, root: %lu (%p)\n", tree, tree->count, tree->root, tree->nodes + tree->root - 1);

76 if (tree->root != 0)

77 node_dump(tree, tree->nodes + tree->root - 1);

78 }

79 #endif

81 static void

82 adjust_heights(nacore_avl_tree_t tree, struct avl_tree_node *p)

83 {

84 struct avl_tree_node *p2;

86 for (p2 = p, p = (p->father == 0) ? NULL : tree->nodes + p->father - 1;

87 p != NULL;

88 p2 = p, p = (p->father == 0) ? NULL : tree->nodes + p2->father - 1)

89 {

90 if (p->left == p2 - tree->nodes + 1)

91 p->l_height = max(p2->l_height, p2->r_height) + 1;

92 else

93 p->r_height = max(p2->l_height, p2->r_height) + 1;

94 }

95 }

97 void

98 nacore_avl_tree_add(nacore_avl_tree_t tree, void *content)

99 {

100 struct avl_tree_node *p, *tmp, *tmp2;

101

102 /* Allocation */

103 tmp = realloc(tree->nodes,

104 (tree->count + 1) * sizeof(struct avl_tree_node));

105 if (tmp == NULL)

106 return;

107

108 tree->nodes = tmp;

109 tmp = tree->nodes + tree->count;

110

111 tmp->content = content;

112 tmp->father = 0;

113 tmp->left = 0;

114 tmp->right = 0;

115 tmp->l_height = 0;

116 tmp->r_height = 0;

117 tree->count++;

118

119 /* Insertion */

120 if (tree->root == 0)

121 {

122 tree->root = 1;

123 return;

124 }

125

126 p = tree->nodes + tree->root - 1;

127 while (1)

128 {

129 if (tree->content_cmp(content, p->content) > 0)

130 {

131 if (p->right != 0)

132 p = tree->nodes + p->right - 1;

133 else

134 {

135 p->r_height = 1;

136 p->right = tree->count;

137 tmp->father = p - tree->nodes + 1;

138 adjust_heights(tree, p);

139 break;

140 }

141 }

142 else

143 {

144 if (p->left != 0)

145 p = tree->nodes + p->left - 1;

146 else

147 {

148 p->l_height = 1;

149 p->left = tree->count;

150 tmp->father = p - tree->nodes + 1;

151 adjust_heights(tree, p);

152 break;

153 }

154 }

155 }

156

157 /* Balancing */

158 while (p->father != 0)

159 {

160 p = tree->nodes + p->father - 1;

161

162 if ((p->l_height - p->r_height) == 2)

163 {

164 if (tree->nodes[p->left - 1].l_height

165 == (p->l_height - 1))

166 {

167 /* right rotation */

168

169 /* p is root, tmp is pivot */

170 tmp = tree->nodes + p->left - 1;

171

172 p->left = tmp->right;

173 tmp->right = p - tree->nodes + 1;

174

175 p->l_height = tmp->r_height;

176 tmp->r_height = max(p->l_height, p->r_height)

177 + 1;

178

179 tmp->father = p->father;

180 p->father = tmp - tree->nodes + 1;

181

182 if (p->left != 0)

183 tree->nodes[p->left - 1].father =

184 p - tree->nodes + 1;

185

186 if (tmp->father != 0)

187 {

188 if (tree->nodes[tmp->father - 1].left

189 == p - tree->nodes + 1)

190 tree->nodes[tmp->father

191 - 1].left =

192 tmp - tree->nodes + 1;

193 else

194 tree->nodes[tmp->father

195 - 1].right =

196 tmp - tree->nodes + 1;

197 }

198

199 adjust_heights(tree, p);

200 }

201 else

202 {

203 /* left-right rotation */

204

205 /* p is root's father, tmp is pivot,

206 * tmp2 is root */

207 tmp = tree->nodes

208 + tree->nodes[p->left - 1].right - 1;

209 tmp2 = tree->nodes + tmp->father - 1;

210

211 p->left = tmp->right;

212 tmp2->right = tmp->left;

213 tmp->left = tmp2 - tree->nodes + 1;

214 tmp->right = p - tree->nodes + 1;

215

216 p->l_height = tmp->r_height;

217 tmp2->r_height = tmp->l_height;

218 tmp->l_height = max(tmp2->l_height,

219 tmp2->r_height) + 1;

220 tmp->r_height = max(p->l_height, p->r_height)

221 + 1;

222

223 tmp->father = p->father;

224 p->father = tmp - tree->nodes + 1;

225 tmp2->father = tmp - tree->nodes + 1;

226

227 if (tmp2->right != 0)

228 tree->nodes[tmp2->right - 1].father =

229 tmp2 - tree->nodes + 1;

230 if (p->left != 0)

231 tree->nodes[p->left - 1].father =

232 p - tree->nodes + 1;

233

234 if (tmp->father != 0)

235 {

236 if (tree->nodes[tmp->father - 1].left

237 == p - tree->nodes + 1)

238 tree->nodes[tmp->father

239 - 1].left =

240 tmp - tree->nodes + 1;

241 else

242 tree->nodes[tmp->father

243 - 1].right =

244 tmp - tree->nodes + 1;

245 }

246

247 adjust_heights(tree, p);

248 }

249 }

250 else if ((p->r_height - p->l_height) == 2)

251 {

252 if (tree->nodes[p->right - 1].r_height

253 == (p->r_height - 1))

254 {

255 /* left rotation */

256

257 /* p is root, tmp is pivot */

258

259 tmp = tree->nodes + p->right - 1;

260

261 p->right = tmp->left;

262 tmp->left = p - tree->nodes + 1;

263

264 p->r_height = tmp->l_height;

265 tmp->l_height = max(p->l_height, p->r_height)

266 + 1;

267

268 tmp->father = p->father;

269 p->father = tmp - tree->nodes + 1;

270

271 if (p->right != 0)

272 tree->nodes[p->right - 1].father =

273 p - tree->nodes + 1;

274

275 if (tmp->father != 0)

276 {

277 if (tree->nodes[tmp->father - 1].left

278 == p - tree->nodes + 1)

279 tree->nodes[tmp->father

280 - 1].left =

281 tmp - tree->nodes + 1;

282 else

283 tree->nodes[tmp->father

284 - 1].right =

285 tmp - tree->nodes + 1;

286 }

287

288 adjust_heights(tree, p);

289 }

290 else

291 {

292 /* right-left rotation */

293

294 /* p is root's father, tmp is pivot,

295 * tmp2 is root */

296

297 tmp = tree->nodes +

298 tree->nodes[p->right - 1].left - 1;

299 tmp2 = tree->nodes + tmp->father - 1;

300

301 p->right = tmp->left;

302 tmp2->left = tmp->right;

303 tmp->left = p - tree->nodes + 1;

304 tmp->right = tmp2 - tree->nodes + 1;

305

306 p->r_height = tmp->l_height;

307 tmp2->l_height = tmp->r_height;

308 tmp->l_height = max(p->l_height, p->r_height)

309 + 1;

310 tmp->r_height = max(tmp2->l_height,

311 tmp2->r_height) + 1;

312

313 tmp->father = p->father;

314 p->father = tmp - tree->nodes + 1;

315 tmp2->father = tmp - tree->nodes + 1;

316

317 if (tmp2->left != 0)

318 tree->nodes[tmp2->left - 1].father =

319 tmp2 -tree->nodes + 1;

320 if (p->right != 0)

321 tree->nodes[p->right - 1].father =

322 p -tree->nodes + 1;

323

324 if (tmp->father != 0)

325 {

326 if (tree->nodes[tmp->father - 1].left

327 == p - tree->nodes + 1)

328 tree->nodes[tmp->father

329 - 1].left =

330 tmp - tree->nodes + 1;

331 else

332 tree->nodes[tmp->father

333 - 1].right =

334 tmp - tree->nodes + 1;

335 }

336

337 adjust_heights(tree, p);

338 }

339 }

340 }

341

342 /* Fix root node */

343 p = tree->nodes + tree->root - 1;

344 while (p->father != 0)

345 p = tree->nodes + p->father - 1;

346

347 tree->root = p - tree->nodes + 1;

348 }

349

350 void

351 nacore_avl_tree_for_each(nacore_avl_tree_t tree,

352 void (*callback)(void *content, void *data),

353 void *data)

354 {

355 size_t i;

356

357 for (i = 0; i < tree->count; i++)

358 callback(tree->nodes[i].content, data);

359 }

360

361 void *

362 nacore_avl_tree_find(nacore_avl_tree_t tree, void *key)

363 {

364 struct avl_tree_node *p;

365 int cmp;

366 size_t next;

367

368 if (tree->root == 0)

369 return NULL;

370

371 next = tree->root;

372 do

373 {

374 p = tree->nodes + next - 1;

375 cmp = tree->key_cmp(p->content, key);

376 if (cmp == 0)

377 return p->content;

378 if (cmp < 0)

379 next = p->right;

380 else

381 next = p->left;

382 }

383 while (next != 0);

384

385 return NULL;

386 }

387

388 size_t

389 nacore_avl_tree_get_nodes_count(nacore_avl_tree_t tree)

390 {

391 return tree->count;

392 }

393

394 void

395 nacore_avl_tree_free(nacore_avl_tree_t tree)

396 {

397 free(tree->nodes);

398 free(tree);

399 }

400

401 int

402 nacore_content_cmp_descriptor_by_uri(void *c1, void *c2)

403 {

404 return strcmp(((struct nacore_descriptor *)c1)->uri,

405 ((struct nacore_descriptor *)c2)->uri);

406 }

407

408 int

409 nacore_key_cmp_descriptor_by_uri(void *content, void *key)

410 {

411 return strcmp(((struct nacore_descriptor *)content)->uri, (char *)key);

412 }