Method GetFreeMenuItemID

source/script_menu.cpp:353–406

UINT Script::GetFreeMenuItemID()
// Returns an unused menu item ID, or 0 if all IDs are used.
{
	// Need to find a menuID that isn't already in use by one of the other menu items.
	// But also need to conserve menu items since only a relatively small number of IDs is available.
	// Can't simply use ID_USER_FIRST + mMenuItemCount because: 1) There might be more than one
	// user defined menu; 2) a menu item in the middle of the list may have been deleted,
	// in which case that value would already be in use by the last item.
	// Update: Now using caching of last successfully found free-ID to greatly improve avg.
	// performance, especially for menus that contain thousands of items and submenus, such as
	// ones that are built to mirror an entire nested directory structure.  Caching should
	// improve performance even after all menu IDs within the available range have been
	// allocated once (via adding and deleting menus + menu items) since large blocks of free IDs
	// should be free, and on average, the caching will exploit these large free blocks.  However,
	// if large amounts of menus and menu items are continually deleted and re-added by a script,
	// the pool of free IDs will become fragmented over time, which will reduce performance.
	// Since that kind of script behavior seems very rare, no attempt is made to "defragment".
	// If more performance is needed in the future (seems unlikely for 99.9999% of scripts),
	// could maintain an field of ~64000 bits, each bit representing whether a menu item ID is
	// free.  Then, every time a menu or one or more of its IDs is deleted or added, the corresponding
	// ID could be marked as free/taken.  That would add quite a bit of complexity to the menu
	// delete code, however, and it would reduce the overall maintainability.  So it definitely
	// doesn't seem worth it, especially since Windows XP seems to have trouble even displaying
	// menus larger than around 15000-25000 items.
	static UINT sLastFreeID = ID_USER_FIRST - 1;
	// Increment by one for each new search, both due to the above line and because the
	// last-found free ID has a high likelihood of still being in use:
	++sLastFreeID;
	bool id_in_use;
	// Note that the i variable is used to force the loop to complete exactly one full
	// circuit through all available IDs, regardless of where the starting/cached value:
	for (int i = 0; i < (ID_USER_LAST - ID_USER_FIRST + 1); ++i, ++sLastFreeID) // FOR EACH ID
	{
		if (sLastFreeID > ID_USER_LAST)
			sLastFreeID = ID_USER_FIRST;  // Wrap around to the beginning so that one complete circuit is made.
		id_in_use = false;  // Reset the default each iteration (overridden if the below finds a match).
		for (UserMenu *m = mFirstMenu; m; m = m->mNextMenu) // FOR EACH MENU
		{
			for (UserMenuItem *mi = m->mFirstMenuItem; mi; mi = mi->mNextMenuItem) // FOR EACH MENU ITEM
			{
				if (mi->mMenuID == sLastFreeID)
				{
					id_in_use = true;
					break;
				}
			}
			if (id_in_use) // No point in searching the other menus, since it's now known to be in use.
				break;
		}
		if (!id_in_use) // Break before the loop increments sLastFreeID.
			break;
	}
	return id_in_use ? 0 : sLastFreeID;
}