1 files changed, 153 insertions, 0 deletions
diff --git a/src/lib/kernel/slist.c b/src/lib/kernel/slist.c
new file mode 100644
index 0000000..2f27250
--- /dev/null
+++ b/src/lib/kernel/slist.c
@@ -0,0 +1,153 @@
+#include "slist.h"
+#include "threads/malloc.h"
+#include <stdio.h>
+//        #include <stdlib.h>
+
+/* List structure */
+struct Node
+{
+  ListElement Element;
+  Position    Next;
+};
+
+/* make empty list */
+
+SList
+MakeEmpty( SList L )
+{
+  if( L != NULL )
+    DeleteList( L );
+  L = malloc( sizeof( struct Node ) );
+  if( L == NULL ) {
+    printf( "Out of memory!\n" );
+    return NULL;
+  }
+  L->Next = NULL;
+  return L;
+}
+
+/* Return true if L is empty */
+
+int
+IsEmpty( SList L )
+{
+  return L->Next == NULL;
+}
+
+/* Return true if P is the last position in SList L */
+/* Parameter L is unused in this implementation */
+
+int IsLast( Position P, UNUSED SList L)
+{
+  return P->Next == NULL;
+}
+
+/* Return Position of X in L; NULL if not found */
+
+Position
+Find( ListElement X, SList L )
+{
+  Position P;
+
+  P = L->Next;
+  while( P != NULL && P->Element != X )
+    P = P->Next;
+
+  return P;
+}
+
+/* Delete from a SList */
+/* Cell pointed to by P->Next is wiped out */
+/* Assume that the position is legal */
+/* Assume use of a header node */
+
+void
+Delete( ListElement X, SList L )
+{
+  Position P, TmpCell;
+
+  P = FindPrevious( X, L );
+
+  if( !IsLast( P, L ) )  /* Assumption of header use */
+    {                      /* X is found; delete it */
+      TmpCell = P->Next;
+      P->Next = TmpCell->Next;  /* Bypass deleted cell */
+      free( TmpCell );
+    }
+}
+
+/* If X is not found, then Next field of returned value is NULL */
+/* Assumes a header */
+
+Position
+FindPrevious( ListElement X, SList L )
+{
+  Position P;
+
+  P = L;
+  while( P->Next != NULL && P->Next->Element != X )
+    P = P->Next;
+
+  return P;
+}
+
+/* Insert (after legal position P) */
+/* Header implementation assumed */
+/* Parameter L is unused in this implementation */
+
+void
+Insert( ListElement X, UNUSED SList L, Position P )
+{
+  Position TmpCell;
+
+  TmpCell = malloc( sizeof( struct Node ) );
+  if( TmpCell == NULL ) {
+    printf( "Out of space!!!\n" );
+    return;
+  }
+
+  TmpCell->Element = X;
+  TmpCell->Next = P->Next;
+  P->Next = TmpCell;
+}
+
+/*  DeleteSList algorithm */
+
+void
+DeleteList( SList L )
+{
+  Position P, Tmp;
+
+  P = L->Next;  /* Header assumed */
+  L->Next = NULL;
+  while( P != NULL )
+    {
+      Tmp = P->Next;
+      free( P );
+      P = Tmp;
+    }
+}
+
+Position
+Header( SList L )
+{
+  return L;
+}
+
+Position
+First( SList L )
+{
+  return L->Next;
+}
+
+Position
+Advance( Position P )
+{
+  return P->Next;
+}
+
+ListElement
+Retrieve( Position P )
+{
+  return P->Element;
+}