Mercurial > hg > th-libs

comparison th_datastruct.c @ 759:618c7fa3a4f8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add th_llist_mergesort() for sorting linked lists.
author Matti Hamalainen <ccr@tnsp.org>
date Sun, 05 Feb 2023 02:16:22 +0200
parents 72fb5ce9086a
children 2263dd13cf2d
comparison
equal deleted inserted replaced
758:72fb5ce9086a 759:618c7fa3a4f8
338 338
339 return NULL; 339 return NULL;
340 } 340 }
341 341
342 342
343 static th_llist_t *th_llist_mergesort_merge(th_llist_t *left, th_llist_t *right,
344 int (compare)(const th_llist_t *lnode, const th_llist_t *rnode, void *userdata),
345 void *userdata)
346 {
347 th_llist_t *result;
348
349 if (left == NULL)
350 return right;
351 else
352 if (right == NULL)
353 return left;
354
355 if (compare(left, right, userdata))
356 {
357 result = left;
358 result->next = th_llist_mergesort_merge(left->next, right, compare, userdata);
359 }
360 else
361 {
362 result = right;
363 result->next = th_llist_mergesort_merge(left, right->next, compare, userdata);
364 }
365
366 if (result->next != NULL)
367 result->prev = result->prev;
368
369 return result;
370 }
371
372
373 static void th_llist_mergesort_do(th_llist_t **list,
374 int (compare)(const th_llist_t *lnode, const th_llist_t *rnode, void *userdata),
375 void *userdata)
376 {
377 th_llist_t *head = *list, *left, *right, *slow, *fast;
378
379 if (head == NULL || head->next == NULL)
380 return;
381
382 slow = head;
383 fast = head->next;
384 while (fast != NULL)
385 {
386 fast = fast->next;
387 if (fast != NULL)
388 {
389 slow = slow->next;
390 fast = fast->next;
391 }
392 }
393
394 left = head;
395 right = slow->next;
396 slow->next = NULL;
397
398 th_llist_mergesort_do(&left, compare, userdata);
399 th_llist_mergesort_do(&right, compare, userdata);
400
401 *list = th_llist_mergesort_merge(left, right, compare, userdata);
402 }
403
404
405 void th_llist_mergesort(th_llist_t **list,
406 int (compare)(const th_llist_t *lnode, const th_llist_t *rnode, void *userdata),
407 void *userdata)
408 {
409 if (list != NULL && *list != NULL)
410 {
411 size_t num = (*list)->num;
412 th_llist_mergesort_do(list, compare, userdata);
413 (*list)->num = num;
414 }
415 }
416
417
343 /* 418 /*
344 * Ringbuffers 419 * Ringbuffers
345 */ 420 */
346 int th_ringbuf_init(th_ringbuf_t *buf, const size_t size, void (*mdeallocator)(void *data)) 421 int th_ringbuf_init(th_ringbuf_t *buf, const size_t size, void (*mdeallocator)(void *data))
347 { 422 {