How to avoid self referential linked list in C

cpgreen2 Source

I'm writing this program for my OS class and I'm stuck on what seems like a simple issue. I have a Lock struct and a lockList struct that holds a pointer to a Lock as its head. When I need to add a lock to the list, I need to add it to the end of the linked list and be able to print them. Problem is when I add two of them (adding one works fine), and then print it with the "list" command that I wrote, it prints the second thing I added infinitely. I've determine that's because the second Lock's "next" field points to itself and I can't figure out why or how to fix it.

Here is my code for adding the lock:

if (lockList.head == NULL) {
    Lock lock = {.next = NULL}; 
    strcpy(lock.name, name);
    lockList.head = &lock;
  } else {
    while (contains(name)) {
      pthread_cond_wait(&cond, &mutex);
    }

    Lock *current = lockList.head;
    while (current->next != NULL) {
      current = current->next;
    }

    Lock lock = {.next = NULL}; 
    strcpy(lock.name, name);

    current->next = &lock;
  }

My Lock and lockList structs:

typedef struct Lock {
  char name[25];
  struct Lock *next;
} Lock;

struct LockList {
  Lock *head;
}lockList;

and my code to list the items in the list:

else if (strcmp(cmd, "list") == 0) {
  Lock *current = lockList.head;

  while (current != NULL) {
    fprintf(fp, "%s\n", current->name);
    current = current->next;
  } 

}

full code:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <netdb.h>
#include <signal.h>
#include <errno.h>

/** Port number used by my server */
#define PORT_NUMBER "26136"

pthread_mutex_t mutex;
pthread_cond_t cond;

// Print out an error message and exit.
static void fail( char const *message ) {
  fprintf( stderr, "%s\n", message );
  exit( 1 );
}



typedef struct Lock {
  char name[25];
  struct Lock *next;
} Lock;

struct LockList {
  Lock *head;
}lockList;

bool contains(char title[]) {
  Lock *current = lockList.head;
  while (current != NULL) {
    if (current->name == title) {
      return true;
    }
    current = current->next;
  }

  return false;
}

/** handle a client connection, close it when we're done. */
void handleClient( int sock ) {
  // Here's a nice trick, wrap a C standard IO FILE around the
  // socket, so we can communicate the same way we would read/write
  // a file.
  FILE *fp = fdopen( sock, "a+" );

  // Prompt the user for a command.
  fprintf( fp, "cmd> " );

  char cmd[ 11 ];
  int match;
  while ( ( match = fscanf( fp, "%s", cmd ) ) == 1 &&
          strcmp( cmd, "quit" ) != 0 ) {

    // if command was lock
    if (strcmp(cmd, "lock") == 0) {
      // lock mutex
      pthread_mutex_lock(&mutex);

      char name[25];
      fscanf(fp, "%s", name);

      // while the thing requested is on the locked list, wait      


      // add the new lock to the locked list
      if (lockList.head == NULL) {
        Lock lock = {.next = NULL}; 
        strcpy(lock.name, name);
        lockList.head = &lock;
      } else {
        while (contains(name)) {
          pthread_cond_wait(&cond, &mutex);
        }

        Lock *current = lockList.head;
        while (current->next != NULL) {
          current = current->next;
        }

        Lock lock = {.next = NULL}; 
        strcpy(lock.name, name);

        current->next = &lock;
      }

      // unlock mutex
      pthread_mutex_unlock(&mutex);
    } else if (strcmp(cmd, "unlock") == 0) {

      // lock mutex
      pthread_mutex_lock(&mutex);

      char name[25];
      fscanf(fp, "%s", name);
      // if item with that name is in the list, take it off
      Lock *current = lockList.head;

      if (strcmp(lockList.head->name, name) == 0) {
        lockList.head = lockList.head->next;
      } else {
        while (current->next != NULL) {
          if (strcmp(current->next->name, name) == 0) {
            // if item found is in the middle of the list
            current->next = current->next->next;
            break;        
          }
          current = current->next;
        }
      }

      // broadcast the condition variable
      pthread_cond_broadcast(&cond);

      // unlock mutex
      pthread_mutex_unlock(&mutex);
    } else if (strcmp(cmd, "list") == 0) {
      Lock *current = lockList.head;

      while (current != NULL) {
        fprintf(fp, "%s\n", current->name);
        current = current->next;
      } 

    } else {
      fprintf(fp, "invalid command");
    }



    // Prompt the user for the next command.
    fprintf( fp, "cmd> " );
    fflush( fp );
  }

  // Close the connection with this client.
  fclose( fp );
}

int main() {
  lockList.head = NULL;


  pthread_mutex_init(&mutex, NULL);
  pthread_cond_init(&cond, NULL);
  // Prepare a description of server address criteria.
  struct addrinfo addrCriteria;
  memset(&addrCriteria, 0, sizeof(addrCriteria));
  addrCriteria.ai_family = AF_INET;
  addrCriteria.ai_flags = AI_PASSIVE;
  addrCriteria.ai_socktype = SOCK_STREAM;
  addrCriteria.ai_protocol = IPPROTO_TCP;

  // Lookup a list of matching addresses
  struct addrinfo *servAddr;
  if ( getaddrinfo( NULL, PORT_NUMBER, &addrCriteria, &servAddr) )
    fail( "Can't get address info" );

  // Try to just use the first one.
  if ( servAddr == NULL )
    fail( "Can't get address" );

  // Create a TCP socket
  int servSock = socket( servAddr->ai_family, servAddr->ai_socktype,
                         servAddr->ai_protocol);
  if ( servSock < 0 )
    fail( "Can't create socket" );

  // Bind to the local address
  if ( bind(servSock, servAddr->ai_addr, servAddr->ai_addrlen) != 0 )
    fail( "Can't bind socket" );

  // Tell the socket to listen for incoming connections.
  if ( listen( servSock, 5 ) != 0 )
    fail( "Can't listen on socket" );

  // Free address list allocated by getaddrinfo()
  freeaddrinfo(servAddr);

  // Fields for accepting a client connection.
  struct sockaddr_storage clntAddr; // Client address
  socklen_t clntAddrLen = sizeof(clntAddr);

  while ( true  ) {
    // Accept a client connection.
    int sock = accept( servSock, (struct sockaddr *) &clntAddr, &clntAddrLen);

    // Talk to this client
    handleClient( sock );
  }

  // Stop accepting client connections (never reached).
  close( servSock );

  return 0;
}

Here's what a real MCVE looks like:

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

typedef struct Lock {
    char name[25];
    struct Lock *next;
} Lock;

struct LockList {
    Lock *head;
}
lockList;

int main(void)
{
    lockList.head = NULL;
    char *str[] = { "world", "hello" };
    for (int i = 0; i < 2; i++)
    {
        Lock lock = {.next = lockList.head};
        strcpy(lock.name, str[i]);
        lockList.head = &lock;
    }
    printf("%s\n", lockList.head->name);
    printf("%s\n", lockList.head->next->name);
}

The expected output from this program is

hello
world

The actual output is

hello
hello

I'll let someone else explain why that happens.

cstructlinked-listsingly-linked-list

Answers

comments powered by Disqus