Subversion Repositories Kolibri OS

Compare Revisions

Regard whitespace Rev 1285 → Rev 1286

/programs/develop/libraries/framework/trunk/stdlib/heap.c
0,0 → 1,176
/*******************************************************************************
* Copyright (C) 2009 Vasiliy Kosenko *
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 3 of the License, or *
* (at your option) any later version. *
* *
* This program is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
* GNU General Public License for more details. *
* *
* You should have received a copy of the GNU General Public License *
* along with this program; if not, write to the Free Software *
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *
*******************************************************************************/
 
/*******************************************************************************
* This is my heap realization adapted for KolibriOS *
*******************************************************************************/
 
#include "kolibri.h"
#include "heap.h"
#include "defs.h"
 
void *halMemAlloc(Heap *wheap, unsigned long nbytes){
MemBlock *heap = wheap->free, *best = 0;
int good_best = 0; // Such memory block, that no memory will left
unsigned long nblocks = (nbytes-1)/sizeof(MemBlock)+1;
if (heap) {
while (heap) {
if (heap->nblocks > nblocks && (!best || heap->nblocks < best->nblocks) && (!good_best || heap->nblocks > nblocks+1)) {
best = heap;
if (heap->nblocks > nblocks+1) {
good_best = 1;
}
} else if (heap->nblocks == nblocks) {
best = heap;
good_best = 0;
break;
}
heap = heap->next;
}
}
if (best && good_best) {
heap = best+best->nblocks-nblocks;
heap->nblocks = nblocks;
wheap->allocated = halMemBlockAdd(wheap->allocated, heap, false);
best->nblocks -= nblocks+1;
best = heap;
} else if (best) {
wheap->free = halMemBlockRemove(best);
wheap->allocated = halMemBlockAdd(wheap->allocated, best, false);
} else {
// We need some memory for heap
int npages = ((nblocks+1)-1)/(PAGE_SIZE/sizeof(MemBlock))+1;
void *pages;
// debug(DEBUG_MESSAGE, 4, "no enough memory in heap, needed %d page%s", npages, npages == 1 ? "" : "s");
// Try to get npages at once
pages = wheap->alloc(wheap, npages*PAGE_SIZE);
if (pages) {
// debug(DEBUG_MESSAGE, 5, "physic pages allocated");
best = (MemBlock *) pages;
if (npages*PAGE_SIZE <= (nblocks+2)*sizeof(MemBlock)) {
best->nblocks = npages*PAGE_SIZE/sizeof(MemBlock)-1;
} else {
best->nblocks = nblocks;
heap = best+best->nblocks+1;
heap->nblocks = npages*PAGE_SIZE/sizeof(MemBlock)-(nblocks+1)-1;
wheap->free = halMemBlockAdd(wheap->free, heap, true);
}
wheap->allocated = halMemBlockAdd(wheap->allocated, best, false);
} else {
// debug(DEBUG_WARNING, 3, "no available physic pages");
return NULL;
}
}
// debug(DEBUG_MESSAGE, 5, "memory allocated");
return (void *) (best + 1);
}
 
void halMemFree(Heap *wheap, void *addr){
MemBlock *heap = wheap->allocated;
MemBlock *block = (MemBlock *)addr - 1;
while (heap->next && block < heap) {
heap = heap->next;
}
if (block != heap) {
return;
}
wheap->allocated = halMemBlockRemove(block);
wheap->free = halMemBlockAdd(wheap->free, block, true);
}
 
void halMemHeapInit(Heap *wheap, void *(*alloc)(Heap *heap, int nbytes), void *st_addr, int size){
MemBlock *st_unit = (MemBlock *)st_addr;
if (st_unit) {
st_unit->nblocks = size/sizeof(MemBlock)-1;
wheap->free = halMemBlockAdd(NULL, st_unit, true);
} else {
wheap->free = NULL;
}
wheap->allocated = NULL;
wheap->alloc = alloc;
}
 
