Skip to content

Instantly share code, notes, and snippets.

@Gavinok
Created March 27, 2023 19:43
Show Gist options
  • Save Gavinok/41b2e5771a6f7d397e5c85fec72199fa to your computer and use it in GitHub Desktop.
Save Gavinok/41b2e5771a6f7d397e5c85fec72199fa to your computer and use it in GitHub Desktop.
Basic linked list library
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
/* typedef void *TaskHandle_t; */
/* enum task_type { VAL1, VAL2 }; */
/* typedef struct DD_Task { */
/* TaskHandle_t t_handle; */
/* enum task_type type; */
/* uint32_t task_id; */
/* uint32_t release_time; */
/* uint32_t absolute_deadline; */
/* uint32_t completion_time; */
/* } DD_Task; */
/* typedef struct DD_Task_List { */
/* DD_Task task; */
/* struct DD_Task_List *next_task; */
/* } DD_Task_List; */
/* typedef enum Found { FOUND, NOT_FOUND } Found; */
/* typedef struct MaybeFound { */
/* Found found; */
/* DD_Task_List **list; */
/* } MaybeFound; */
DD_Task_List *newNode(TaskHandle_t t_handle, enum task_type type,
uint32_t task_id, uint32_t release_time,
uint32_t absolute_deadline, uint32_t completion_time) {
DD_Task t =
(DD_Task){t_handle, type, task_id, release_time,
absolute_deadline, completion_time};
DD_Task_List *val = (DD_Task_List *)malloc(sizeof(DD_Task_List));
val->task = t;
val->next_task = NULL;
return val;
}
bool idEq(const int id, const DD_Task task) { return task.task_id == id; }
/* MaybeFound find(uint32_t id, DD_Task_List **list) { */
/* for (DD_Task_List **l = list; (*l) != NULL; l = &(*l)->next_task) { */
/* if (idEq(id, (*l)->task)) { */
/* return (MaybeFound){FOUND, l}; */
/* } */
/* } */
/* return (MaybeFound){NOT_FOUND, NULL}; */
/* } */
MaybeFound findIf(bool(fun_ptr)(const int, const DD_Task), int fun_arg,
DD_Task_List **list) {
for (DD_Task_List **l = list; (*l) != NULL; l = &(*l)->next_task) {
if (fun_ptr(fun_arg, (*l)->task)) {
return (MaybeFound){FOUND, l};
}
}
return (MaybeFound){NOT_FOUND, NULL};
}
Found delete(DD_Task_List **l) {
if (l == NULL)
return NOT_FOUND;
DD_Task_List *tmp_task;
if ((*l)->next_task) {
tmp_task = *l;
*l = (*l)->next_task;
} else {
// If there is nothing left then set this list to NULL
tmp_task = *l;
*l = NULL;
}
free(tmp_task);
(tmp_task) = NULL;
return FOUND;
}
DD_Task_List *insert(DD_Task_List *new, DD_Task_List **l) {
if ((*l)->next_task)
new->next_task = (*l)->next_task;
(*l)->next_task = new;
return *l;
}
bool deadlineBefore(const int deadline, DD_Task task) {
return deadline < task.absolute_deadline;
}
DD_Task_List *insertByDeadline(DD_Task_List *new, DD_Task_List **list) {
// add task at front of list if the new deadline is earlier
MaybeFound f = findIf(deadlineBefore, new->task.absolute_deadline, list);
if (f.found == FOUND) {
DD_Task_List **tmp = f.list;
insert(new, f.list);
return *list;
}
DD_Task_List *l;
// Iterate to the end of the list and insert there
for (l = *list; l->next_task != NULL; l = l->next_task) {
}
l->next_task = new;
return *list;
}
void printLL(DD_Task_List *list) {
if (list == NULL)
printf("NULL");
for (DD_Task_List *l = list; l != NULL; l = l->next_task) {
printf("{ id %d , deadline %d}", l->task.task_id,
l->task.absolute_deadline);
}
printf("\n");
}
int main(int argc, char *argv[]) {
DD_Task_List *list = NULL;
findIf(idEq, 10, &list);
DD_Task_List *n = newNode(NULL, 0, 2, 0, 0, 0);
insert(newNode(NULL, // TaskHandle_t t_handle
0, // task_type type;
7, 0, // uint32_t release_time
1, // uint44_t absolute_deadline;
0),
&n);
// this is the head of our list which is why it as a -1
list = newNode(NULL, // TaskHandle_t t_handle
0, // task_type type;
10, 0, // uint32_t release_time
0, // uint33_t absolute_deadline;
0); // uint32_t completion_time
printLL(list);
insert(newNode(NULL, // TaskHandle_t t_handle
0, // task_type type;
-1, 0, // uint32_t release_time
0, // uint33_t absolute_deadline;
0),
&list); // uint32_t completion_time
printLL(list);
insert(newNode(NULL, // TaskHandle_t t_handle
0, // task_type type;
7, 0, // uint32_t release_time
1, // uint44_t absolute_deadline;
0),
&list);
printLL(list);
insertByDeadline(newNode(NULL, // TaskHandle_t t_handle
0, // task_type type;
12, 0, // uint32_t release_time
10, // uint34_t absolute_deadline;
0),
&list);
printLL(list);
insertByDeadline(newNode(NULL, // TaskHandle_t t_handle
0, // task_type type;
2, 0, // uint32_t release_time
1, // uint32_t absolute_deadline;
0),
&list);
int search = 7;
MaybeFound was_found = findIf(idEq, search, &list);
printLL(list);
switch (was_found.found) {
case FOUND:
if (delete (was_found.list) == FOUND) {
assert(findIf(idEq, 19, &list).found == NOT_FOUND);
printLL(list);
assert(delete (findIf(idEq, 12, &list).list) == FOUND);
printLL(list);
assert(findIf(idEq, 12, &list).found == NOT_FOUND);
printLL(list);
assert(delete (findIf(idEq, 2, &list).list) == FOUND);
printLL(list);
assert(findIf(idEq, 2, &list).found == NOT_FOUND);
printLL(list);
assert(delete (findIf(idEq, -1, &list).list) == FOUND);
printLL(list);
return printf("I found task with id %d", search);
}
printLL(list);
return printf("I found task with id %d but not deleted",
(*was_found.list)->task.task_id);
case NOT_FOUND:
return printf("I FAILED to find a task with id %d", search);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment