Oct 16, 2007

WMArray vs. WMList

Yesterday I have analized sources of WINGs and WindowMaker a little. Now I'm certain that WMArrays are mostly misused. Little research showed that the most used pattern of accessing data in arrays is plain iteration form beginning to end. There are only four exceptions (out of approximately 23 use cases), where random access to data is used: WMList, WMPopupButton, WMSplitView, and switch panel. And I don't think that all of those can't be converted to using linked lists and be more efficient. Moreover, linked lists are actually used in many places in WINGs. For example, event handlers are organized in lists, notification observers are also organized in lists.

I'm not talking here about blind replacing of all arrays with linked lists, it would be stupid. But if I feel that linked list is more appropriate structure for particular task, I'll use it. If I see, that some linked list is implemented ad hoc, I'll replace it with WMLList data structure. There's possibility that after removal of WMPropLists, WMLLists will take place of proplist arrays.

Since the name WMList is already taken by list widget, I will use the name WMLList for data structure. I will probably change all names later anyway. Now I'm implementing WMLList object as double-linked list. If there will be never the need to iterate those lists in reverse direction, I'll remove second pointer, but currently I think this small memory overhead will pay off shortly.

No comments: