Simcllist linked list open source library Introduction &
example program
- SimCList is a high quality C (C++ embeddable) library for handling lists.
- SimCList is available for free, under restrictions imposed by the BSD license.
- Need to explore below thread safe mechanism:
- The SimCList library is thread safe, meaning that many threads can run SimCList operators on different lists concurrently without hurt
Memory:
- SimClist free only the containter memory, suppose if you use strucute value & allocate memory for that structure then you need to take care of that memory, hence we have to store that allocated memory in one place & have to free after delete the container.
- Or you have to get first API to get memory & then delete first API to delete and then free the memory, so that we don't need to store allocated memory.
- Best way is allow SimClist to allocate memory by setting list_attributes_copy() API with size of strucute function pointer, so that SimClist will allocate memory for container & data also, while deleting, SimcList will delete the data & container memory.
API & Description:
- list_init -> Initialize the global list variable
- list_attributes_seeker -> Intall the search function pointer for list_seek
- list_attributes_copy -> Intall function pointer to get the size of data (strucute) so that SimcList allocate memory for this data.
- list_insert_at -> Insert the data into the corresponding place 0-> to insert first
- list_seek -> Used to search the data using the keyword, list_attributes_seeker() installed the function to search the keyword.
- list_size -> Get the total number of node in the list.
- list_get_at -> Get the node from the list in particular position , 0 -> get first.
To display:
- list_iterator_start -> starting an iteration "session"
- In while loop:
- list_iterator_hasnext -> Use this in while loop for check , tell whether more values available
- list_iterator_next -> Get the node from the list
- list_iterator_stop -> stop the iteration "session". After while must call this otherwise, next time it will not start from first, face issue,
To delete & check:
- list_delete_at -> Delete the node from the list in particular position, 0-> delete first
- list_empty -> Check list is empty, if empty return 1 otherwise return 0
- list_clear -> Delete all the node in the list
- list_destroy -> It will destroy the compelete list, need to call list_init if we need to use the list again.
License:
Program:
- SimCList is BSD-licensed, so you can simply its whole source code into your application.
Program:
* Simcllist linked list example by
Velraj.K
* Check : http://velrajcoding.blogspot.in
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h> /* for srandom() */
#include "../simclist.h"
//#define N 100000
#define N 10
#define LEN 12
struct foo_s {
int a, b;
char c[LEN];
};
//#define VEL_DYNAMIC_MEM
int seeker(const void *el, const void *indicator) {
if (((struct foo_s *)el)->a == *(int *)indicator)
return 1;
return 0;
}
* Check : http://velrajcoding.blogspot.in
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h> /* for srandom() */
#include "../simclist.h"
//#define N 100000
#define N 10
#define LEN 12
struct foo_s {
int a, b;
char c[LEN];
};
//#define VEL_DYNAMIC_MEM
int seeker(const void *el, const void *indicator) {
if (((struct foo_s *)el)->a == *(int *)indicator)
return 1;
return 0;
}
/* This will used to inform list to
copy the data for this size */
size_t mymeter(const void *el) {
return (sizeof(struct foo_s));
}
void display_list(list_t *list)
{
struct foo_s *temp2 = NULL;
printf("Displaying the list \n");
list_iterator_start(list); /* starting an iteration "session" */
while (list_iterator_hasnext(list)) { /* tell whether more values available */
temp2 = list_iterator_next(list);
printf("%d\n", temp2->a);
}
list_iterator_stop(list); /* stop the iteration "session" */
return;
}
void insert_list(list_t *list, int num)
{
int i =0;
struct foo_s el;
#if defined VEL_DYNAMIC_MEM
struct foo_s *temp = NULL;
#endif
for (i = 0; i < num; i++) {
#if defined VEL_DYNAMIC_MEM
/* Should not allocate memory for data, because if we didn't give the
then it will free only the containers not the element data */
temp = malloc(sizeof(struct foo_s));
temp->a = i;
temp->b = 3*i;
snprintf(temp->c, LEN, "%d-%d", temp->a, temp->b);
list_insert_at(list, temp, i);
if (i == 100) {
printf("Vel memory at i = 100 is = %p\n", temp);
}
#else
el.a = i;
el.b = 3*i;
snprintf(el.c, LEN, "%d-%d", el.a, el.b);
list_insert_at(list, & el, i);
#endif
}
}
void line(char ch)
{
int i = 0;
for (i = 0; i < 80; printf("%c", ch), i++);
printf("\n");
return;
}
int main()
{
list_t l;
struct foo_s el, *new = NULL;
struct foo_s *temp2 = NULL;
int i = 0, j = 0;
#if defined VEL_DYNAMIC_MEM
struct foo_s *temp = NULL;
#endif
line('*');
printf("Vel starting Size of list_t = %zu \n", sizeof(list_t));
list_init(& l);
list_attributes_seeker(&l, seeker);
#if defined VEL_DYNAMIC_MEM
printf("Vel Using the dynamic memory allocation for node \n");
#else
printf("Vel Allow list to allocation memory for node \n");
/* To copy data install function to get the size */
list_attributes_copy(&l, mymeter, 1);
#endif
insert_list(&l, N);
srandom(time(NULL));
j = 5;
/* it retrun the node with same our dynamic memory */
new = (struct foo_s *)list_seek(&l, &j);
if (new) {
printf("Vel list_seek found node with key as 5 = %d Addres is = %p \n", new->a, new);
}
line('*');
for (i = 0; i < N/4; i++) {
j = random() % list_size(&l);
el = *(struct foo_s *)list_seek(&l, &j);
if (el.a != j) {
printf("KO: %d retrieved %d\n", j, el.a);
return 1;
}
}
/* Return element if found otherwise return NULL */
temp2 = (struct foo_s *)list_get_at(&l, 0);
if (temp2) {
printf("First elemet is a = %d, Addr = %p list size = %d\n", temp2->a, temp2, list_size(&l));
} else {
printf("Element not found \n");
}
line('*');
display_list(&l);
line('*');
printf("Deleting the 2 node from the staring of the list \n");
list_delete_at(&l, 0);
list_delete_at(&l, 0);
temp2 = (struct foo_s *)list_get_at(&l, 0);
if (temp2) {
/*
* list_size(const list_t *restrict l):
* Description: Inspect the number of elements in the list.
* Input : l list to operate
* Returns: number of elements currently held by the list
* Vel: This is not looping all the element to find the number of element,
* just return l->numels value, it contain the total no. of element.
*/
printf("First elemet is a = %d, Addr = %p list size = %d \n", temp2->a, temp2, list_size(&l));
} else {
printf("Element not found on 2nd get \n");
}
line('*');
display_list(&l);
line('*');
printf("list_empty output %d list_size:%d \n", list_empty(&l), list_size(&l));
/*
* list_empty(const list_t *restrict l):
* Description : inspect whether the list is empty.
* Input : l list to operate
* Returns : 0 iff the list is not empty, if 1 then the list is empty(That is no element in the list)
*/
if (list_empty(&l) == 0) {
display_list(&l);
/* After clear we can able to insert the node */
list_clear(&l);
insert_list(&l, 1);
printf("Tryign to insert \n");
line('*');
display_list(&l);
line('*');
list_destroy(&l);
printf("Destroying the item and the list \n");
/* Below insert is wrong becasue we deleted the string
* Valgrind thrown an following error:
* Invalid write of size 8
*/
// insert_list(&l, 1);
// printf("Tryign to insert \n");
} else {
/* Even the item is empty need to destroy the list to release all the internal using memory
* At the time of initialization(list_init) it will allocate memory for internal purpose,
* we should clear that memory when clear the list
*/
list_destroy(&l);
printf("Destroying only the list \n");
}
printf("list_empty output = %d \n", list_empty(&l));
return 0;
}
/*
* list_append(list_t *restrict l, const void *data):
* Description : append data at the end of the list.
* Input : l list to operate & data pointer to user data to append
* Returns : 1 for success. < 0 for failure.
* Vel : It won't do loop to find the last, It use the list_findpos to find the last
* This function split the give position into 4 quarter, for last they start from end to decrease.
* Our case append end will start on end only, so first check in for loop itself getting the data.
*/
size_t mymeter(const void *el) {
return (sizeof(struct foo_s));
}
void display_list(list_t *list)
{
struct foo_s *temp2 = NULL;
printf("Displaying the list \n");
list_iterator_start(list); /* starting an iteration "session" */
while (list_iterator_hasnext(list)) { /* tell whether more values available */
temp2 = list_iterator_next(list);
printf("%d\n", temp2->a);
}
list_iterator_stop(list); /* stop the iteration "session" */
return;
}
void insert_list(list_t *list, int num)
{
int i =0;
struct foo_s el;
#if defined VEL_DYNAMIC_MEM
struct foo_s *temp = NULL;
#endif
for (i = 0; i < num; i++) {
#if defined VEL_DYNAMIC_MEM
/* Should not allocate memory for data, because if we didn't give the
then it will free only the containers not the element data */
temp = malloc(sizeof(struct foo_s));
temp->a = i;
temp->b = 3*i;
snprintf(temp->c, LEN, "%d-%d", temp->a, temp->b);
list_insert_at(list, temp, i);
if (i == 100) {
printf("Vel memory at i = 100 is = %p\n", temp);
}
#else
el.a = i;
el.b = 3*i;
snprintf(el.c, LEN, "%d-%d", el.a, el.b);
list_insert_at(list, & el, i);
#endif
}
}
void line(char ch)
{
int i = 0;
for (i = 0; i < 80; printf("%c", ch), i++);
printf("\n");
return;
}
int main()
{
list_t l;
struct foo_s el, *new = NULL;
struct foo_s *temp2 = NULL;
int i = 0, j = 0;
#if defined VEL_DYNAMIC_MEM
struct foo_s *temp = NULL;
#endif
line('*');
printf("Vel starting Size of list_t = %zu \n", sizeof(list_t));
list_init(& l);
list_attributes_seeker(&l, seeker);
#if defined VEL_DYNAMIC_MEM
printf("Vel Using the dynamic memory allocation for node \n");
#else
printf("Vel Allow list to allocation memory for node \n");
/* To copy data install function to get the size */
list_attributes_copy(&l, mymeter, 1);
#endif
insert_list(&l, N);
srandom(time(NULL));
j = 5;
/* it retrun the node with same our dynamic memory */
new = (struct foo_s *)list_seek(&l, &j);
if (new) {
printf("Vel list_seek found node with key as 5 = %d Addres is = %p \n", new->a, new);
}
line('*');
for (i = 0; i < N/4; i++) {
j = random() % list_size(&l);
el = *(struct foo_s *)list_seek(&l, &j);
if (el.a != j) {
printf("KO: %d retrieved %d\n", j, el.a);
return 1;
}
}
/* Return element if found otherwise return NULL */
temp2 = (struct foo_s *)list_get_at(&l, 0);
if (temp2) {
printf("First elemet is a = %d, Addr = %p list size = %d\n", temp2->a, temp2, list_size(&l));
} else {
printf("Element not found \n");
}
line('*');
display_list(&l);
line('*');
printf("Deleting the 2 node from the staring of the list \n");
list_delete_at(&l, 0);
list_delete_at(&l, 0);
temp2 = (struct foo_s *)list_get_at(&l, 0);
if (temp2) {
/*
* list_size(const list_t *restrict l):
* Description: Inspect the number of elements in the list.
* Input : l list to operate
* Returns: number of elements currently held by the list
* Vel: This is not looping all the element to find the number of element,
* just return l->numels value, it contain the total no. of element.
*/
printf("First elemet is a = %d, Addr = %p list size = %d \n", temp2->a, temp2, list_size(&l));
} else {
printf("Element not found on 2nd get \n");
}
line('*');
display_list(&l);
line('*');
printf("list_empty output %d list_size:%d \n", list_empty(&l), list_size(&l));
/*
* list_empty(const list_t *restrict l):
* Description : inspect whether the list is empty.
* Input : l list to operate
* Returns : 0 iff the list is not empty, if 1 then the list is empty(That is no element in the list)
*/
if (list_empty(&l) == 0) {
display_list(&l);
/* After clear we can able to insert the node */
list_clear(&l);
insert_list(&l, 1);
printf("Tryign to insert \n");
line('*');
display_list(&l);
line('*');
list_destroy(&l);
printf("Destroying the item and the list \n");
/* Below insert is wrong becasue we deleted the string
* Valgrind thrown an following error:
* Invalid write of size 8
*/
// insert_list(&l, 1);
// printf("Tryign to insert \n");
} else {
/* Even the item is empty need to destroy the list to release all the internal using memory
* At the time of initialization(list_init) it will allocate memory for internal purpose,
* we should clear that memory when clear the list
*/
list_destroy(&l);
printf("Destroying only the list \n");
}
printf("list_empty output = %d \n", list_empty(&l));
return 0;
}
/*
* list_append(list_t *restrict l, const void *data):
* Description : append data at the end of the list.
* Input : l list to operate & data pointer to user data to append
* Returns : 1 for success. < 0 for failure.
* Vel : It won't do loop to find the last, It use the list_findpos to find the last
* This function split the give position into 4 quarter, for last they start from end to decrease.
* Our case append end will start on end only, so first check in for loop itself getting the data.
*/
Output:
labuser@labuser-virtual-machine:~/image/software/simclist-1.5/regrtest$
valgrind ./a.out
==13116== Memcheck, a memory error detector
==13116== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==13116== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==13116== Command: ./a.out
==13116==
********************************************************************************
Vel starting Size of list_t = 120
Vel Allow list to allocation memory for node
Vel list_seek found node with key as 5 = 5 Addres is = 0x5406590
********************************************************************************
First elemet is a = 0, Addr = 0x54061d0 list size = 10
********************************************************************************
Displaying the list
0
1
2
3
4
5
6
7
8
9
********************************************************************************
Deleting the 2 node from the staring of the list
First elemet is a = 2, Addr = 0x5406350 list size = 8
********************************************************************************
Displaying the list
2
3
4
5
6
7
8
9
********************************************************************************
list_empty output 0 list_size:8
Displaying the list
2
3
4
5
6
7
8
9
Tryign to insert
********************************************************************************
Displaying the list
0
********************************************************************************
Destroying the item and the list
list_empty output = 1
==13116==
==13116== HEAP SUMMARY:
==13116== in use at exit: 0 bytes in 0 blocks
==13116== total heap usage: 24 allocs, 24 frees, 548 bytes allocated
==13116==
==13116== All heap blocks were freed -- no leaks are possible
==13116==
==13116== For counts of detected and suppressed errors, rerun with: -v
==13116== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
labuser@labuser-virtual-machine:~/image/software/simclist-1.5/regrtest$
labuser@labuser-virtual-machine:~/image/software/simclist-1.5/regrtest$
==13116== Memcheck, a memory error detector
==13116== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==13116== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==13116== Command: ./a.out
==13116==
********************************************************************************
Vel starting Size of list_t = 120
Vel Allow list to allocation memory for node
Vel list_seek found node with key as 5 = 5 Addres is = 0x5406590
********************************************************************************
First elemet is a = 0, Addr = 0x54061d0 list size = 10
********************************************************************************
Displaying the list
0
1
2
3
4
5
6
7
8
9
********************************************************************************
Deleting the 2 node from the staring of the list
First elemet is a = 2, Addr = 0x5406350 list size = 8
********************************************************************************
Displaying the list
2
3
4
5
6
7
8
9
********************************************************************************
list_empty output 0 list_size:8
Displaying the list
2
3
4
5
6
7
8
9
Tryign to insert
********************************************************************************
Displaying the list
0
********************************************************************************
Destroying the item and the list
list_empty output = 1
==13116==
==13116== HEAP SUMMARY:
==13116== in use at exit: 0 bytes in 0 blocks
==13116== total heap usage: 24 allocs, 24 frees, 548 bytes allocated
==13116==
==13116== All heap blocks were freed -- no leaks are possible
==13116==
==13116== For counts of detected and suppressed errors, rerun with: -v
==13116== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
labuser@labuser-virtual-machine:~/image/software/simclist-1.5/regrtest$
labuser@labuser-virtual-machine:~/image/software/simclist-1.5/regrtest$
Scenario 2: compiled with allocate memory dynamic and found the
memory leak:
labuser@labuser-virtual-machine:~/image/software/simclist-1.5/regrtest$ vi vel_seeker_add_del.c
labuser@labuser-virtual-machine:~/image/software/simclist-1.5/regrtest$ gcc vel_seeker_add_del.c -DVEL_DYNAMIC_MEM -lsimclist
labuser@labuser-virtual-machine:~/image/software/simclist-1.5/regrtest$ valgrind ./a.out
==13626== Memcheck, a memory error detector
==13626== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==13626== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==13626== Command: ./a.out
==13626==
********************************************************************************
Vel starting Size of list_t = 120
Vel Using the dynamic memory allocation for node
Vel list_seek found node with key as 5 = 5 Addres is = 0x5406530
********************************************************************************
First elemet is a = 0, Addr = 0x5406170 list size = 10
********************************************************************************
Displaying the list
0
1
2
3
4
5
6
7
8
9
********************************************************************************
Deleting the 2 node from the staring of the list
First elemet is a = 2, Addr = 0x54062f0 list size = 8
********************************************************************************
Displaying the list
2
3
4
5
6
7
8
9
********************************************************************************
list_empty output 0 list_size:8
Displaying the list
2
3
4
5
6
7
8
9
Tryign to insert
********************************************************************************
Displaying the list
0
********************************************************************************
Destroying the item and the list
list_empty output = 1
==13626==
==13626== HEAP SUMMARY:
==13626== in use at exit: 220 bytes in 11 blocks
==13626== total heap usage: 24 allocs, 13 frees, 548 bytes allocated
==13626==
==13626== LEAK SUMMARY:
==13626== definitely lost: 220 bytes in 11 blocks
==13626== indirectly lost: 0 bytes in 0 blocks
==13626== possibly lost: 0 bytes in 0 blocks
==13626== still reachable: 0 bytes in 0 blocks
==13626== suppressed: 0 bytes in 0 blocks
==13626== Rerun with --leak-check=full to see details of leaked memory
==13626==
==13626== For counts of detected and suppressed errors, rerun with: -v
==13626== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Before restart read below reference:
http://mij.oltrelinux.com/devel/simclist/sneakpeakapi.html
http://mij.oltrelinux.com/devel/simclist/
No comments:
Post a Comment