deleting internal pointer in QModelIndex

[rickbsgu]

Hmm.

Here's an issue: I'm creating QModelIndexes, and storing a pointer with traversal information via a 'new' operator in the index (so the object is allocated on the heap.)

Problem is, I don't know when the index is deleted - an obvious memory leak issue for the internal pointer object.

Looking through the docs and the code, there doesn't seem to be any way to know when a QModelIndex is being deleted. It would be nice if there was a flag in the index - something like: 'deletePointerOnDestroy'. That way the index could take care of the deletion on it's own.

Any thoughts on how to do something like this? I suppose I could keep a vector of the pointers and then delete them after I know no QModelIndexes were required, but that's not necessarily obvious, either.

Scratching my head... Any thoughts appreciated.

rickb

[wysota]

The pointer should not be owned by the index! It should be owned by the model and only assigned to the index so that in may access it. Model indices are shortlived objects - you shouldn't store them or use them after manipulating the model - they become stale very quickly. Model indices are always required - they are used internally by the model, the view and everything else that touches the model. So... keep your hands away from making model indices too complex. They should be simple and should not carry any information that is not contained in the model. And the pointer should never be used outside the model - it's called "internal" for a reason.

[rickbsgu]

Philosophically, I think I would disagree.

In this case, the pointer contains information to help the traversal and essentially becomes an extension of the index. As such, it is handed off to the index, and it is appropriate that the index be entrusted with destroying it.

Alternatively (if you want to adhere to the assertion), then the index could let me (the model) know that it (the index) is being destroyed, and the model can then do what it needs to clean up anything it has given to the index before said index is destroyed. That would preserve the notion that anything given to the index belongs to the model.

I don't think that breaks any design paradigms, and is consistent with the idea of the index.

my 2c
rickb

[wysota]

Philosophically, I think I would disagree.

It has nothing to do with philosophy or other difficult words. QModelIndex was created to be a simple lightweight object.

In this case, the pointer contains information to help the traversal and essentially becomes an extension of the index. As such, it is handed off to the index, and it is appropriate that the index be entrusted with destroying it.

No, because as long as an item is valid, it has some way to be found (traversed to). If you have an index and then you modify the model, your traversal data becomes stale (invalid) - so keeping such data without regard to the item itself doesn't make sense. It is the model that knows how to find a particular item. If you need some special data for finding the item, store it in the model (or even in the item - for instance using parent-child pointers) and make the model create, update or destroy traversal data.

Alternatively (if you want to adhere to the assertion), then the index could let me (the model) know that it (the index) is being destroyed, and the model can then do what it needs to clean up anything it has given to the index before said index is destroyed. That would preserve the notion that anything given to the index belongs to the model.

See my comment above.

I don't think that breaks any design paradigms, and is consistent with the idea of the index.

Again - the idea of an index is that it is an object that is quick to create and quick to destroy. It should also provide means to traverse data using parent(), sibling() and child() methods for accessing appropriate indices. If you make the index heavy, your application will constantly be busy creating and destroying your traversal data. For instance, if you have 100 items, the process of showing them in a view involves creation and destruction of few hundred indices. Do you want to create and destroy such information several times a second? Isn't it better to just keep it and use it when appropriate?

What kind of data do you have such that it needs some extra data to be traversable? Assuming you have some "Item" structure in your model where you keep items, can't you have methods there that allow traversal and simply pass that item pointer to the index as its internal pointer? Data in applications is usually organized into some kind of graph (net of items) and such structures are very easily traversable.