/////////////////////////////////////////////////////////////////////////////////
// inside functions //
/////////////////////////////////////////////////////////////////////////////////
MemBlock *halMemBlockAdd(MemBlock *heap, MemBlock *unit, bool optimize){
MemBlock *heap_st = heap;
// int optimize = (heap_st != wheap->allocated);
if (!heap || (heap > unit)) {
heap_st = unit;
if (heap) {
heap->previos = unit;
}
unit->next = heap;
unit->previos = NULL;
} else {
if (heap->next) {
while (heap->next && (heap < unit)) {
heap = heap->next;
}
heap = heap->previos;
}
unit->next = heap->next;
unit->previos = heap;
if (heap->next) {
heap->next->previos = unit;
}
heap->next = unit;
}
if (optimize) {
if (unit->previos && unit->previos+unit->previos->nblocks == unit) {
halMemBlockRemove(unit);
unit->previos->nblocks += unit->nblocks+1;
}
if (unit->next && unit+unit->nblocks == unit->next) {
unit->nblocks += unit->next->nblocks+1;
halMemBlockRemove(unit->next);
}
}
return heap_st;
}
 
MemBlock *halMemBlockRemove(MemBlock *unit) {
if (unit->next) {
unit->next->previos = unit->previos;
}
if (unit->previos) {
unit->previos->next = unit->next;
while (unit->previos) {
unit = unit->previos;
}
return unit;
} else {
return unit->next;
}
}
/programs/develop/libraries/framework/trunk/stdlib/makefile
0,0 → 1,5
ROOT=..
 
include ../config.mk
 
all: heap.o malloc.o stdlib.o
/programs/develop/libraries/framework/trunk/stdlib/malloc.c
0,0 → 1,43
/***************************************************************************************************
* Copyright (C) Vasiliy Kosenko (vkos), 2009 *
* This program is free software: you can redistribute it and/or modify it under the terms of the *
* GNU General Public License as published by the Free Software Foundation, either version 3 *
* of the License, or (at your option) any later version. *
* *
* This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; *
* without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See *
* the GNU General Public License for more details. *
* *
* You should have received a copy of the GNU General Public License along with this program. *
* If not, see <http://www.gnu.org/licenses/>. *
***************************************************************************************************/
 
/***************************************************************************************************
* malloc.c - realisation of malloc & free functions based on heap.c *
***************************************************************************************************/
 
#include "malloc.h"
#include "kolibri.h"
#include "heap.h"
 
Heap malloc_heap;
 
void malloc_init(){
// Init system heap
kolibri_heap_init();
// Init main heap for malloc
halMemHeapInit(&malloc_heap, &heap_alloc, NULL, 0);
}
 
void *heap_alloc(Heap *wheap, int nbytes){
return kolibri_malloc(nbytes);
}
 
void *malloc(int nbytes){
return halMemAlloc(&malloc_heap, nbytes);
}
 
void free(void *addr){
halMemFree(&malloc_heap, addr);
}
/programs/develop/libraries/framework/trunk/stdlib/stdlib.c
0,0 → 1,70
/***************************************************************************************************
* Copyright (C) Vasiliy Kosenko (vkos), 2009 *
* Kobra is free software: you can redistribute it and/or modify it under the terms of the GNU *
* General Public License as published by the Free Software Foundation, either version 3 *
* of the License, or (at your option) any later version. *
* *
* Kobra is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without *
* even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
* General Public License for more details. *
* *
* You should have received a copy of the GNU General Public License along with Kobra. *
* If not, see <http://www.gnu.org/licenses/>. *
***************************************************************************************************/
 
/***************************************************************************************************
* Some stdlib functions *
***************************************************************************************************/
 
#include "stdlib.h"
 
void *memcpy(void *dst, void *src, int length){
void *value;
 
if (length & 3) { //length not aligned in 4 bytes use rep movsb
__asm__ __volatile__(
"movl %%edi,%%eax\n\t"
"cld\n\t"
"rep\n\t"
"movsb"
:"=D"(value)
:"c"(length),"S"(src),"D"(dst)
:"eax");
} else { //length aligned in 4 bytes use rep movsd
length=length >> 2;//length=length/4
__asm__ __volatile__(
"movl %%edi,%%eax\n\t"
"cld\n\t"
"rep\n\t"
"movsd"
:"=D"(value)
:"c"(length),"S"(src),"D"(dst)
:"eax");
 
}
return(value);
}
 
char strcmp(char *s1, char *s2){
while (*s1) {
if (*s1++ != *s2++) {
return *--s1-*--s2;
}
}
return 0;
}
 
int strlen(char *s){
int i;
while (*s++) {
++i;
}
return i;
}
 
char *strcpy(char *dest, char *src){
while (*src) {
*dest++ = *src++;
}
*dest = '\0';
}