generic container for ordered maps

[Bruno Haible]

Hi,

Gnulib should have generic containers of types
  - list
  - ordered set
  - set
  - ordered map
  - map

The first three are already implemented. Here comes the implementation for
ordered maps. An "ordered map" is a set of key -> value mappings which is
sorted according to the keys.

It is not frequently needed, but when you need it, it's better to have a
direct implementation than to have to emulate it (by combining an ordered set
with a list).

The operations are:

   Operation                  ARRAY     TREE

   gl_omap_size                O(1)     O(1)
   gl_omap_get               O(log n) O(log n)
   gl_omap_put                 O(n)   O(log n)
   gl_omap_remove              O(n)   O(log n)
   gl_omap_search            O(log n) O(log n)
   gl_omap_search_atleast    O(log n) O(log n)
   gl_omap_iterator            O(1)   O(log n)
   gl_omap_iterator_next       O(1)   O(log n)

Review and comments welcome!

Bruno

0001-omap-New-module.patch
Description: Text Data

0002-array-omap-New-module.patch
Description: Text Data

0003-avltree-omap-New-module.patch
Description: Text Data

0004-rbtree-omap-New-module.patch
Description: Text Data

0005-xomap-New-module.patch
Description: Text Data

0006-array-omap-Add-tests.patch
Description: Text Data

0007-avltree-omap-Add-tests.patch
Description: Text Data

0008-rbtree-omap-Add-tests.patch
Description: Text Data