Simcllist linked list open source library sorting example program

Simcllist linked list open source library sorting example program

• Sorting will sort the master list, it won't have any separate list for sort.
• Simclist not support the single data place in two list, like one list as master and another list will be sorted one.
• EG for 1 node to be a member of 2 list:
•  linux list.h or bsd's queue.h it is possible to have one node be a member of two lists
• Thus one list is sorted by time and the other list is sorted by something else, like MAC or an order that matches the dpi data.

Program:

/* Simclist sorting by Velraj.K
 * Check : http://velrajcoding.blogspot.in
 */


#include 
#include 
#include 
#include 

#include "../simclist.h"

#include "printlist.c"

#define N       25

void line(char ch)
{
    int i = 0;

    for (i = 0; i < 80; printf("%c", ch), i++);

    printf("\n");

    return;
}
void display_list(list_t *list)
{
    int *temp2 = NULL;
    if (list_size(list) == 0) {
        printf("List is empty\n");
    }


    printf("\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);
    }
    list_iterator_stop(list);         /* stop the iteration "session" */

    return;
}


int main() {
    list_t l;
    int i, j, newpos, els[N];

    srandom(time(NULL));
    list_init(&l);

    list_attributes_copy(&l, list_meter_int32_t, 1);
    list_attributes_comparator(&l, list_comparator_int32_t);

    /* generate an unsorted list of values from 0 to N */
    printf("Test 2: random insertions and deletions ... \n");
    fflush(stdout);
    els[0] = 0;
    for (i = 1; i < N; i++) {
        els[i] = i;
        newpos = random() % (i + 1);
        j = els[newpos];
        els[newpos] = i;
        els[i] = j;
    }


    for (i = 0; i < N; i++) {
        list_append(&l, & els[i]);
    }
    line('=');
    printf("Displaying the list:\n");
    display_list(&l);
    printf("Insertion passed.\n");
    line('*');

#if 0
    printf("Test 3: positioning (The Revenge) ... ");
    fflush(stdout);
    for (i = 0; i < N; i++) {
        assert(*(int *)list_get_at(&l, i) == i);
    }
    printf("passed.\n");
#endif

    printf("Test 4: sorting ... ");
    fflush(stdout);
    assert(list_sort(&l, -1) == 0);

    printf("\nDisplaying the list:\n");
    display_list(&l);
    line('*');

    return 0;
}

Simcllist linked list open source library Introduction & example program

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:

• 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;
}

/* 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.
 */

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$

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/

How to check the return value of sscanf

Check SScanf return value:

int sscanf(const char *str, const char *format, ...);

Description:

sscanf() reads its input from the character string pointed to by str

1. sscanf return number of variable written into the buffer, so that we can check retun value with number of variable return
2. we could not do the same in snprint, because it return the number buffer writting, 

      Example : Suppose write (%s,%s, "Vel", "kutralam"), then sscanf return 2 since 2 variable is written, but snprintf return 11 because it return number of character written

hh modifier:

As for h, but the next pointer is a pointer to a signed char or unsigned char.
This hh modifier is used to print the mac address(octal)

Return:

  Return the number of input items successfully matched and assigned.
  Which can be fewer than provided for, or even zero in the event of an early matching failure.

Program:

/* Sscanf return value checker by Velraj.K
 * Check : http://velrajcoding.blogspot.in
 */


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>

int main()
{
    int ret = 0;
    unsigned char mac_addr[6] = {0};
    char *mac_value_buf = NULL;
    unsigned int int_value[6];
    int count = 0;
    char str[256] = {0};
//    uint32_t new;

    do {
    if (count == 0) {
        mac_value_buf = "000C2956BAF5,1,2,3,4,5,6";
    } else {
        mac_value_buf = "000C2956:BAF5,1,2,3,4,5";
    }
    count++;
    printf("\n\n\t\t ************* Mac buff value = %s Start ****************\n", mac_value_buf);

    /* Here using 04d, this is not needed */
    ret = sscanf(mac_value_buf, "%02hhx%02hhx%02hhx%02hhx%02hhx%02hhx,%04d,%04d,%04d,%04d,%04d,%04d",
            &mac_addr[0], &mac_addr[1],
            &mac_addr[2], &mac_addr[3],
            &mac_addr[4], &mac_addr[5],
            &int_value[0], &int_value[1],
            &int_value[2], &int_value[3],
            &int_value[4], &int_value[5]);
    /*
     * Reading 12 variable, so sscanf return 12 then all the values are read successfully,
     * and no error, otherwise error in reading
     */

    if (ret != 12) {
        printf("Error in retrieve the data from buffer mac_value_buf = %s \n", mac_value_buf);
    } else {
        printf("sscanf ret = %d dev inf = %d inf[5] = %d \n", ret, int_value[0], int_value[5]);
    }

     memset(int_value, 0, sizeof(int_value));

     /* Here using %d, this is enough */
     ret = sscanf(mac_value_buf, "%02hhx%02hhx%02hhx%02hhx%02hhx%02hhx,%d,%d,%d,%d,%d,%d",
             &mac_addr[0], &mac_addr[1], &mac_addr[2], &mac_addr[3], &mac_addr[4], &mac_addr[5], &int_value[0],
             &int_value[1], &int_value[2], &int_value[3], &int_value[4], &int_value[5]);

     printf("sscanf to skip ret = %d dev inf = %d inf[5] = %d errno = %d \n", ret, int_value[0], int_value[5], errno);

     /*
      * Here trying to skip the mac & start read from comma, but sscanf is not working this module,
      * it will fail and won't retrieve any value.
      */
     ret = sscanf(mac_value_buf, ",%u,%u,%u,%u,%u,%u",
//             &mac_addr[0], &mac_addr[1], &mac_addr[2], &mac_addr[3], &mac_addr[4], &mac_addr[5], &int_value[0],
             &int_value[0],
             &int_value[1], &int_value[2], &int_value[3], &int_value[4], &int_value[5]);
     printf("sscanf to skip ret = %d dev inf = %d inf[5] = %d errno = %d \n", ret, int_value[0], int_value[5], errno);


     /* snprintf return number of bytes read not an number variable so could not add if check */
     ret = snprintf(str, sizeof(str), "%02X:%02X:%02X:%02X:%02X:%02X,%04d,%04d,%04d,%04d,%04d,%04d",
            mac_addr[0], mac_addr[1],
            mac_addr[2], mac_addr[3],
            mac_addr[4], mac_addr[5],
            int_value[0], int_value[1],
            int_value[2], int_value[3],
            int_value[4], int_value[5]);
    /*
      * we could not check 12 with snprintf because snprintf calculate number bytes is writing,
      * not a number variable is writing, here value change from 45 to 50 based on number of digit in dev_info
      */
     printf("snprintf ret = %d \n", ret);
     printf("\t\t************* Mac buff value = %s END ****************\n", mac_value_buf);

    } while (count < 2);


     return 0;
}

Output:

 sample$ ./a.out
                 ************* Mac buff value = 000C2956BAF5,1,2,3,4,5,6 Start ****************
sscanf ret = 12 dev inf = 1 inf[5] = 6
sscanf to skip ret = 12 dev inf = 1 inf[5] = 6 errno = 0
sscanf to skip ret = 0 dev inf = 1 inf[5] = 6 errno = 0
snprintf ret = 47
                ************* Mac buff value = 000C2956BAF5,1,2,3,4,5,6 END ****************


                 ************* Mac buff value = 000C2956:BAF5,1,2,3,4,5 Start ****************
Error in retrieve the data from buffer mac_value_buf = 000C2956:BAF5,1,2,3,4,5
sscanf to skip ret = 4 dev inf = 0 inf[5] = 0 errno = 0
sscanf to skip ret = 0 dev inf = 0 inf[5] = 0 errno = 0
snprintf ret = 47
                ************* Mac buff value = 000C2956:BAF5,1,2,3,4,5 END ****************