Home - sourcemod-central - file revision - knight/shared/KeLumpAllocator.cpp@f3b8bbe17f85 Mercurial
summary | shortlog | changelog | graph | tags | branches | files | changeset | file | latest | revisions | annotate | diff | raw | help
knight/shared/KeLumpAllocator.cpp
author David Anderson <dvander@alliedmods.net>
Wed Feb 25 20:07:12 2009 -0500 (2009-02-25)
changeset 2607 f3b8bbe17f85
parent 2226 d10b38524be3
child 2541 0352326a1f3f
permissions -rw-r--r--
Backed out changeset fa286305bd3f 
     1 #include "KePlatform.h"
     2 #include <KeLumpAllocator.h>
     3 #include <KeVector.h>
     4 
     5 using namespace Knight;
     6 
     7 /**
     8  * :TODO: don't make this part of the page, because touching it means 
     9  * dirtying a page.  Instead, we should have a separate linked list.
    10  * Maybe that linked list itself could be marshalled from one page.
    11  */
    12 struct KeLumpRegion
    13 {
    14 	char *base;
    15 	char *cur;
    16 	size_t size;
    17 	size_t avail;
    18 	KeLumpRegion *next;
    19 	KeLumpRegion *prev;
    20 };
    21 
    22 class KeLumpAllocator
    23 {
    24 public:
    25 	KeLumpAllocator() : m_pUsableRegions(NULL), m_pUnusableRegions(NULL)
    26 	{
    27 		m_DefLumpSize = 65536;
    28 
    29 #if defined KE_PLATFORM_WINDOWS
    30 		SYSTEM_INFO info;
    31 
    32 		GetSystemInfo(&info);
    33 		if (info.dwAllocationGranularity > m_DefLumpSize)
    34 		{
    35 			m_DefLumpSize = info.dwAllocationGranularity;
    36 		}
    37 #endif
    38 	}
    39 
    40 	~KeLumpAllocator()
    41 	{
    42 		FreeRegionChain(m_pUsableRegions);
    43 		FreeRegionChain(m_pUnusableRegions);
    44 	}
    45 
    46 	void Reset()
    47 	{
    48 		KeLumpRegion *region;
    49 
    50 		/* Find the tail of the usable regions. */
    51 		region = m_pUsableRegions;
    52 		while (region != NULL)
    53 		{
    54 			if (region->next == NULL)
    55 			{
    56 				break;
    57 			}
    58 		}
    59 
    60 		/* Link the unusable chain into the usable chain. */
    61 		if (region == NULL)
    62 		{
    63 			m_pUsableRegions = m_pUnusableRegions;
    64 		}
    65 		else
    66 		{
    67 			region->next = m_pUnusableRegions;
    68 			m_pUnusableRegions->prev = region;
    69 		}
    70 		m_pUnusableRegions = NULL;
    71 
    72 		region = m_pUsableRegions;
    73 		while (region != NULL)
    74 		{
    75 			region->avail = region->size;
    76 			region->cur = region->base;
    77 			region = region->next;
    78 		}
    79 	}
    80 
    81 	void FreeRegionChain(KeLumpRegion *region)
    82 	{
    83 		KeLumpRegion *next;
    84 
    85 		while (region != NULL)
    86 		{
    87 			next = region->next;
    88 			
    89 #if defined KE_PLATFORM_WINDOWS
    90 			VirtualFree(region, 0, MEM_RELEASE);
    91 #endif
    92 			region = next;
    93 		}
    94 	}
    95 
    96 	void *Alloc(size_t size)
    97 	{
    98 		char *blob;
    99 		KeLumpRegion *region;
   100 
   101 		if (size % 8 != 0)
   102 		{
   103 			size += 8;
   104 			size -= size % 8;
   105 		}
   106 
   107 		region = FindRegionForSize(size);
   108 
   109 		blob = region->cur;
   110 		region->avail -= size;
   111 		region->cur += size;
   112 
   113 		/** 
   114 		 * Technically we could make one last small allocation, but 
   115 		 * this edge case is not worth the extra work.
   116 		 */
   117 		if (region->avail < 8)
   118 		{
   119 			/* Unlink us from the usable list */
   120 			if (region == m_pUsableRegions)
   121 			{
   122 				m_pUsableRegions = m_pUsableRegions->next;
   123 				m_pUsableRegions->prev = NULL;
   124 			}
   125 			else
   126 			{
   127 				region->prev->next = region->next;
   128 				if (region->next != NULL)
   129 				{
   130 					region->next->prev = region->prev;
   131 				}
   132 			}
   133 
   134 			/* Link us into the unusable list */
   135 			region->prev = NULL;
   136 			region->next = m_pUnusableRegions;
   137 
   138 			if (m_pUnusableRegions != NULL)
   139 			{
   140 				m_pUnusableRegions->prev = region;
   141 			}
   142 
   143 			m_pUnusableRegions = region;
   144 		}
   145 
   146 		return blob;
   147 	}
   148 
   149 private:
   150 	KeLumpRegion *FindRegionForSize(size_t size)
   151 	{
   152 		char *base;
   153 		KeLumpRegion *region;
   154 		size_t size_of_region;
   155 
   156 		/**
   157 		 * :TODO: replace this with a priority queue or something 
   158 		 * that's actually fast.  Even worse is we dirty pages by 
   159 		 * doing this.  Ouch!
   160 		 */
   161 		region = m_pUsableRegions;
   162 		while (region != NULL)
   163 		{
   164 			if (region->avail >= size)
   165 			{
   166 				return region;
   167 			}
   168 			region = region->next;
   169 		}
   170 
   171 		/* Make sure regions end at 8-byte alignment. */
   172 		size_of_region = sizeof(KeLumpRegion);
   173 		if (size_of_region % 8 != 0)
   174 		{
   175 			size_of_region += 8;
   176 			size_of_region -= size_of_region % 8;
   177 		}
   178 
   179 		/* If the size is too big, fix that. */
   180 		if (size > m_DefLumpSize - size_of_region)
   181 		{
   182 			size += m_DefLumpSize;
   183 			size -= size % m_DefLumpSize;
   184 		}
   185 		else
   186 		{
   187 			size = m_DefLumpSize;
   188 		}
   189 
   190 #if defined KE_PLATFORM_WINDOWS
   191 		base = (char *)VirtualAlloc(
   192 			NULL,
   193 			m_DefLumpSize,
   194 			MEM_COMMIT|MEM_RESERVE,
   195 			PAGE_READWRITE);
   196 #endif
   197 
   198 		/* Initialize the region */
   199 		region = (KeLumpRegion *)base;
   200 		region->base = &base[size_of_region];
   201 		region->size = size - size_of_region;
   202 		region->cur = region->base;
   203 		region->avail = region->size;
   204 		region->prev = NULL;
   205 		region->next = m_pUsableRegions;
   206 
   207 		if (m_pUsableRegions != NULL)
   208 		{
   209 			m_pUsableRegions->prev = region;
   210 		}
   211 
   212 		m_pUsableRegions = region;
   213 
   214 		return region;
   215 	}
   216 
   217 private:
   218 	KeLumpRegion *m_pUsableRegions;
   219 	KeLumpRegion *m_pUnusableRegions;
   220 	size_t m_DefLumpSize;
   221 };
   222 
   223 inline KeLumpAllocator *ke_LumpFromAllocator(ke_allocator_t *arena)
   224 {
   225 	return (KeLumpAllocator *)arena->user;
   226 }
   227 
   228 void *ke_LumpAlloc(ke_allocator_t *arena, size_t size)
   229 {
   230 	return ke_LumpFromAllocator(arena)->Alloc(size);
   231 }
   232 
   233 void ke_LumpFree(ke_allocator_t *arena, void *ptr)
   234 {
   235 }
   236 
   237 ke_allocator_t * KE_LINK Knight::KE_CreateLumpAllocator()
   238 {
   239 	ke_allocator_t *alloc;
   240 
   241 	alloc = new ke_allocator_t;
   242 	alloc->alloc = ke_LumpAlloc;
   243 	alloc->dealloc = ke_LumpFree;
   244 	alloc->user = new KeLumpAllocator();
   245 
   246 	return alloc;
   247 }
   248 
   249 void KE_LINK Knight::KE_DestroyLumpAllocator(ke_allocator_t *alloc)
   250 {
   251 	delete ke_LumpFromAllocator(alloc);
   252 	delete alloc;
   253 }
   254 
   255 void KE_LINK Knight::KE_ResetLumpAllocator(ke_allocator_t *alloc)
   256 {
   257 	ke_LumpFromAllocator(alloc)->Reset();
   258 }
sourcemod-central
Feed