The post is quite long, so a summary follows:
As long as your model is static (doesn't change), the way to access each of its items doesn't change, hence no extra data needs to be created or destroyed. It is the model that knows if items are created, destroyed or moved thus it is best suited to update any extra data associated with its items. A model index is a volatile and lightweight object - it should be treated as a pointer, nothing more. It doesn't need to know anything about the model - it is the model that can create valid indices, not the other way round - the model controls its indices, indices know nothing about state changes in the model. If the model changes, all its indices should be considered invalid and should be queried for again. If you need to store an index, you should use QPersistentModelIndex and it is the model's job to update all its persistent indices when its state changes.

[rickbsgu]

Well, no, I think you're missing the point - the little things I'm creating are expected to die with the index. They're simply little containers that provide parent/child information, so I don't have to carry them in the model.

Sure, I can create a traversal mechanism (and have, since I can't seem to get a way to insure these items are deleted.) The traversal mechanism can give me paths and I can derive parent-child relationships from the paths. And they're temporary and go away when I'm done with them.

Fineree.

But - why do I have to do a traversal, when Qt is already doing the traversal? I'd rather take advantage of Qt's traversal mechanism, since it's doing it anyway. (And I could, if I could get these little items deleted along with the QModelIndex deletion. )

For instance, if you have 100 items, the process of showing them in a view involves creation and destruction of few hundred indices. Do you want to create and destroy such information several times a second? Isn't it better to just keep it and use it when appropriate?

Well, the indices have to get created and destroyed. What's another 20 bytes or so? Doesn't seem to be adding a lot of weight.

(BTW, the behavior you describe is something of a curiosity - I notice I get called a lot of times for the same indices.)

If the model changes, all its indices should be considered invalid and should be queried for again. If you need to store an index, you should use QPersistentModelIndex and it is the model's job to update all its persistent indices when its state changes.

No, I certainly don't need that. All I'm looking to do is give the indexes a little extra information that will help me create proper indexes, subsequently.

Anyway. The tradeoff boils down to adding a small amount of complexity to the indices or a larger amount of complexity to the model to achieve the same thing. I'd rather go with the smaller amount of complexity, if I have the choice.

Since I don't have the choice (at least not without modifying the Qt code - which I really don't want to do), I've re-implemented along the lines you've suggested.

Cheers,
rickb

[wysota]

Well, no, I think you're missing the point

We can continue this discussion forever but it won't change the fact you are trying to do with the index something it was never designed for. If you want to be smarter than people who actually thought of and implemented QModelIndex, go argue with them - I'm just repeating what I was told and with what I completely agree.

- the little things I'm creating are expected to die with the index. They're simply little containers that provide parent/child information, so I don't have to carry them in the model.

"parent" and "child" are attributes of items, not index objects. No matter how many times you are going to deny that, I'll keep repeating it, because hierarchy is the attribute of the model and not its index.

The traversal mechanism can give me paths and I can derive parent-child relationships from the paths. And they're temporary and go away when I'm done with them.

What do you mean by that you are done with them? If you want to manipulate the model again a while later will they be different than a moment ago? If not, why constantly create and delete them? It's a big overhead.

But - why do I have to do a traversal, when Qt is already doing the traversal? I'd rather take advantage of Qt's traversal mechanism, since it's doing it anyway. (And I could, if I could get these little items deleted along with the QModelIndex deletion. )

Don't ask me - I never needed any traversal data for my models and I implemented quite a number of them in my life. I'm using the mechanism Qt provides - using QAbstractItemModel::index(), QAbstractItemModel::parent() and QAbstractItemModel::rowCount().

Well, the indices have to get created and destroyed. What's another 20 bytes or so?

Yes... If you have 10000 of these created every second then that's quite some time needed to allocate and deallocate memory.

Doesn't seem to be adding a lot of weight.

They do, but it's not about the memory footprint but rather the time needed to create and destroy them.

(BTW, the behavior you describe is something of a curiosity - I notice I get called a lot of times for the same indices.)

Yes, that's one of the problems with InterView - it wants data much too often. But that's the way it is and until InterViewNG comes out we have to live with it.

All I'm looking to do is give the indexes a little extra information that will help me create proper indexes, subsequently.

It's the model that creates indexes, not QModelIndex... (how many times have I already written this?) Thus the index doesn't need any extra data. The internal pointer is to be used solely by the model or abused by external objects if they are not designed correctly. internalPointer() shouldn't be available outside the model - it's one of those little things that breaks its OO design.

Anyway. The tradeoff boils down to adding a small amount of complexity to the indices or a larger amount of complexity to the model to achieve the same thing. I'd rather go with the smaller amount of complexity, if I have the choice.

Please do and when you're finished with it, write an article about it and I will gladly read it. Just note there are no virtual methods in QModelIndex (and no wonder - it is meant to be lightweight!), so subclassing it is useless.

Since I don't have the choice (at least not without modifying the Qt code - which I really don't want to do), I've re-implemented along the lines you've suggested.

