1 files changed, 392 insertions, 0 deletions

diff --git a/linden/indra/llcommon/llpagemem.h b/linden/indra/llcommon/llpagemem.h
new file mode 100644
index 0000000..7081251
--- /dev/null
+++ b/linden/indra/llcommon/llpagemem.h
@@ -0,0 +1,392 @@
+/** 
+ * @file llpagemem.h
+ *
+ * Copyright (c) 2002-2007, Linden Research, Inc.
+ * 
+ * The source code in this file ("Source Code") is provided by Linden Lab
+ * to you under the terms of the GNU General Public License, version 2.0
+ * ("GPL"), unless you have obtained a separate licensing agreement
+ * ("Other License"), formally executed by you and Linden Lab.  Terms of
+ * the GPL can be found in doc/GPL-license.txt in this distribution, or
+ * online at http://secondlife.com/developers/opensource/gplv2
+ * 
+ * There are special exceptions to the terms and conditions of the GPL as
+ * it is applied to this Source Code. View the full text of the exception
+ * in the file doc/FLOSS-exception.txt in this software distribution, or
+ * online at http://secondlife.com/developers/opensource/flossexception
+ * 
+ * By copying, modifying or distributing this software, you acknowledge
+ * that you have read and understood your obligations described above,
+ * and agree to abide by those obligations.
+ * 
+ * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
+ * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
+ * COMPLETENESS OR PERFORMANCE.
+ */
+#ifndef LL_LLPAGEMEM_H
+#define LL_LLPAGEMEM_H
+
+#if !LL_DARWIN
+#include "malloc.h"
+#endif
+
+#include "llrand.h"
+
+
+#ifndef __GNUC__
+template <class Object, U32 mPageSize=1024> 
+class LLPageMemory 
+{
+private:
+
+        union XObject
+        {
+                XObject *mNextFreeObject;
+                U8               mObject[sizeof(Object)];
+        };
+
+        template <U32 mPageSize> struct Page
+        {
+                XObject *mFirstFreeObject;
+                U32      mObjectCount;
+                U8       mObjects[mPageSize-8];
+
+                void init(U32 mObjPerPage)
+                {
+                        XObject *o = (XObject*)&mObjects;
+                        mObjectCount     = 0;
+                        mFirstFreeObject = o;
+        
+                        for (U32 i = 0; i < mObjPerPage-1; i++) 
+                        {
+                                o->mNextFreeObject = o+1;
+                                o++;
+                        }
+                        o->mNextFreeObject = NULL;
+                };
+
+                Object* alloc()
+                {
+                        if (mFirstFreeObject)
+                        {
+                                XObject     *ret = mFirstFreeObject;
+                                mFirstFreeObject = mFirstFreeObject->mNextFreeObject;
+                                ret->mNextFreeObject = NULL;
+                                mObjectCount++;
+                                return (Object*)&ret->mObject;
+                        };
+                        return NULL;
+                }
+        };
+
+        U32     mObjPerPage;
+        U32     mMaxPages;
+        U32     mObjectCount;
+
+        Page<mPageSize>*   mPageMemory;
+        Page<mPageSize>*   mFirstPage;
+
+public:
+        U32 precise, anywhere, fail;
+
+        void    init()
+        {
+                Page<mPageSize> *p = mFirstPage;
+                for (U32 i = 0; i < mMaxPages; i++) 
+                {
+                        p[i].init(mObjPerPage);
+                }
+
+                precise  = 0;
+                anywhere = 0;
+                fail     = 0;
+        };
+
+public:
+
+        Page<mPageSize>*  pageof(Object *object)
+        {
+                return (Page<mPageSize>*) ((((U32)object - 8) / mPageSize) * mPageSize );
+        }
+
+        LLPageMemory(U32 maxObjects)
+        {
+                mObjPerPage = (mPageSize-8) / sizeof(Object);
+                mMaxPages   = (maxObjects / mObjPerPage) + 1;
+                mObjectCount= 0;
+
+                //printf("%d objects per page, %d pages total, %d/%d objects\n",
+                //      mObjPerPage, mMaxPages, mMaxPages * mObjPerPage,maxObjects);
+
+                mPageMemory = (Page<mPageSize>*)calloc(mPageSize,mMaxPages+1);
+                mFirstPage = mPageMemory;
+                U32 fix = ((U32)mPageMemory % mPageSize);
+                if (fix) mFirstPage = (Page<mPageSize>*)((U32)mPageMemory+mPageSize-fix);
+        
+                //printf("fix = %d\n",fix);
+
+                init();
+        };
+
+        LLPageMemory(void *pageMem, U32 bytes)
+        {
+        }
+
+        ~LLPageMemory()
+        {
+                if (mPageMemory)
+                {
+                        free(mPageMemory);
+                }
+        }
+        
+        Object*     alloc(Object *after=NULL)
+        {
+                Page<mPageSize> * p = mFirstPage;
+                Object          * o = NULL;
+                U32               i = mMaxPages;
+
+                if (after)
+                {
+                        o = pageof(after)->alloc();
+                        if (o) 
+                        {
+                                precise++;
+                                return o;
+                        }
+                        return NULL;
+                }
+
+                F32 frac   = 1.0f / (F32)mMaxPages;             
+                F32 thresh = 0.0f;
+                for (i = 0; i < mMaxPages; i++)
+                {
+                        if (thresh > ((F32)p[i].mObjectCount / (F32)mObjPerPage))
+                        {
+                                o = p[i].alloc();
+                                if (o) 
+                                {
+                                        //printf("allocating page %x obj %x\n",p, o);
+                                        anywhere++;
+                                        return o;
+                                }
+                        }
+                        thresh += frac;
+                } 
+
+                fail++;
+                return NULL;
+        };
+
+        void        free(Object *o)
+        {
+                if (!o) return;
+
+                Page<mPageSize> *page = pageof(o);
+                XObject *obj = (XObject*)o;
+
+                //printf("freeing %x\n",obj);
+
+                obj->mNextFreeObject    = page->mFirstFreeObject;
+                page->mFirstFreeObject  = obj;
+                page->mObjectCount--;
+
+                //printf("freeing page %x %d\n",page, page->mObjectCount);
+        };
+
+        U32  indexof(Object *object)
+        {
+                if (!object) return -1;
+
+                return ((((U32)object-8) % mPageSize) / sizeof(Object)) + 
+                           ((pageof(object) - mFirstPage) * mObjPerPage);
+        }
+
+
+        void dump()
+        {
+
+                for (U32 i=0;i < mMaxPages;i++)
+                {
+                        //printf("page %d   %d/%d objects\n",i,mFirstPage[i].mObjectCount,mObjPerPage);
+                }
+                //printf("precise = %d anywhere %d ratio = %f\n",precise,anywhere,(F32)precise/(F32)(anywhere+precise));
+                //printf("fail = %d\n",fail);
+
+        }
+
+        static void test()
+        {
+                struct Foo
+                {
+                        U32 ord;
+                        U32 foo[8];
+                };
+
+                const U32 count = 100;
+                U32 i,c;
+                U32 mix = 50;
+
+                LLPageMemory<Foo> mem(count);
+                LLRand rand(LLUUID::getRandomSeed());
+
+                Foo *obj[count];
+
+                for (i=0;i<count;i++) obj[i] = 0;
+
+                U32 x= 0;
+                for (U32 run=0; run < 10000 ;run++)
+                {
+                        U32 m =rand.llrand(count);
+                        for (c=0;c < m;c++)
+                        {
+                                U32 j = rand.llrand(count);
+                                if (obj[j]) 
+                                {
+                                        mem.free(obj[j]);
+                                        obj[j] = 0;
+                                }
+                        }
+
+                        m =rand.llrand(count);
+                        for (c=0;c<m;c++)
+                        {
+                                U32 i = rand.llrand(count);
+                                while (obj[i] && i < count) i++;
+
+                                if (!obj[i]) 
+                                {
+                                        if (i > 0) obj[i] = mem.alloc(obj[i-1]);
+                                        else       obj[i] = mem.alloc();
+                                        if (obj[i]) obj[i]->ord = x++;
+                                }
+                        }
+                }
+
+                for (i = 0; i< count; i++)
+                {
+                        //printf("obj[%2d] = %08x %02d %4d\n",i,obj[i],mem.indexof(obj[i]),(obj[i] ? obj[i]->ord : -1));
+                }
+
+                mem.dump();
+        }
+};
+
+
+template <class Object> 
+class LLObjectPool
+{
+private:
+
+        class XObject
+        {
+        public:
+                Object   mObject;
+                U32      mNextFreeObject;
+
+                XObject() { mObject = NULL; mNextFreeObject = 0; }
+        };
+
+        U32      mNumObjects;
+        U32              mMaxObjects;
+        XObject* mObjects;
+        U32      mFirstFreeObject;
+
+        U32 indexof(XObject *xobj) { return (xobj - mObjects); }
+
+public:
+        LLObjectPool(U32 maxObjects)
+        {
+                mMaxObjects = maxObjects;
+                mFirstFreeObject = 0;
+
+                mObjects = new XObject[mMaxObjects];
+
+                //printf("objectpool allocated %d bytes\n",sizeof(XObject) * mMaxObjects);
+
+                for (U32 i=0;i<mMaxObjects;i++) mObjects[i].mNextFreeObject = i+1;
+        };
+
+        ~LLObjectPool()
+        {
+                delete [] mObjects;
+                mObjects = NULL;
+        }
+
+        Object*     alloc(Object *after=NULL)
+        {
+                XObject *obj     = &mObjects[mFirstFreeObject];
+                mFirstFreeObject = obj->mNextFreeObject;
+                if (mFirstFreeObject >= mMaxObjects)
+                {
+                        llerrs << "Attempted to allocate too many objects out of pool\n" << llendl;
+                        llassert(0);
+                }
+                return &obj->mObject;
+        };
+
+        void        free(Object *obj)
+        {
+                if (!obj) return;
+                XObject *xobj         = (XObject*)obj;
+                xobj->mNextFreeObject = mFirstFreeObject;
+                mFirstFreeObject      = indexof(xobj);
+        };
+
+        static void test()
+        {
+                struct Foo
+                {
+                        U32 ord;
+                        U32 foo[8];
+                };
+
+                const U32 count = 100;
+                U32 i,c;
+                U32 mix = 50;
+
+                LLPageMemory<Foo> mem(count);
+                LLRand rand(LLUUID::getRandomSeed());
+
+                Foo *obj[count];
+
+                for (i=0;i<count;i++) obj[i] = 0;
+
+                U32 x= 0;
+                for (U32 run=0; run < 10000 ;run++)
+                {
+                        U32 m =rand.llrand(count);
+                        for (c=0;c < m;c++)
+                        {
+                                U32 j = rand.llrand(count);
+                                if (obj[j]) 
+                                {
+                                        mem.free(obj[j]);
+                                        obj[j] = 0;
+                                }
+                        }
+
+                        m =rand.llrand(count);
+                        for (c=0;c<m;c++)
+                        {
+                                U32 i = rand.llrand(count);
+                                while (obj[i] && i < count) i++;
+
+                                if (!obj[i]) 
+                                {
+                                        if (i > 0) obj[i] = mem.alloc(obj[i-1]);
+                                        else       obj[i] = mem.alloc();
+                                        if (obj[i]) obj[i]->ord = x++;
+                                }
+                        }
+                }
+
+                for (i = 0; i< count; i++)
+                {
+                        //printf("obj[%2d] = %08x %02d %4d\n",i,obj[i],mem.indexof(obj[i]),(obj[i] ? obj[i]->ord : -1));
+                }
+        }
+};
+#endif // !defined __GNUC__
+
+#endif