Thread: How to decouple a pointer conditional check on link lists?

  1. #1
    Registered User
    Join Date
    Feb 2022
    Posts
    6

    How to decouple a pointer conditional check on link lists?

    Hello All,

    See the code below. What i'm trying to do is disassociate the condition, so i can re-use the function for different parameters.

    Code:
    // 1. How can I decouple the fast forward condition?
    // 2. How can i change the operator?
    // 3. What do I do when type of stop condition for structure comparison is no longer int?
    // -------------- Attempt 1
    // function
    void elem_forward_until(seg_list_elem_t ptr, &ptr->s.t_end##, int stop_condition) {
        while (ptr && (ptr->s.t_end## < stop_condition)) {
            ptr = ptr->next;
        }
    }
    // instance of call
    elem_forward_until(ptr, &ptr->s.t_end##, stop_condition);
    // -------------- Attempt 2
    // function
    void elem_forward_until2(seg_list_elem_t ptr, int offset, int stop_condition) {
        while (ptr && ((ptr + offset) < stop_condition)) {
            ptr = ptr->next;
        }
    }
    // instance of call
    elem_forward_until2(ptr, offsetof(struct seg_list_elem_t), stop_condition);
    Regards,
    Wes

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    1,466
    Looks like a little non-C (or C++) syntax there.
    Maybe you mean something along these lines.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
      
    typedef struct Segment
    {
        int n;
        struct Segment *next;
    } Segment;
     
    Segment *new_segment(int n, Segment *next)
    {
        Segment *seg = malloc(sizeof *seg);
        if (!seg) { perror("new_segment"); exit(EXIT_FAILURE); }
        seg->next = next;
        seg->n = n;
        return seg;
    }
     
    Segment *prepend(Segment *root, int n)
    {
        return new_segment(n, root);
    }
     
    Segment *append(Segment *root, int n)
    {
        Segment *seg = new_segment(n, NULL);
        if (!root) return seg;
        Segment *s = root;
        while (s->next) s = s->next;
        s->next = seg;
        return root;
    }
     
    void print(const Segment *segs)
    {
        for ( ; segs; segs = segs->next) printf("%d ", segs->n);
        printf("\n");
    }
     
    int cmp_less   (const Segment *a, const void *b) { return a->n < *(int*)b; }
    int cmp_greater(const Segment *a, const void *b) { return a->n > *(int*)b; }
     
    Segment *elem_forward_until(
        Segment*    segs,
        int(*       cmp)(const Segment*, const void*),
        const void* stop)
    {
        while (segs && cmp(segs, stop)) segs = segs->next;
        return segs;
    }
     
    int main()
    {
        const int init[] = {4, 5, 3, 6, 2, 7, 1, 9, -1}; // -1 marks end of init list
     
        Segment *segs = NULL;
        for (const int *n = init; *n != -1; ++n) segs = append(segs, *n);
        print(segs);
     
        Segment *s = elem_forward_until(segs, cmp_less, &(int){7});
        if (s) printf("%d\n", s->n); else printf("nil\n");
     
        s = elem_forward_until(segs, cmp_greater, &(int){1});
        if (s) printf("%d\n", s->n); else printf("nil\n");
     
        return 0;
    }
    The whole problem with the world is that fools and fanatics are always so certain of themselves, but wiser people so full of doubts. - Bertrand Russell

  3. #3
    Registered User
    Join Date
    Feb 2019
    Posts
    1,040
    Just a note: I prefer to deal with lists as described by Sedgewick because we can create polymorphic nodes, in C. Here's an example using a circular single linked list:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    // A list always have a 'head' sentinel node. All data nodes are polymorphic since
    // we only need to declare a structure with the same 'next' pointer at the beginning.
    
    // Used to initialize a list
    #define SLIST_HEAD_PTR struct slist_head *next
    
    struct slist_head { struct slist_head *next; };
    
    #define SLIST_INIT_HEAD(head_) { &(head_) }
    
    static inline void slist_add_next( struct slist_head *node, struct slist_head *new )
    {
      new->next = node->next;
      node->next = new;
    }
    
    static inline struct slist_head *slist_del_next( struct slist_head *node )
    {
      struct slist_head *next = node->next;
      node->next = next->next;
      return next;
    }
    
    static inline int slist_isempty( struct slist_head *head )
    {
      return head->next == head;
    }
    
    #define slist_foreach( iter_, head_ ) \
      for ( iter_ = (head_)->next; iter_ != head_; iter_ = (iter_)->next )
    
    // ------- test ------------
    
    int main( void )
    {
      // My node (polymorphism)
      struct mynode {
        SLIST_HEAD_PTR;    // it is important this is the first declaration!
        int x;
      };  
    
      struct slist_head list = SLIST_INIT_HEAD( list );  // our head of the list.
      struct slist_head *p;
      struct mynode *q;
    
      // Notice: Allocation isn't present at the list routines!
      q = malloc( sizeof *q );
      q->x = 1;
      slist_add_next( &list, (struct slist_head *)q );  // q is tail.
      p = (struct slist_head *)q;                       // save the tail node.
    
      q = malloc( sizeof *q );
      q->x = 2;
      slist_add_next( p, (struct slist_head *)q );      // q is tail.
      p = (struct slist_head *)q;                       // save the tail node.
    
      q = malloc( sizeof *q );
      q->x = 3;
      slist_add_next( p, (struct slist_head *)q );      // q is tail.
    
      // List all nodes.
      slist_foreach( p, &list )
        printf( "%d\n", ((struct mynode *)p)->x );
    
      // delete all nodes.
      // Notice: Deallocation isn't present at list routines either.
      while ( ! slist_isempty( &list ) )
        free( slist_del_next( &list ) );
    }

  4. #4
    Registered User
    Join Date
    Sep 2020
    Posts
    394
    Who is the this "Sedgewich"? I really think they should move off to other languages..

    Is it really so hard to recognize or type this pattern?

    Code:
       struct whatever *p = first_p;
       while(p != NULL) {
          // dp spmething
          p = p->next;
       }
    Wait till they need a structure to be a member of two different lists at the same time...

    Code:
    struct statistic_year {
       struct x *next_for_year;
       struct x *next_for_statistic;
       double value;
    };.
    Have a look at this mid-80s magazine, https://vintageapple.org/byte/pdf/19...ss_Storage.pdf on page 137 (by the page number) if you want to see where this ends...

    Code:
    In C:
    if ((c > = 'a' && c < = 'z') II (c > = 'A' && c < = 'Z'))
       return(LETTER);
    
    In Easy C:
    
    if ((c GE 'a' AND c LE 'z) OR (c GE 'A' AND c LE 'Z'))
       return(LETTER);
    And these gems:

    Code:
    #define CASE(e) { switch (e) { /* head of case /*
    #define CASEOF(e) casee : { /* case block • / 
    #define DEFCASE default : { /* default case block • / 
    #define ENDCOF } break ; /* end of case block • / 
    #define ENDCASE } } 1 end of case 1

    IMO excessively leaning on the pre-processor and inline functions rather than changing languages is a bad idea.

  5. #5
    Registered User
    Join Date
    Feb 2022
    Posts
    6
    Can someone break this down barney style for me - "*(int*)b"

    Hamster_nz? Are you the same guy whos posted lots of FPGA related topics?

  6. #6
    Registered User
    Join Date
    Sep 2020
    Posts
    394
    First question....

    cast 'b' to be a pointer to int, then dereference it to return the integer at memory address b.

    Code:
    int a = *((int *)b);
    Second qn, yes, that was me a decade ago. Stopped now because I got sick of being begged or shouted at in emails for not helping students with their assignments.

  7. #7
    Registered User
    Join Date
    Feb 2022
    Posts
    6
    Regarding a = *((int*)b); Is this so b can be a different data type. For example char?

    Is it not constrained by data type underlined.
    returna->n < *(int*)b;

    Nz, shame to hear. You're a bit of a legend

  8. #8
    Registered User
    Join Date
    Sep 2020
    Posts
    394
    Yes
    ,
    Code:
      char *buffer = malloc(2000); // Allocate a buffer, enough for 2000 chars, or 500 32-bit ints
      // ... do something here to fill the buffer
      int32_t a = *((int32_t *)buffer);   // a will be the  value of the first four bytes of the buffer, treated as an 32-bit signed integer.
    Doing things like this is somewhat bad form, as dynamically changing pointer types can break some of the finer points of C, esp compiler optimizations which assume that different data types don't overlap each other in memory (that is a very bad explanation of strict aliasing)

    A union is far better way, that is legal C.

  9. #9
    Registered User
    Join Date
    Feb 2022
    Posts
    6
    Thanks all,

    How do I mark this as solved?

    Regards,
    Wes

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,426
    There's no actual mark as solved.
    Saying thanks is usually enough and people stop replying.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Conditional to check for backslash , \
    By seal308 in forum C Programming
    Replies: 17
    Last Post: 01-30-2016, 11:24 AM
  2. functions using link lists
    By chood72 in forum C++ Programming
    Replies: 3
    Last Post: 10-31-2005, 03:51 PM
  3. Link Lists
    By Loki in forum C Programming
    Replies: 2
    Last Post: 06-07-2003, 09:21 PM
  4. Link lists
    By thedumbmutt in forum C++ Programming
    Replies: 2
    Last Post: 12-11-2002, 02:33 PM
  5. double link lists
    By rumi_red in forum C++ Programming
    Replies: 3
    Last Post: 10-30-2001, 10:13 AM

Tags for this Thread