From cc437b9263b51f96484762e91a15c1584ede1e83 Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Fri, 4 May 2012 21:20:46 +0200 Subject: Object version of earray --- src/kernel/Makefile | 2 +- src/kernel/lib/earray.cpp | 158 ++++++++++++++++++++++++++++++++++++++++++++++ src/kernel/lib/earray.h | 35 ++++++++++ 3 files changed, 194 insertions(+), 1 deletion(-) create mode 100644 src/kernel/lib/earray.cpp create mode 100644 src/kernel/lib/earray.h diff --git a/src/kernel/Makefile b/src/kernel/Makefile index a1acc49..1103a7d 100644 --- a/src/kernel/Makefile +++ b/src/kernel/Makefile @@ -2,7 +2,7 @@ Out = kernel.elf Obj = core/loader_.o core/kmain.o core/sys.o \ core/monitor.o task/timer.o \ task/idt.o task/idt_.o task/task.o task/task_.o task/syscall.o task/sched.o \ - lib/bitset.o lib/std.o lib/cpp.o \ + lib/bitset.o lib/std.o lib/cpp.o lib/earray.o \ mem/mem.o mem/paging.o mem/gdt.o mem/_dlmalloc.o mem/seg.o \ linker/elf.o diff --git a/src/kernel/lib/earray.cpp b/src/kernel/lib/earray.cpp new file mode 100644 index 0000000..5760822 --- /dev/null +++ b/src/kernel/lib/earray.cpp @@ -0,0 +1,158 @@ +#include "earray.h" + +#include +#include +#include + +template +earray::earray(int rvil, int vl) { + ref_vect_init_len = rvil; + vect_len = vl; + + ref_vect_len = ref_vect_init_len; + elements = 0; + mutex = MUTEX_UNLOCKED; + + data = (T***)kmalloc(ref_vect_len * sizeof(T**)); + + for (int i = 0; i < ref_vect_len; i++) { + data[i] = 0; + } +} + +template +earray::~earray() { + mutex_lock(&mutex); + + for (int i = 0; i < ref_vect_len; i++) { + if (data[i] != 0) kfree(data[i]); + } + kfree(data); + + //no need to unlock, the structure is never to be used again +} + +template +int earray::add(T* ptr) { + if (ptr == 0) return -1; + + mutex_lock(&mutex); + + for (int i = 0; i < ref_vect_len; i++) { + if (data[i] == 0) { + // Allocate here + data[i] = (T**)kmalloc(vect_len * sizeof(T*));; + data[i][0] = ptr; + for (int j = 1; j < vect_len; j++) data[i][j] = 0; + + int ret = i * vect_len; + + if (elements <= ret) elements = ret + 1; + + mutex_unlock(&mutex); + return ret; + } else { + // Look for free space + for (int j = 0; j < vect_len; j++) { + if (data[i][j] == 0) { + data[i][j] = ptr; + + int ret = i * vect_len + j; + if (elements <= ret) elements = ret + 1; + + mutex_unlock(&mutex); + return ret; + } + } + } + } + // Nothing was allocated, we need MORE SPACE + T ***new_data = (T***)kmalloc((ref_vect_len + ref_vect_init_len) * sizeof(T**)); + for (int i = 0; i < ref_vect_len; i++) { + new_data[i] = data[i]; + } + new_data[ref_vect_len] = (T**)kmalloc(vect_len * sizeof(T*)); + new_data[ref_vect_len][0] = ptr; + int ret = ref_vect_len * vect_len; + for (int i = 1; i < vect_len; i++) { + new_data[ref_vect_len][i] = 0; + } + for (int i = ref_vect_len + 1; i < ref_vect_len + ref_vect_init_len; i++) { + new_data[i] = 0; + } + kfree(data); + data = new_data; + ref_vect_len += ref_vect_init_len; + + ASSERT(ret >= elements); + elements = ret + 1; + + mutex_unlock(&mutex); + return ret; + +} + +template +T *earray::at(int num) { + mutex_lock(&mutex); + + int i = num / vect_len, j = num % vect_len; + if (i >= ref_vect_len || data[i] == 0) { + mutex_unlock(&mutex); + return 0; + } + void* ret = data[i][j]; + mutex_unlock(&mutex); + return ret; +} + +template +void earray::set(int num, T* ptr) { + mutex_lock(&mutex); + + int a = num / vect_len, b = num % vect_len, i, j; + if (a >= ref_vect_len) { + if (ptr == 0) { + mutex_unlock(&mutex); + return; + } + int new_vect_len = ref_vect_len; + while (a >= ref_vect_len) new_vect_len += ref_vect_init_len; + + T ***new_data = (T***)kmalloc(new_vect_len * sizeof(T**)); + for (i = 0; i < ref_vect_len; i++) { + new_data[i] = data[i]; + } + for (i = ref_vect_len; i < new_vect_len; i++) { + new_data[i] = 0; + } + kfree(data); + data = new_data; + ref_vect_len = new_vect_len; + } + if (ptr == 0) { + if (data[a] != 0) { + if (data[a][b] != 0) { + data[a][b] = 0; + j = 1; + for (i = 0; i < vect_len; i++) { + if (data[a][i] != 0) j = 0; + } + if (j == 1) { + kfree(data[a]); + data[a] = 0; + } + } + } + } else { + if (data[a] = 0) { + data[a] = (T**)kmalloc(vect_len * sizeof(T*)); + for (i = 0; i < vect_len; i++) data[a][i] = 0; + } + data[a][b] = ptr; + + if (num >= elements) elements = num + 1; + } + + mutex_unlock(&mutex); +} diff --git a/src/kernel/lib/earray.h b/src/kernel/lib/earray.h new file mode 100644 index 0000000..b6d0a55 --- /dev/null +++ b/src/kernel/lib/earray.h @@ -0,0 +1,35 @@ +#ifndef DEF_EARRAY_H +#define DEF_EARRAY_H + +#include + +/* + * This class implements a simple extensible array structure. + * An entry with a 0 value is considered free and can be allocated. + * The array will free as much space when elements are removed. + */ + +template +struct earray { + private: + int ref_vect_init_len; + int vect_len; // NEVER CHANGE THIS AFTER INITIALISATION!!!! + + int ref_vect_len; + int elements; + T ***data; + + mutex_t mutex; + + public: + earray(int refvectinitlen, int vectlen); + ~earray(); + + int add(T* ptr); // return element number or -1 if fail + T* at(int num); // returns 0 when nothing + void set(int num, T* ptr); +}; + + + +#endif -- cgit v1.2.3