/* List Insertion Sorting.
* Implementation history:.
* 2013-09-15, Mars Fu, first version.
*/
#include "stdafx.h"
#include "list_insertion.h"
int
init_list(struct s_clist *hd, int max_cnt, struct s_nodes *nodes)
{
if (hd == NULL) return 0;
if (max_cnt < 0) return 0;
hd->node = NULL;
nodes->cur = hd;
nodes->hd = hd;
memset(nodes->cur, 0, sizeof(struct s_clist));
nodes->nodes_cnt = 0;
nodes->max_nodes_cnt = max_cnt;
debug("nodes->max_nodes_cnt %d \r\n", nodes->max_nodes_cnt);
return 1;
}
int
insert_list_sort(struct s_node *node, struct s_nodes *nodes, cmp_func cmp)
{
struct s_clist *tmp;
struct s_clist *next;
if (node == NULL) return 0;
if (nodes->cur == NULL) return 0;
next = (struct s_clist *)malloc(sizeof(struct s_clist));
if (next == NULL) {
debug("malloc list failed \r\n");
return 0;
}
next->node = node;
tmp = nodes->hd->pre;
if (tmp == NULL) {
tmp = nodes->hd;
tmp->next = next;
next->pre = tmp;
next->next = nodes->hd;
nodes->hd->pre = next;
}
else {
while (tmp != NULL) {
if (tmp->node == NULL) break;
if (cmp(tmp->node->key, node->key) < 0) break;
tmp = tmp->pre;
}
next->next = tmp->next;
tmp->next->pre = next;
tmp->next = next;
next->pre = tmp;
}
nodes->cur = nodes->hd->pre;
nodes->nodes_cnt++;
return 1;
}
int
is_list_full(struct s_nodes *nodes)
{
return (nodes->nodes_cnt >= nodes->max_nodes_cnt);
}
int
get_list_cnt(struct s_nodes *nodes)
{
return nodes->nodes_cnt;
}
int
delete_item_from_list(struct s_node *node, struct s_nodes *nodes)
{
struct s_clist *cur;
if(node == NULL) return 0;
cur = nodes->hd;
cur = cur->next;
while(cur->node != NULL) {
if(cur->node != node) {
cur = cur->next;
continue;
}
cur->pre->next = cur->next;
cur->next->pre = cur->pre;
cur->next = NULL;
cur->pre = NULL;
free(cur->node);
free(cur);
nodes->nodes_cnt--;
return 1;
}
return 0;
}
#ifdef LIST_INSERTION_DEBUG
static int
int_increasing_cmp(void* lv, void* rv)
{
int tmp_lv, tmp_rv;
tmp_lv = *(int*)lv;
tmp_rv = *(int*)rv;
return (tmp_lv - tmp_rv);
}
static void
debug_func(void*src, int n, int h)
{
int i;
debug("%d-sort:\r\n----\r\n", h);
for (i = 0; i < n; ++i) {
debug("%d ", *((int*)src + i));
}
debug("\r\n----\r\n");
}
int
main(int argc, char* argv[])
{
int i;
int cnt;
const int int_items[] = { 503, 87, 512, 61, 908, 170, 897, 275,
653, 426, 154, 509, 612, 677, 765, 703
};
int ret;
struct s_clist hd;
struct s_nodes nodes;
struct s_node *node;
struct s_clist *cur;
debug("[Testing list insertion sort].. \r\n");
ret = init_list(&hd, 1000, &nodes);
if (!ret) goto END;
cnt = sizeof(int_items)/sizeof(int_items[0]);
debug("src database:\r\n----\r\n");
for (i = 0; i < cnt; ++i) {
debug("%d ", int_items[i]);
}
debug("\r\n----\r\n");
for (i = 0; i < cnt; ++i) {
node = (struct s_node*)malloc(sizeof(struct s_node));
if (node == NULL) goto END;
node->key = (void*)(&int_items[i]);
ret = insert_list_sort(node, &nodes, int_increasing_cmp);
if (!ret) {
debug("failed. \r\n");
goto END;
}
}
debug("dst database:\r\n----\r\n");
cur = nodes.hd->next;
while(cur->node != NULL) {
debug("%d ", *(int*)cur->node->key);
cur = cur->next;
}
debug("\r\n----\r\n");
debug("\r\n");
debug("[Testing list insertion sort].. done. \r\n");
END:
while(1);
return 0;
}
#endif /* LIST_INSERTION_DEBUG */
#ifndef __LIST_INSERTION_H__
#define __LIST_INSERTION_H__
#define LIST_INSERTION_DEBUG
typedef int(*cmp_func)(void*, void*);
typedef void (*dbg_func)(void*, int, int);
struct s_node{
void* key;
void *data;
};
struct s_clist{
struct s_clist *pre;
struct s_clist *next;
struct s_node *node;
};
struct s_nodes
{
struct s_clist *hd;
int nodes_cnt;
int max_nodes_cnt;
struct s_clist *cur;
};
int init_list(struct s_clist *hd, int max_cnt, struct s_nodes *nodes);
int insert_list_sort(struct s_node *node, struct s_nodes *nodes);
int is_list_full(struct s_nodes *nodes);
int get_list_cnt(struct s_nodes *nodes);
int delete_item_from_list(struct s_node *node, struct s_nodes *nodes);
#endif /* __LIST_INSERTION_H__ */
#pragma once
#include <windows.h>
#ifdef _WIN32
#define msleep(x) Sleep(x)
#endif
#include <stdio.h>
#include <tchar.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <math.h>
#define MY_DEBUG
#ifdef MY_DEBUG
#define debug printf
#else
#define debug(x,argc, __VA_ARGS__) ;
#endif /* MY_DEBUG */
#define F_S() debug("[%s]..\r\n", __FUNCTION__)
#define F_E() debug("[%s]..done. \r\n", __FUNCTION__)
Enjoy :)
Mars
Sep 15th, 2013
