naspro: d7568c8379c1 naspro-core/src/avl.c

naspro

view naspro-core/src/avl.c @ 163:d7568c8379c1

Initiial DSSI support + reorganization

author	Stefano D'Angelo <zanga.mail@gmail.com>
date	Fri Sep 11 13:31:52 2009 +0200 (2009-09-11)
parents	src/core/avl.c@60edbe170fed
children	71372f617827

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 /* TODO: Nothing here is thread-safe. */

17 struct avl_tree_node

18 {

19 size_t father;

20 size_t left;

21 size_t right;

22 size_t l_height;

23 size_t r_height;

24 void *content;

25 };

27 struct _nacore_avl_tree

28 {

29 size_t root;

30 struct avl_tree_node *nodes;

31 size_t count;

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

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

35 };

37 nacore_avl_tree_t

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

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

40 {

41 nacore_avl_tree_t tree;

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

44 if (tree == NULL)

45 return NULL;

47 tree->root = 0;

48 tree->nodes = NULL;

49 tree->count = 0;

50 tree->content_cmp = content_cmp;

51 tree->key_cmp = key_cmp;

53 return tree;

54 }

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

58 #if 0

59 static void

60 node_dump(nacore_avl_tree_t tree, struct avl_tree_node *node)

61 {

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

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

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

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

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

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

68 if (node->left != 0)

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

70 if (node->right != 0)

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

72 }

74 static void

75 tree_dump(nacore_avl_tree_t tree)

76 {

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

78 if (tree->root != 0)

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

80 }

81 #endif

83 static void

84 adjust_heights(nacore_avl_tree_t tree, struct avl_tree_node *p)

85 {

86 struct avl_tree_node *p2;

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

89 p != NULL;

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

91 {

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

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

94 else

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

96 }

97 }

99 void

100 nacore_avl_tree_add(nacore_avl_tree_t tree, void *content)

101 {

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

103

104 /* Allocation */

105 tmp = realloc(tree->nodes,

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

107 if (tmp == NULL)

108 return;

109

110 tree->nodes = tmp;

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

112

113 tmp->content = content;

114 tmp->father = 0;

115 tmp->left = 0;

116 tmp->right = 0;

117 tmp->l_height = 0;

118 tmp->r_height = 0;

119 tree->count++;

120

121 /* Insertion */

122 if (tree->root == 0)

123 {

124 tree->root = 1;

125 return;

126 }

127

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

129 while (1)

130 {

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

132 {

133 if (p->right != 0)

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

135 else

136 {

137 p->r_height = 1;

138 p->right = tree->count;

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

140 adjust_heights(tree, p);

141 break;

142 }

143 }

144 else

145 {

146 if (p->left != 0)

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

148 else

149 {

150 p->l_height = 1;

151 p->left = tree->count;

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

153 adjust_heights(tree, p);

154 break;

155 }

156 }

157 }

158

159 /* Balancing */

160 while (p->father != 0)

161 {

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

163

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

165 {

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

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

168 {

169 /* right rotation */

170

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

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

173

174 p->left = tmp->right;

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

176

177 p->l_height = tmp->r_height;

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

179 + 1;

180

181 tmp->father = p->father;

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

183

184 if (p->left != 0)

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

186 p - tree->nodes + 1;

187

188 if (tmp->father != 0)

189 {

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

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

192 tree->nodes[tmp->father

193 - 1].left =

194 tmp - tree->nodes + 1;

195 else

196 tree->nodes[tmp->father

197 - 1].right =

198 tmp - tree->nodes + 1;

199 }

200

201 adjust_heights(tree, p);

202 }

203 else

204 {

205 /* left-right rotation */

206

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

208 * tmp2 is root */

209 tmp = tree->nodes

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

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

212

213 p->left = tmp->right;

214 tmp2->right = tmp->left;

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

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

217

218 p->l_height = tmp->r_height;

219 tmp2->r_height = tmp->l_height;

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

221 tmp2->r_height) + 1;

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

223 + 1;

224

225 tmp->father = p->father;

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

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

228

229 if (tmp2->right != 0)

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

231 tmp2 - tree->nodes + 1;

232 if (p->left != 0)

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

234 p - tree->nodes + 1;

235

236 if (tmp->father != 0)

237 {

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

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

240 tree->nodes[tmp->father

241 - 1].left =

242 tmp - tree->nodes + 1;

243 else

244 tree->nodes[tmp->father

245 - 1].right =

246 tmp - tree->nodes + 1;

247 }

248

249 adjust_heights(tree, p);

250 }

251 }

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

253 {

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

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

256 {

257 /* left rotation */

258

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

260

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

262

263 p->right = tmp->left;

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

265

266 p->r_height = tmp->l_height;

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

268 + 1;

269

270 tmp->father = p->father;

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

272

273 if (p->right != 0)

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

275 p - tree->nodes + 1;

276

277 if (tmp->father != 0)

278 {

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

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

281 tree->nodes[tmp->father

282 - 1].left =

283 tmp - tree->nodes + 1;

284 else

285 tree->nodes[tmp->father

286 - 1].right =

287 tmp - tree->nodes + 1;

288 }

289

290 adjust_heights(tree, p);

291 }

292 else

293 {

294 /* right-left rotation */

295

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

297 * tmp2 is root */

298

299 tmp = tree->nodes +

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

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

302

303 p->right = tmp->left;

304 tmp2->left = tmp->right;

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

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

307

308 p->r_height = tmp->l_height;

309 tmp2->l_height = tmp->r_height;

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

311 + 1;

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

313 tmp2->r_height) + 1;

314

315 tmp->father = p->father;

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

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

318

319 if (tmp2->left != 0)

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

321 tmp2 -tree->nodes + 1;

322 if (p->right != 0)

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

324 p -tree->nodes + 1;

325

326 if (tmp->father != 0)

327 {

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

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

330 tree->nodes[tmp->father

331 - 1].left =

332 tmp - tree->nodes + 1;

333 else

334 tree->nodes[tmp->father

335 - 1].right =

336 tmp - tree->nodes + 1;

337 }

338

339 adjust_heights(tree, p);

340 }

341 }

342 }

343

344 /* Fix root node */

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

346 while (p->father != 0)

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

348

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

350 }

351

352 void

353 nacore_avl_tree_for_each(nacore_avl_tree_t tree,

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

355 void *data)

356 {

357 size_t i;

358

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

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

361 }

362

363 void *

364 nacore_avl_tree_find(nacore_avl_tree_t tree, void *key)

365 {

366 struct avl_tree_node *p;

367 int cmp;

368 size_t next;

369

370 if (tree->root == 0)

371 return NULL;

372

373 next = tree->root;

374 do

375 {

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

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

378 if (cmp == 0)

379 return p->content;

380 if (cmp < 0)

381 next = p->right;

382 else

383 next = p->left;

384 }

385 while (next != 0);

386

387 return NULL;

388 }

389

390 size_t

391 nacore_avl_tree_get_nodes_count(nacore_avl_tree_t tree)

392 {

393 return tree->count;

394 }

395

396 void

397 nacore_avl_tree_free(nacore_avl_tree_t tree)

398 {

399 free(tree->nodes);

400 free(tree);

401 }

402

403 int

404 nacore_content_cmp_descriptor_by_uri(void *c1, void *c2)

405 {

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

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

408 }

409

410 int

411 nacore_key_cmp_descriptor_by_uri(void *content, void *key)

412 {

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

414 }