That's not true. You can subclass the index, inherit QObject that has a virtual destructor and even emit signals from the index. Just expect your application to be really slow.

As a side note - it occured that QModelIndex in its current state was too expensive to use on Java, so Qt Jambi doesn't use it.

[rickbsgu]

We can continue this discussion forever but it won't change the fact you are trying to do with the index something it was never designed for. If you want to be smarter than people who actually thought of and implemented QModelIndex, go argue with them - I'm just repeating what I was told and with what I completely agree.


"parent" and "child" are attributes of items, not index objects. No matter how many times you are going to deny that, I'll keep repeating it, because hierarchy is the attribute of the model and not its index.

Then why does the view ask for parents? What does it care, if there are no parent/child relationships among the items (this is for a QTreeView, BTW).

What do you mean by that you are done with them? If you want to manipulate the model again a while later will they be different than a moment ago? If not, why constantly create and delete them? It's a big overhead.

No, it's not that big. Just following a few pointers. (It's the way OpenInventor works, BTW - doesn't seem to slow it up. XML XPaths do the same kind of thing. XML can be slow, but not because of pathing. If anything, pathing can speed things up - if you can re-use the paths.)

Don't ask me - I never needed any traversal data for my models and I implemented quite a number of them in my life. I'm using the mechanism Qt provides - using QAbstractItemModel::index(), QAbstractItemModel::parent() and QAbstractItemModel::rowCount().

Gotta get it a parent, somehow...

It's the model that creates indexes, not QModelIndex... (how many times have I already written this?) Thus the index doesn't need any extra data. The internal pointer is to be used solely by the model or abused by external objects if they are not designed correctly. internalPointer() shouldn't be available outside the model - it's one of those little things that breaks its OO design.

I'm not arguing that. I'm (the model) the only one using the internal pointer. It just has to get deleted, somehow.

Please do and when you're finished with it, write an article about it and I will gladly read it. Just note there are no virtual methods in QModelIndex (and no wonder - it is meant to be lightweight!), so subclassing it is useless.

It's a demo of something I did in Qt3. Want to re-implement it w/ Qt4's model/view architecture. It's coming along, albeit slowly.

That's not true. You can subclass the index, inherit QObject that has a virtual destructor and even emit signals from the index. Just expect your application to be really slow.

No, don't want to carry the overhead of QObject in the indexes (or in the model items, for that matter) - total agreement, there. (I had a big discussion about that in a previous contract gig, BTW. They wanted the items to behave as QObjects. I disagreed, but was over-ruled. Implemented it under protest.)

As a side note - it occured that QModelIndex in its current state was too expensive to use on Java, so Qt Jambi doesn't use it.

That is interesting. I wonder if it's the same in Qyoto? I know it's quite slow, at the moment, but I don't know if QModelIndex is the culprit.

Another discussion.

thanx,
rickb

[wysota]

Then why does the view ask for parents? What does it care, if there are no parent/child relationships among the items (this is for a QTreeView, BTW).

I don't see your point...

If I show a directory that has a parent directory, I want to be able to access it... What is wrong with that?

No, it's not that big. Just following a few pointers. (It's the way OpenInventor works, BTW - doesn't seem to slow it up. XML XPaths do the same kind of thing. XML can be slow, but not because of pathing. If anything, pathing can speed things up - if you can re-use the paths.)

Two short questions - which is quicker, creating/managing/destroying an object on stack or on heap? Why?

Gotta get it a parent, somehow...

I don't really see a problem... Have you seen the simple tree model example in Qt?

I'm (the model) the only one using the internal pointer. It just has to get deleted, somehow.

The pointer was never meant to be owned by the index. And it doesn't make sense to do so. If you have two indexes pointing to the same item, what is the reason for having two different "internal pointers" in them? Because that's what is meant to happen with your approach and you can't work it around without keeping those objects in the model. And if you do keep them in the model, they shouldn't be owned by indexes or they will make the model go out of sync or worse.

That is interesting. I wonder if it's the same in Qyoto? I know it's quite slow, at the moment, but I don't know if QModelIndex is the culprit.

I don't know what Qyoto is. I know that there is no concept of stack based objects in Java so the whole point in having QModelIndex is denied.

[rickbsgu]

I don't see your point...

If I show a directory that has a parent directory, I want to be able to access it... What is wrong with that?

