lib_ll.c

   1 #include <assert.h>
   2 #include <stdlib.h>
   3 #include <stddef.h>
   4 #include <stdbool.h>
   5 #include <stdio.h>
   6 #include <string.h>
   7
   8 #include "lib_ll.h"
   9
  10 List_Head *list_new(void)
  11 {
  12         List_Head *pHead = malloc(sizeof(List_Head));
  13         if (pHead == NULL) return NULL;
  14         pHead->count = 0;
  15         pHead->pNext = NULL;
  16         return pHead;
  17 }
  18
  19 void list_delete(List_Head *pHead)
  20 {
  21         List_Node *pTemp;
  22         assert(pHead != NULL);
  23         if(pHead->count == 0) { return; }
  24         pTemp = pHead->pNext;
  25         while(pTemp->pNext != NULL)
  26         {
  27                 pTemp = pTemp->pNext;
  28                 free(pTemp);
  29         }
  30         pHead->count = 0;
  31         pHead->pNext = NULL;
  32         free(pHead);
  33 }
  34
  35 int list_len(List_Head *pHead)
  36 {
  37         assert(pHead != NULL);
  38         if (pHead == NULL) return -1;
  39         return pHead->count;
  40 }
  41
  42 int list_search(List_Head *pHead, List_Node *pNode)
  43 {
  44         List_Node *pTemp = NULL;
  45         assert(pHead != NULL);
  46         if(pHead->count == 0) return 0;
  47         pTemp = pHead->pNext;
  48         while(pTemp != NULL) {
  49                 if(pTemp == pNode) return 1;
  50                 pTemp = pTemp->pNext;
  51         }
  52         return 0;
  53 }
  54
  55 List_Node *list_tail(List_Head *pHead)
  56 {
  57         List_Node *pTemp = pHead->pNext;
  58
  59         if(pHead->pNext == NULL) return NULL;
  60         while(pTemp->pNext != NULL)
  61                 pTemp = pTemp->pNext;
  62         return pTemp;
  63 }
  64
  65 List_Node *list_ins_head(List_Head *pHead)
  66 {
  67         List_Node *pTemp = pHead->pNext;
  68
  69         List_Node *pNode = malloc(sizeof(List_Node));
  70         if (pNode == NULL) return NULL;
  71         pNode->pData = NULL;
  72         pNode->pNext = NULL;
  73         if(pHead->pNext == NULL) /* adding to empty list */
  74         {
  75                 pHead->pNext = pNode;
  76         } else {
  77                 pNode->pNext = pTemp;
  78                 pHead->pNext = pNode;
  79         }
  80         pHead->count++;
  81         return pNode;
  82 }
  83
  84 List_Node *list_ins_head_data(List_Head *pHead, void *Data)
  85 {
  86         List_Node *temp = list_ins_head(pHead);
  87         temp->pData = Data;
  88         return temp;
  89 }
  90
  91 List_Node *list_ins_tail(List_Head *pHead)
  92 {
  93         List_Node *pTemp = pHead->pNext;
  94         List_Node *pNode = malloc(sizeof(List_Node));
  95         if (pNode == NULL) return NULL;
  96         pNode->pData = NULL;
  97         if(pHead->pNext == NULL) /* empty list */
  98         {
  99                 pHead->pNext = pNode;
 100         } else {
 101                 pTemp = list_tail(pHead);
 102                 pTemp->pNext = pNode;
 103                 pNode->pNext = NULL;
 104         }
 105         pHead->count++;
 106         return pNode;
 107 }
 108
 109 List_Node *list_ins_tail_data(List_Head *pHead, void *Data)
 110 {
 111         List_Node *temp = list_ins_tail(pHead);
 112         temp->pData = Data;
 113         return temp;
 114 }
 115
 116 List_Node *list_ins_before(List_Head *pHead, List_Node *pNode)
 117 {
 118         List_Node *pTemp = pHead->pNext;
 119         List_Node *pPrev = NULL;
 120         List_Node *pNew = malloc(sizeof(List_Node));
 121         if (pNew == NULL) return NULL;
 122         pNew->pData = NULL;
 123         if(pTemp == NULL) /* empty list */
 124         {
 125                 pHead->pNext = pNode;
 126         } else {
 127                 while(pTemp != pNode && pTemp != NULL)
 128                 {
 129                         pPrev = pTemp;
 130                         pTemp = pTemp->pNext;
 131                 }
 132                 if(pTemp == NULL) /* did not find matching node */
 133                 {
 134                         free(pNew);
 135                         return NULL;
 136                 }
 137                 if(pPrev == NULL) pHead->pNext = pNew;
 138                 else pPrev->pNext = pNew; /* put new node at end of previous */
 139                 pNew->pNext = pTemp; /* push current node down */
 140         }
 141         pHead->count++;
 142         return pNew;
 143 }
 144
 145 List_Node *list_ins_after(List_Head *pHead, List_Node *pNode)
 146 {
 147         List_Node *pTemp = pHead->pNext;
 148         List_Node *pNew = malloc(sizeof(List_Node));
 149         if (pNew == NULL) return NULL;
 150         pNew->pData = NULL;
 151         if(pTemp == NULL) /* empty list */
 152         {
 153                 pHead->pNext = pNode;
 154         } else {
 155                 while(pTemp != pNode && pTemp != NULL)
 156                 {
 157                         pTemp = pTemp->pNext;
 158                 }
 159                 if(pTemp == NULL) /* did not find matching node */
 160                 {
 161                         free(pNew);
 162                         return NULL;
 163                 }
 164                 pTemp->pNext = pNew;
 165                 pNew->pNext = NULL;
 166         }
 167         pHead->count++;
 168         return pNew;
 169 }
 170
 171 int list_rm_node(List_Head *pHead, List_Node *pNode)
 172 {
 173         List_Node *pPrev = NULL;
 174
 175         if(pHead == NULL || pNode == NULL)
 176                 return -1; /* Not valid data */
 177
 178         if(list_size(pHead) == 0)
 179                 return -1; /* list was empty */
 180
 181         pPrev = list_prev_node(pHead, pNode);
 182         if(pNode->pNext == NULL) /* removing from end of list */
 183         {
 184                 if(pPrev == NULL) /* no node before this one */
 185                 {
 186                         pHead->pNext = NULL;
 187                 } else { /* previous node exists */
 188                         /*pHead->pNext = pHead->pNext->pNext;*/
 189                         pPrev->pNext = NULL;
 190                 }
 191         } else { /* removing from middle */
 192                 if(pPrev == NULL)
 193                 {
 194                         pHead->pNext = pNode->pNext;
 195                 } else {
 196                         pPrev->pNext = pNode->pNext;
 197                 }
 198         }
 199         free(pNode);
 200         pHead->count--;
 201         return 1;
 202 }
 203
 204
 205 int list_rm_before(List_Head *pHead, List_Node *pNode)
 206 {
 207         List_Node *pPrev = list_prev_node(pHead, pNode);
 208         if(pPrev == NULL)
 209                 return -1;
 210         return list_rm_node(pHead, pPrev);
 211 }
 212
 213 int list_copy(List_Head *pDest, List_Head *pSrc)
 214 {
 215         int i = 1; /* start with head node */
 216         List_Node *pTemp = NULL;
 217         assert(pDest != NULL && pSrc != NULL);
 218         if(pSrc->count == 0) { return 0; } /* nothing to copy */
 219         list_clear(pDest);
 220         while (i <= pSrc->count) {
 221                 pTemp = list_get_num(pSrc, i);
 222                 list_ins_tail_data(pDest, pTemp->pData);
 223                 i++;
 224         }
 225         return 0;
 226 }
 227
 228 void list_print(List_Head *pHead)
 229 {
 230         int i = 0;
 231         List_Node *temp = NULL;
 232         assert(pHead != NULL);
 233         printf("\n");
 234         if(pHead->count == 0)
 235                 printf("Empty List\n");
 236         else {
 237                 temp = pHead->pNext;
 238                 do {
 239                         printf("List Item: %d -> Data: %p\n", i, (void *)temp);
 240                         temp = temp->pNext;
 241                         i++;
 242                 } while (temp != NULL);
 243         }
 244 }
 245
 246 List_Node *list_get_num(List_Head *pHead, int count)
 247 {
 248         int i = 1;
 249         List_Node *pNode;
 250         assert(count > 0);
 251         assert(pHead != NULL);
 252         if(pHead->count == 0) { return NULL; } /* list is empty */
 253         if(count > pHead->count) { return NULL; } /* node does not exist */
 254         pNode = pHead->pNext;
 255         while(i < count) {
 256                 pNode = pNode->pNext;
 257                 i++;
 258         }
 259         return pNode;
 260 }
 261
 262 int list_node_swap(List_Node *pPrev, List_Node *pCurr)
 263 {
 264         List_Node* pTemp = NULL;
 265         assert(pCurr != NULL && pPrev != NULL);
 266         pTemp = pCurr->pNext;
 267         pCurr->pNext = pPrev->pNext;
 268         pPrev->pNext = pTemp;
 269         return 0;
 270 }
 271
 272 List_Head *list_reverse(List_Head *pHead)
 273 {
 274         List_Head *newList = list_new();
 275         assert(pHead != NULL);
 276         while(pHead->count > 0)
 277         {
 278                 list_ins_head_data(newList, pHead->pNext->pData);
 279                 list_rm_node(pHead, pHead->pNext);
 280         }
 281         list_delete(pHead);
 282         return newList;
 283 }
 284
 285 void list_append(List_Head *pLo, List_Head *pHi)
 286 {
 287         List_Node *pTemp = NULL;
 288         assert(pLo != NULL && pHi != NULL);
 289         pTemp = list_tail(pLo);
 290         pTemp->pNext = pHi->pNext;
 291         pLo->count = pLo->count + pHi->count;
 292 }
 293
 294 int list_data_array(List_Head *pHead, void *pArr[], int len)
 295 {
 296         int i = 0;
 297         List_Node *pTemp = NULL;
 298         assert(pHead != NULL);
 299         assert(pArr != NULL);
 300         assert(len > 0);
 301         for(i = 0; i < len; i++) /* reset array */
 302                 pArr[i] = NULL;
 303         if(pHead->count == 0) return 1;
 304         pTemp = pHead->pNext;
 305         i = 0;
 306         while(pTemp != NULL) {
 307                 pArr[i++] = pTemp->pData;
 308                 pTemp = pTemp->pNext;
 309         }
 310         return 0;
 311 }
 312
 313 int list_node_array(List_Head *pHead, void *pArr[], int len)
 314 {
 315         int i = 0;
 316         List_Node *pTemp = NULL;
 317         assert(pHead != NULL);
 318         assert(pArr != NULL);
 319         assert(len > 0);
 320         for(i = 0; i < len; i++) /* reset array */
 321                 pArr[i] = NULL;
 322         if(pHead->count == 0) return 1;
 323         pTemp = pHead->pNext;
 324         i = 0;
 325         while(pTemp != NULL){
 326                 pArr[i++] = pTemp;
 327                 pTemp = pTemp->pNext;
 328         }
 329         return 0;
 330 }
 331
 332 void list_clear(List_Head *pHead)
 333 {
 334         List_Node *pTemp = pHead->pNext;
 335         assert(pHead != NULL);
 336         if(pTemp != NULL)
 337         {
 338                 while(pTemp->pNext != NULL)
 339                 {
 340                         pTemp = pTemp->pNext;
 341                         free(pTemp);
 342                 }
 343         }
 344         pHead->count = 0;
 345         pHead->pNext = NULL;
 346 }
 347
 348 List_Node *list_prev_node(List_Head *pHead, List_Node *pNode)
 349 {
 350         List_Node *pPrev = NULL, *pTemp;
 351         if(pHead == NULL || pNode == NULL)
 352                 return NULL;
 353         pTemp = pHead->pNext;
 354         do {
 355                 pPrev = pTemp;
 356                 pTemp = pTemp->pNext;
 357                 if(pTemp == NULL) return NULL; /* reached end of list */
 358         } while(pTemp != pNode);
 359         return pPrev;
 360 }