src/kernel/paging/ordered_array.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include <stdint.h>
#include "ordered_array.h"
#include "kheap.h"
#include "../lib/lib.h"
#include "../system.h"

char standard_lessthan_predicate(type_t a, type_t b) {
    return (a < b) ? 1 : 0;
}

ordered_array_t create_ordered_array(uint32_t max_size, lessthan_predicate_t less_than) {
    ordered_array_t to_ret;
    to_ret.array = (void *) kmalloc(max_size * sizeof(type_t));
    memory_set(to_ret.array, 0, max_size * sizeof(type_t));
    to_ret.size = 0;
    to_ret.max_size = max_size;
    to_ret.less_than = less_than;
    return to_ret;
}

ordered_array_t place_ordered_array(void *addr, uint32_t max_size, lessthan_predicate_t less_than) {
    ordered_array_t to_ret;
    to_ret.array = (type_t *) addr;
    memory_set(to_ret.array, 0, max_size * sizeof(type_t));
    to_ret.size = 0;
    to_ret.max_size = max_size;
    to_ret.less_than = less_than;
    return to_ret;
}

void destroy_ordered_array(ordered_array_t *array) {
    kfree(array->array);
}

void insert_ordered_array(type_t item, ordered_array_t *array) {
    assert(array->less_than);
    uint32_t iterator = 0;
    while (iterator < array->size && array->less_than(array->array[iterator], item))
        iterator++;
    if (iterator == array->size)
        array->array[array->size++] = item;
    else {
        type_t tmp = array->array[iterator];
        array->array[iterator] = item;
        while (iterator < array->size) {
            iterator++;
            type_t tmp2 = array->array[iterator];
            array->array[iterator] = tmp;
            tmp = tmp2;
        }
        array->size++;
    }
}

type_t lookup_ordered_array(uint32_t i, ordered_array_t *array) {
    assert(i < array->size);
    return array->array[i];
}

void remove_ordered_array(uint32_t i, ordered_array_t *array) {
    while (i < array->size) {
        array->array[i] = array->array[i + 1];
        i++;
    }
    array->size--;
}