This is in response to your statement that the indexes don't need to know parent child relationships. If that is the case, then why are they asking for them? - to rephrase the question.

Two short questions - which is quicker, creating/managing/destroying an object on stack or on heap?

Obviously, on the stack, but I can't do that, can I? Since I return after the call, my stack frame is gone.

Why?

Ok, if we must - because all that has to be done is increase the stack pointer and the memory from the last stack pointer position is now ours to use. But, when I return out of my routine, that space is no longer valid. Allocating on the heap requires maintenance of free space/used space pointers, but it sticks around until it's deleted. Heap management algorithms have been optimized to a very high degree in modern operating systems, so it's much less an issue than it used to be.

I guess now it's my turn to ask: what's the relevance?

I don't really see a problem... Have you seen the simple tree model example in Qt?

Yup. And the way they're doing it is carrying a parent pointer in every single item. I don't want to do that.

The pointer was never meant to be owned by the index. And it doesn't make sense to do so. If you have two indexes pointing to the same item, what is the reason for having two different "internal pointers" in them? Because that's what is meant to happen with your approach and you can't work it around without keeping those objects in the model. And if you do keep them in the model, they shouldn't be owned by indexes or they will make the model go out of sync or worse.

Ok, well when we talk about 'ownership' we are most certainly talking on a philosophical basis, aren't we? At least in terms of design.

