|
2 registered members (TipmyPip, 1 invisible),
18,699
guests, and 8
spiders. |
|
Key:
Admin,
Global Mod,
Mod
|
|
|
Cheap coding for 100
#408569
10/03/12 20:26
10/03/12 20:26
|
Joined: Apr 2007
Posts: 3,751
Canada
WretchedSid
OP
Expert
|
OP
Expert
Joined: Apr 2007
Posts: 3,751
Canada
|
Let's try something new, in this thread I'm going to share some cheap coding tricks for problems you might or might not have. There is no fixed topic besides that everything posted here has something to do with programming and solving a very specific problem in a very obvious way. Also, you are free to post your own stuff here (one tip per post to make it easier to link to specific entries if that is ever going to be needed). I'm going to start with a problem regarding linked list, how many of you ever had the problem of finding the middle of the linked list? I guess the answer is less than a dozen, but still, if you ever try to sort a linked list with anything else than bubble sort, you are going to come across this problem, and the most straightforward implementation is quite expensive. The cheap coders way to solve this problem? Use two pointers to iterate and skip one entry with the second pointer, when the second one hits the end of the linked list the first one points to the middle. Example:
typedef struct bucket_s
{
struct bucket_s *next;
} bucket_t;
bucket_t *findMiddle(bucket_t *head)
{
bucket_t *c1 = head;
bucket_t *c2 = head;
while(c2->next)
{
c1 = c1->next;
c2 = c2->next;
if(c2->next)
c2 = c2->next;
}
return c1;
}
Shitlord by trade and passion. Graphics programmer at Laminar Research. I write blog posts at feresignum.com
|
|
|
Re: Cheap coding for 100
[Re: WretchedSid]
#408580
10/03/12 21:09
10/03/12 21:09
|
Joined: Nov 2007
Posts: 2,568
Germany, BW, Stuttgart
MasterQ32
Expert
|
Expert
Joined: Nov 2007
Posts: 2,568
Germany, BW, Stuttgart
|
Setting the engine window to the working area of the primary desktop (useful for any kind of editor):
#include <windows.h>
typedef void *HMONITOR;
typedef struct tagMONITORINFO
{
DWORD cbSize;
RECT rcMonitor;
RECT rcWork;
DWORD dwFlags;
} MONITORINFO;
long WINAPI MonitorFromWindow(long hwnd,long dwFlags);
#define PRAGMA_API MonitorFromWindow;user32!MonitorFromWindow
#define MONITOR_DEFAULTTONULL 0x00000000
#define MONITOR_DEFAULTTOPRIMARY 0x00000001
#define MONITOR_DEFAULTTONEAREST 0x00000002
function main()
{
wait(1); // You need to wait 1 because the engine window is created here (which is needed to get the monitor)...
MONITORINFO info;
memset(&info, 0, sizeof(MONITORINFO));
info.cbSize = sizeof(MONITORINFO);
HMONITOR primary = MonitorFromWindow(hWnd, MONITOR_DEFAULTTOPRIMARY);
GetMonitorInfo(primary, &info);
SetWindowPos(hWnd, HWND_TOP, info.rcWork.left, info.rcWork.top, info.rcWork.right - info.rcWork.left, info.rcWork.bottom - info.rcWork.top, SWP_SHOWWINDOW);
SetWindowText(hWnd, "Hotel California - Edit");
video_window(NULL, NULL, 1, NULL);
video_set(info.rcWork.right - info.rcWork.left, info.rcWork.bottom - info.rcWork.top, 32, 2);
}
Last edited by MasterQ32; 10/03/12 21:09.
|
|
|
Re: Cheap coding for 100
[Re: MasterQ32]
#408638
10/04/12 22:29
10/04/12 22:29
|
Joined: Apr 2007
Posts: 3,751
Canada
WretchedSid
OP
Expert
|
OP
Expert
Joined: Apr 2007
Posts: 3,751
Canada
|
Well, another day another cheap trick. It's about linked lists, again, but this time probably more practical. Consider the following, you want to write a container for your list that also provides convinient functions to work with the list's content, the functions are going to be well tested and debugged so you can be sure that it works without any flaws and don't have to copy and paste all over the place and keep track of them in case you have to fix something. But, oh noes, how would a node/bucket in the linked list look like? It must be generic as well, so you will probably end up with something like this:
typedef struct bucket_s
{
void *data;
struct bucket_s *next;
struct bucket_s *prev;
} bucket_t;
But this is rather inelegant, because what exactly are you going to pass around when working with the linked list? The data pointer or the bucket/node (which requires you to keep track of the content and the bucket when working with the data). But if you use just the data, you have too lookup the node the data belongs to every time you want to operate with the list. Deleting a known node, which should be an O(1) operation in a linked list suddenly becomes an O(n) operation! All advantages of a linked list gone, and let's not even talk about walking down the list. So let's go and toss the generic bucket around, let's do two allocations instead of one and let's alway go an indirect route when working with our data, all for the sake of performance and freedom of bugs. No wait, actually, let's do something else. You can tell the list WHERE your next and previous pointers are in the linked list and have it work with this data. So you are free to design your own bucket and still have the advantage of a fast and generic linked list implementation. It's easy to say the least, so I'm just going to leave you with the code which implements the two functions add and delete. Afterwards follows a short example with a custom bucket.
// offsetof Makro
#define offsetof(type, member) ((unsigned int)&(((type *)0)->member))
typedef struct
{
size_t oPrev;
size_t oNext;
void *head;
void *tail;
} list_t;
list_t *list_create(size_t oPrev, size_t oNext)
{
list_t *list = malloc(sizeof(list_t));
if(list)
{
list->oPrev = oPrev;
list->oNext = oNext;
list->head = list->tail = NULL;
}
return list;
}
// Access primitives
#define list_t_accessPrev(list, entry) *((void **)&((char *)entry)[list->oPrev])
#define list_t_accessNext(list, entry) *((void **)&((char *)entry)[list->oNext])
void list_addBack(list_t *list, void *entry)
{
if(list->tail)
{
list_t_accessPrev(list, entry) = list->tail;
list_t_accessNext(list, entry) = NULL;
list_t_accessNext(list, list->tail) = entry;
}
else
{
list_t_accessPrev(list, entry) = NULL;
list_t_accessNext(list, entry) = NULL;
list->head = entry;
}
list->tail = entry;
}
void list_delete(list_t *list, void *entry)
{
void *prev = list_t_accessPrev(list, entry);
void *next = list_t_accessNext(list, entry);
if(prev)
list_t_accessNext(list, prev) = next;
if(next)
list_t_accessPrev(list, next) = prev;
if(list->head == entry)
list->head = next;
if(list->tail == entry)
list->tail = prev;
}
Example:
typedef struct myBucket
{
int i;
struct myBucket *prev;
struct myBucket *next;
} myBucket;
myBucket *bucket_create(int i)
{
myBucket *bucket = malloc(sizeof(myBucket));
bucket->i = i;
return bucket;
}
void main()
{
list_t *list = list_create(offsetof(myBucket, prev), offsetof(myBucket, next));
// Insert ten entries
for(int i=0; i<10; i++)
{
myBucket *bucket = bucket_create(i);
list_addBack(list, bucket);
if((i % 2) == 0) // No, actually, I hate even numbers. Fuck them!
{
list_delete(list, bucket);
free(bucket);
}
}
// Iterate over the entries
myBucket *bucket = list->head;
while(bucket)
{
printf("i: %i\n", bucket->i);
bucket = bucket->next;
}
}
Shitlord by trade and passion. Graphics programmer at Laminar Research. I write blog posts at feresignum.com
|
|
|
|