(If it gets heated, then I guess it's religion...)

Let's see: I don't mind owning the extra little pieces, but I have to know when an index is destroyed, so I can destroy the extra little piece it's carrying. OTOH, I don't have a problem giving the index ownership of the extra little piece - if I do it explicitly, and there is an explicit mechanism for the index to delete it once it's finished.

You're correct, there would be different 'pointers' for multiple requests of the same index, but the internal information would be the same. That's an unfortunate outfall of the implementation - it seems a smarter implementation would only ask for each index once (on a given operation - it would re-ask for the index on a new operation, since the indexes used for the previous operation have been trashed. We hope.)

I don't know what Qyoto is. I know that there is no concept of stack based objects in Java so the whole point in having QModelIndex is denied.

It's the C# binding for Qt. Think it has a lot of promise, as C# is really a fast development environment, and the resource usage isn't as heavy as Java. It's being headed up by Richard Dale - there's more info here: http://cougarpc.net/qyoto/. I think C# is a stack based language...

Hmm. Are you suggesting the QModelIndexes are allocated on the stack? That would be pretty tricky, since the index is returned out of the creation stack frame and then the 'request to the model stack' frame. Anything in either stack frames would be invalid. Have to walk through that section of the code and see how it's done.

Later,
rickb

[wysota]

This is in response to your statement that the indexes don't need to know parent child relationships. If that is the case, then why are they asking for them? - to rephrase the question.

Here is how QModelIndex::parent() is implemented ("m" is a pointer to the model):

inline QModelIndex QModelIndex::parent() const
{ return m ? m->parent(*this) : QModelIndex(); }

inline QModelIndex QModelIndex::parent() const
{ return m ? m->parent(*this) : QModelIndex(); }

To copy to clipboard, switch view to plain text mode 

As you see it is the model that gives back the information about the parent.

Obviously, on the stack, but I can't do that, can I? Since I return after the call, my stack frame is gone.

I don't know what you mean, but the point is that QModelIndex is meant to be created on stack. That's why it's so slow in Java - there is no stack there.

Allocating on the heap requires maintenance of free space/used space pointers, but it sticks around until it's deleted.

Sure, but you want to delete it when the index is deleted and the index is created on stack hence you slow down the index by creating some part of it on heap. QModelIndex is so optimized, it doesn't even have a P-IMPL or a shared data pointer.

Heap management algorithms have been optimized to a very high degree in modern operating systems, so it's much less an issue than it used to be.

See the java issue.

I guess now it's my turn to ask: what's the relevance?

I think I already answered that two quotes earlier.

Yup. And the way they're doing it is carrying a parent pointer in every single item. I don't want to do that.

Yes, it's better to carry a whole bunch of stuff in an index... Please...

[quote]Ok, well when we talk about 'ownership' we are most certainly talking on a philosophical basis, aren't we? At least in terms of design./quote]
No. "Ownership" is a well defined term that means that an object can (and should) delete all object it owns when it is destroyed (or sooner).

You're correct, there would be different 'pointers' for multiple requests of the same index, but the internal information would be the same.

Exactly.

That's an unfortunate outfall of the implementation - it seems a smarter implementation would only ask for each index once (on a given operation - it would re-ask for the index on a new operation, since the indexes used for the previous operation have been trashed. We hope.)

And that's exactly what happens if that "extra information" is owned by the model. And in the simplest case the extra information is a pointer to the parent sitting in an item whose pointer is kept as an internal pointer of an index. I dare you to show a simpler solution using up less than sizeof(void*) memory.

Hmm. Are you suggesting the QModelIndexes are allocated on the stack?

Yes! That's the whole point of creating the class in the first place!

That would be pretty tricky, since the index is returned out of the creation stack frame and then the 'request to the model stack' frame.

The index is volatile - it is to be created, used and destroyed immediately.

Take a look at this: http://chaos.troll.no/~ahanssen/devd...delView.tar.gz (slides 32-35).

[rickbsgu]

Here is how QModelIndex::parent() is implemented ("m" is a pointer to the model):

inline QModelIndex QModelIndex::parent() const
{ return m ? m->parent(*this) : QModelIndex(); }

inline QModelIndex QModelIndex::parent() const
{ return m ? m->parent(*this) : QModelIndex(); }

To copy to clipboard, switch view to plain text mode 

As you see it is the model that gives back the information about the parent.

The question remains unanswered: If the view doesn't care about parent-child relationships, why is it asking for parents? And why is there a 'child()' member?

I'll provide the answer that I perceive: it is creating a view hierarchy, and it needs to set up it's own parent-child relationship to mirror that of the model. It uses the model index queries to do so.

Yes, it's better to carry a whole bunch of stuff in an index... Please...

Are we married? If not, I'd like to keep the discussion on a professional level without the snide asides. The tone of a bickering couple is not conducive to the exchange of ideas.


So - using the examples you sent (thanks for the reference, BTW - that's a good write-up. Wish I could have gone), the standard test seems to be 100,000 items.

100,000 items, every one of them carrying a parent pointer, adds up to 100,000 words, or 400,000 bytes on a 32-bit machine devoted to back-pointers. Twice that on a 64 bit machine.

Given that page sizes are typically what? around 8k or so, that's a lot of pages tied up in carrying pointers. If they were contiguous, the memory manager could shove them out of the way until they're needed. But, the problem is, the pointers are interspersed throughout the model, so you're upping the liability of page-faults carrying around what is essentially a lot of dead weight - especially in a flat hierarchy (which UI hierarchies tend to be - most of the pointers will be carrying duplicate information.)

So, then, a little itty bitty structure that is consructed on the fly and then goes away when it's not needed, to establish parent-child relationships makes a lot of sense.

Ok, well when we talk about 'ownership' we are most certainly talking on a philosophical basis, aren't we? At least in terms of design.

No. "Ownership" is a well defined term that means that an object can (and should) delete all object it owns when it is destroyed (or sooner).

Fine. I give ownership of the little chunks I create to the model item.

"Ownership" is well-defined to whom? The code? The machine? Neither have any concept of 'ownership'. It's purely a design concept imparted by the designers. All they (the objects) 'know' is they carry a pointer that needs to be or does not need to be deleted. And, since there are different notions of how ownership plays out - for instance, whether it should be permantly assigned or be transferable is a matter of policy, it falls squarely in the province of philosophy.

I don't have a problem with transferring ownership of a bit of memory. You apparently do. That is a fundamental difference in philosophy. We'll have to agree to disagree on that score.

And that's exactly what happens if that "extra information" is owned by the model. And in the simplest case the extra information is a pointer to the parent sitting in an item whose pointer is kept as an internal pointer of an index. I dare you to show a simpler solution using up less than sizeof(void*) memory.

Sure - do as another member here has done: store paths of small integers. Of course you're limited to the number of children you can store in a byte or a nibble, and that correspondingly limits the depth. A small structure, on the other hand, removes such constraints.

The index is volatile - it is to be created, used and destroyed immediately.

That it's short lived, I don't have a problem with. But they're not all destroyed immediately, because they're fed back to me for further action (like discovering parent-child relationships.) Not only that, but they come to me in a specific order.

They wink in and out of existence - no problem. In fact, that's a benefit. I would either like to know when they go out of existence, since they're carrying a bit of information I gave them, or I can transfer ownership to them (knowing they can be destroyed at any moment), and work within that constraint. No sweat.

As far as memory allocation algorithms being inefficient, they're pretty well optimized for creating and destroying little pieces of the same size frequently in a tight loop. The following code works on four architectures: MacOS, Linux, FreeBSD, and Windows. It does a million allocations and a few less frees of objects. You'll note the allocation routine settles down to around 20-26 pointers assigned/reassigned, over-all. It runs almost instantaneously on Mac/Linux - a bit slower on Windows (maybe all this optimization effort is to compensate for Windows inefficiencies... wouldn't be surprised.)


In summary, my assertion is that page-swapping is the real culprit, and if you're not reducing weight over-all, you're just asking for more page-faults. One page-fault is worth a whole lot of machine instructions.

My 2c

#include <iostream>
#include <time.h>
 
using namespace std;
 
#ifdef _WIN32
  #define random rand
  #define srandom srand
#endif
 
struct LittleStruct
{
  void *pointer1, *pointer2;
  int val1, val2;
  LittleStruct *ls1;
};
 
static const int SIZE_ASSIGNED = 100000, NUM_RUN = 1000000, SIZE_POOL = 20,
     		 DRAIN = SIZE_POOL - SIZE_POOL / 4, LOG_EVERY = NUM_RUN / 1000;
 
#ifdef _WIN32
static const long long RAND_TOP = RAND_MAX;
#else
static const long long RAND_TOP = (1 << 31) - 1;
#endif
 
static LittleStruct *assigned_ptrs[SIZE_ASSIGNED], *pool[SIZE_POOL];
 
static int numAssigned = 0, numAllocs = 0, numFrees = 0;
 
static inline int getPoolIX()
{
  long long bigrand = (long long)random() * 20;
  int rand = bigrand / RAND_TOP;
  if (rand == 20) rand = 19;
			// clunky, but it'll do for this
  return (rand);
}
 
static void freeSlot()
{
  int slot = getPoolIX();
  if (pool[slot] != NULL)
  {
    numFrees++;
    delete pool[slot];
    pool[slot] = NULL;
  }
}
 
static LittleStruct *allocSlot()
{
  int ix;
  for (;;)
  {
    for (ix = 0; ix < SIZE_POOL; ix++)
    {
      int slot = getPoolIX();
      if (pool[slot] == NULL)
      {
        numAllocs++;
	return (pool[slot] = new LittleStruct());
      }
      else
        freeSlot();
    } 
 
    for (ix = 0; ix < DRAIN; ix++)
      freeSlot();
  }
 
  return NULL;
}
 
static void tallyAlloced(LittleStruct *ls)
{
  for (int ix = 0; ix < numAssigned; ix++)
    if (assigned_ptrs[ix] == ls) return;
 
  assigned_ptrs[numAssigned++] = ls;
}
 
int main(int argc, char **argv)
{
  bool dolog = false;
 
  if (argc > 1)
  {
    switch(argv[1][0])
    {
      case 't': // check some values and test the random number generator
      {
	char buf[32];
	cout << "SIZE_POOL: " << SIZE_POOL << endl;
	cout << "RAND_TOP: 0x" << hex << RAND_TOP << dec << endl;
 
	for (int ix = 0; ix < 1000; ix++)
	  cout << ix << ": " << getPoolIX() << endl;
       }
       exit(0);
 
      case 'l': // do logs
        dolog = true;
        break;
 
      default:
        cout << "alloctest { t | l }" << endl;
        cout << "where:" << endl;
        cout << "  t: test random number generator, show values." << endl;
        cout << "  l: log output (slows things up, of course...)" << endl;
        exit(0);
    }
  }
 
  else
  {
    srandom(time(NULL));
    memset(pool, SIZE_POOL * sizeof(LittleStruct *), 0);
			  // make sure this is cleared, no matter what
 
    while (numAllocs < NUM_RUN)
    {
      tallyAlloced(allocSlot());
 
      if (dolog && (numAllocs % LOG_EVERY) == 0)
	cout << "NumAllocs: " << numAllocs << 
		", NumFrees: " << numFrees <<
		", NumAssigned: " << numAssigned << endl;
 
      if (numAssigned >= SIZE_ASSIGNED)
      {
	cout << "Overflowed assigned pointer vector" << endl;
	exit(1);
      }
    }
 
    cout << endl << "Run ended: " << endl;
    cout << "Used:\t\t" << numAllocs << " allocations, " << numFrees << " frees." <<endl;
    cout << "     \t\t" << numAssigned << " pointers, total." << endl << endl;
  }
}

#include <iostream>
#include <time.h>

using namespace std;

#ifdef _WIN32
  #define random rand
  #define srandom srand
#endif

struct LittleStruct
{
  void *pointer1, *pointer2;
  int val1, val2;
  LittleStruct *ls1;
};

static const int SIZE_ASSIGNED = 100000, NUM_RUN = 1000000, SIZE_POOL = 20,
     		 DRAIN = SIZE_POOL - SIZE_POOL / 4, LOG_EVERY = NUM_RUN / 1000;

#ifdef _WIN32
static const long long RAND_TOP = RAND_MAX;
#else
static const long long RAND_TOP = (1 << 31) - 1;
#endif

static LittleStruct *assigned_ptrs[SIZE_ASSIGNED], *pool[SIZE_POOL];

static int numAssigned = 0, numAllocs = 0, numFrees = 0;

static inline int getPoolIX()
{
  long long bigrand = (long long)random() * 20;
  int rand = bigrand / RAND_TOP;
  if (rand == 20) rand = 19;
			// clunky, but it'll do for this
  return (rand);
}

static void freeSlot()
{
  int slot = getPoolIX();
  if (pool[slot] != NULL)
  {
    numFrees++;
    delete pool[slot];
    pool[slot] = NULL;
  }
}

static LittleStruct *allocSlot()
{
  int ix;
  for (;;)
  {
    for (ix = 0; ix < SIZE_POOL; ix++)
    {
      int slot = getPoolIX();
      if (pool[slot] == NULL)
      {
        numAllocs++;
	return (pool[slot] = new LittleStruct());
      }
      else
        freeSlot();
    } 

    for (ix = 0; ix < DRAIN; ix++)
      freeSlot();
  }

  return NULL;
}

static void tallyAlloced(LittleStruct *ls)
{
  for (int ix = 0; ix < numAssigned; ix++)
    if (assigned_ptrs[ix] == ls) return;

  assigned_ptrs[numAssigned++] = ls;
}

int main(int argc, char **argv)
{
  bool dolog = false;

  if (argc > 1)
  {
    switch(argv[1][0])
    {
      case 't': // check some values and test the random number generator
      {
	char buf[32];
	cout << "SIZE_POOL: " << SIZE_POOL << endl;
	cout << "RAND_TOP: 0x" << hex << RAND_TOP << dec << endl;
      
	for (int ix = 0; ix < 1000; ix++)
	  cout << ix << ": " << getPoolIX() << endl;
       }
       exit(0);

      case 'l': // do logs
        dolog = true;
        break;
      
      default:
        cout << "alloctest { t | l }" << endl;
        cout << "where:" << endl;
        cout << "  t: test random number generator, show values." << endl;
        cout << "  l: log output (slows things up, of course...)" << endl;
        exit(0);
    }
  }

  else
  {
    srandom(time(NULL));
    memset(pool, SIZE_POOL * sizeof(LittleStruct *), 0);
			  // make sure this is cleared, no matter what

    while (numAllocs < NUM_RUN)
    {
      tallyAlloced(allocSlot());

      if (dolog && (numAllocs % LOG_EVERY) == 0)
	cout << "NumAllocs: " << numAllocs << 
		", NumFrees: " << numFrees <<
		", NumAssigned: " << numAssigned << endl;

      if (numAssigned >= SIZE_ASSIGNED)
      {
	cout << "Overflowed assigned pointer vector" << endl;
	exit(1);
      }
    }

    cout << endl << "Run ended: " << endl;
    cout << "Used:\t\t" << numAllocs << " allocations, " << numFrees << " frees." <<endl;
    cout << "     \t\t" << numAssigned << " pointers, total." << endl << endl;
  }
}

To copy to clipboard, switch view to plain text mode 

[calmspeaker]

I like this post!