/src/opensips/map.c

Source (jump to first uncovered line)
/*
 * Copyright (C) 2009 Voice System SRL
 *
 * This file is part of opensips, a free SIP server.
 *
 * opensips is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version
 *
 * opensips is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
 *
 * History:
 * --------
 * 2009-09-16  initial version (andreidragus)
 *
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "str.h"
#include "map.h"

#include "mem/mem.h"
#include "mem/shm_mem.h"
#include "mem/rpm_mem.h"

#define avl_malloc(dest,size,flags) do \
{ \
  if(flags & AVLMAP_SHARED) \
    (dest) = shm_malloc(size); \
  else if (flags & AVLMAP_PERSISTENT) \
    (dest) = rpm_malloc(size); \
  else \
    (dest) = pkg_malloc(size); \
} while(0)

#define avl_free(dest,flags) do \
{ \
  if(flags & AVLMAP_SHARED) \
    shm_free(dest); \
  else if (flags & AVLMAP_PERSISTENT) \
    rpm_free(dest); \
  else \
    pkg_free(dest); \
} while(0)


#define min(a,b)  ((a)<(b))?(a):(b)


static int str_cmp(str s1, str s2)
{
  int ret;

  ret = strncmp( s1.s, s2.s, min( s1.len, s2.len) );

  if( ret == 0)
    ret =  s1.len -  s2.len;


  return ret;
}


/* Creates and returns a new table
   with comparison function |compare| using parameter |param|
   and memory allocator |allocator|.
   Returns |NULL| if memory allocation failed. */

map_t map_create(enum map_flags flags)
{
  map_t tree;

  avl_malloc(tree, sizeof *tree, flags);

  if (tree == NULL)
    return NULL;

  tree->avl_root = NULL;
  tree->flags = flags;
  tree->avl_count = 0;


  return tree;
}

/* Search |tree| for an item matching |item|, and return it if found.
   Otherwise return |NULL|. */
void ** map_find( map_t tree, str key)
{
  struct avl_node *p;

  for (p = tree->avl_root; p != NULL;) {
    int cmp = str_cmp(key, p->key);

    if (cmp < 0)
      p = p->avl_link[0];
    else if (cmp > 0)
      p = p->avl_link[1];
    else /* |cmp == 0| */
      return & (p->val);
  }

  return NULL;
}

/* Inserts |item| into |tree| and returns a pointer to |item|'s address.
   If a duplicate item is found in the tree,
   returns a pointer to the duplicate without inserting |item|.
   Returns |NULL| in case of memory allocation failure.
 */

void ** map_get( map_t tree, str key)
{
  struct avl_node *y;     /* Top node to update balance factor, and parent. */
  struct avl_node *p, *q; /* Iterator, and parent. */
  struct avl_node *n; /* Newly inserted node. */
  struct avl_node *w; /* New root of rebalanced subtree. */
  int dir;    /* Direction to descend. */
  str key_copy;

  y = tree->avl_root;
  dir = 0;
  for (q = NULL, p = tree->avl_root; p != NULL; q = p, p = p->avl_link[dir]) {
    int cmp = str_cmp(key, p->key);
    if (cmp == 0)
      return &p->val;
    dir = cmp > 0;

    if (p->avl_balance != 0)
      y = p;
  }

  avl_malloc( n, sizeof *n, tree->flags );

  if (n == NULL)
    return NULL;

  tree->avl_count++;
  n->avl_link[0] = n->avl_link[1] = NULL;
  n->avl_parent = q;

  if( !( tree->flags & AVLMAP_NO_DUPLICATE ) )
  {
    avl_malloc(key_copy.s, key.len, tree->flags );
    if (!key_copy.s)
      return NULL;

    memcpy(key_copy.s,key.s,key.len);
    key_copy.len = key.len;
    n->key = key_copy;
  }
  else
    n->key = key;

  n->val = NULL;
  if (q != NULL)
    q->avl_link[dir] = n;
  else
    tree->avl_root = n;

  n->avl_balance = 0;

  if (tree->avl_root == n)
    return &n->val;

  for (p = n; p != y; p = q) {
    q = p->avl_parent;
    dir = q->avl_link[0] != p;
    if (dir == 0)
      q->avl_balance--;
    else
      q->avl_balance++;
  }

  if (y->avl_balance == -2) {
    struct avl_node *x = y->avl_link[0];
    if (x->avl_balance == -1) {
      w = x;
      y->avl_link[0] = x->avl_link[1];
      x->avl_link[1] = y;
      x->avl_balance = y->avl_balance = 0;
      x->avl_parent = y->avl_parent;
      y->avl_parent = x;
      if (y->avl_link[0] != NULL)
        y->avl_link[0]->avl_parent = y;
    } else {
      assert(x->avl_balance == +1);
      w = x->avl_link[1];
      x->avl_link[1] = w->avl_link[0];
      w->avl_link[0] = x;
      y->avl_link[0] = w->avl_link[1];
      w->avl_link[1] = y;
      if (w->avl_balance == -1)
        x->avl_balance = 0, y->avl_balance = +1;
      else if (w->avl_balance == 0)
        x->avl_balance = y->avl_balance = 0;
      else /* |w->avl_balance == +1| */
        x->avl_balance = -1, y->avl_balance = 0;
      w->avl_balance = 0;
      w->avl_parent = y->avl_parent;
      x->avl_parent = y->avl_parent = w;
      if (x->avl_link[1] != NULL)
        x->avl_link[1]->avl_parent = x;
      if (y->avl_link[0] != NULL)
        y->avl_link[0]->avl_parent = y;
    }
  } else if (y->avl_balance == +2) {
    struct avl_node *x = y->avl_link[1];
    if (x->avl_balance == +1) {
      w = x;
      y->avl_link[1] = x->avl_link[0];
      x->avl_link[0] = y;
      x->avl_balance = y->avl_balance = 0;
      x->avl_parent = y->avl_parent;
      y->avl_parent = x;
      if (y->avl_link[1] != NULL)
        y->avl_link[1]->avl_parent = y;
    } else {
      assert(x->avl_balance == -1);
      w = x->avl_link[0];
      x->avl_link[0] = w->avl_link[1];
      w->avl_link[1] = x;
      y->avl_link[1] = w->avl_link[0];
      w->avl_link[0] = y;
      if (w->avl_balance == +1)
        x->avl_balance = 0, y->avl_balance = -1;
      else if (w->avl_balance == 0)
        x->avl_balance = y->avl_balance = 0;
      else /* |w->avl_balance == -1| */
        x->avl_balance = +1, y->avl_balance = 0;
      w->avl_balance = 0;
      w->avl_parent = y->avl_parent;
      x->avl_parent = y->avl_parent = w;
      if (x->avl_link[0] != NULL)
        x->avl_link[0]->avl_parent = x;
      if (y->avl_link[1] != NULL)
        y->avl_link[1]->avl_parent = y;
    }
  } else
    return &n->val;
  if (w->avl_parent != NULL)
    w->avl_parent->avl_link[y != w->avl_parent->avl_link[0]] = w;
  else
    tree->avl_root = w;

  return &n->val;
}


/* Inserts |item| into |table|.
   Returns |NULL| if |item| was successfully inserted
   or if a memory allocation error occurred.
   Otherwise, returns the duplicate item. */
void * map_put( map_t table, str key, void *item)
{
  void **p = map_get(table, key);
  void * ret;


  if( p == NULL )
    return p;

  ret = *p;
  *p = item;

  return ret == item ? NULL : ret;
}

void * delete_node(map_t tree, struct avl_node * p)
{
  struct avl_node *q;   /* Parent of |p|. */
  int dir;      /* Side of |q| on which |p| is linked. */
  void * val;

  val = p->val;

  q = p->avl_parent;
  if (q == NULL) {
    q = (struct avl_node *) & tree->avl_root;
    dir = 0;
  }
  else
  {
    if( p == q->avl_link[0] )
      dir = 0;
    else
      dir = 1;
  }

  if (p->avl_link[1] == NULL) {
    q->avl_link[dir] = p->avl_link[0];
    if (q->avl_link[dir] != NULL)
      q->avl_link[dir]->avl_parent = p->avl_parent;
  } else {
    struct avl_node *r = p->avl_link[1];
    if (r->avl_link[0] == NULL) {
      r->avl_link[0] = p->avl_link[0];
      q->avl_link[dir] = r;
      r->avl_parent = p->avl_parent;
      if (r->avl_link[0] != NULL)
        r->avl_link[0]->avl_parent = r;
      r->avl_balance = p->avl_balance;
      q = r;
      dir = 1;
    } else {
      struct avl_node *s = r->avl_link[0];
      while (s->avl_link[0] != NULL)
        s = s->avl_link[0];
      r = s->avl_parent;
      r->avl_link[0] = s->avl_link[1];
      s->avl_link[0] = p->avl_link[0];
      s->avl_link[1] = p->avl_link[1];
      q->avl_link[dir] = s;
      if (s->avl_link[0] != NULL)
        s->avl_link[0]->avl_parent = s;
      s->avl_link[1]->avl_parent = s;
      s->avl_parent = p->avl_parent;
      if (r->avl_link[0] != NULL)
        r->avl_link[0]->avl_parent = r;
      s->avl_balance = p->avl_balance;
      q = r;
      dir = 0;
    }
  }

  if(!( tree->flags & AVLMAP_NO_DUPLICATE ) )
    avl_free(p->key.s,tree->flags);

  avl_free(p,tree->flags);

  while (q != (struct avl_node *) & tree->avl_root) {
    struct avl_node *y = q;

    if (y->avl_parent != NULL)
      q = y->avl_parent;
    else
      q = (struct avl_node *) & tree->avl_root;

    if (dir == 0) {
      dir = q->avl_link[0] != y;
      y->avl_balance++;
      if (y->avl_balance == +1)
        break;
      else if (y->avl_balance == +2) {
        struct avl_node *x = y->avl_link[1];
        if (x->avl_balance == -1) {
          struct avl_node *w;

          w = x->avl_link[0];
          x->avl_link[0] = w->avl_link[1];
          w->avl_link[1] = x;
          y->avl_link[1] = w->avl_link[0];
          w->avl_link[0] = y;
          if (w->avl_balance == +1)
            x->avl_balance = 0, y->avl_balance = -1;
          else if (w->avl_balance == 0)
            x->avl_balance = y->avl_balance = 0;
          else /* |w->avl_balance == -1| */
            x->avl_balance = +1, y->avl_balance = 0;
          w->avl_balance = 0;
          w->avl_parent = y->avl_parent;
          x->avl_parent = y->avl_parent = w;
          if (x->avl_link[0] != NULL)
            x->avl_link[0]->avl_parent = x;
          if (y->avl_link[1] != NULL)
            y->avl_link[1]->avl_parent = y;
          q->avl_link[dir] = w;
        } else {
          y->avl_link[1] = x->avl_link[0];
          x->avl_link[0] = y;
          x->avl_parent = y->avl_parent;
          y->avl_parent = x;
          if (y->avl_link[1] != NULL)
            y->avl_link[1]->avl_parent = y;
          q->avl_link[dir] = x;
          if (x->avl_balance == 0) {
            x->avl_balance = -1;
            y->avl_balance = +1;
            break;
          } else {
            x->avl_balance = y->avl_balance = 0;
            y = x;
          }
        }
      }
    } else {
      dir = q->avl_link[0] != y;
      y->avl_balance--;
      if (y->avl_balance == -1)
        break;
      else if (y->avl_balance == -2) {
        struct avl_node *x = y->avl_link[0];
        if (x->avl_balance == +1) {
          struct avl_node *w;
          w = x->avl_link[1];
          x->avl_link[1] = w->avl_link[0];
          w->avl_link[0] = x;
          y->avl_link[0] = w->avl_link[1];
          w->avl_link[1] = y;
          if (w->avl_balance == -1)
            x->avl_balance = 0, y->avl_balance = +1;
          else if (w->avl_balance == 0)
            x->avl_balance = y->avl_balance = 0;
          else /* |w->avl_balance == +1| */
            x->avl_balance = -1, y->avl_balance = 0;
          w->avl_balance = 0;
          w->avl_parent = y->avl_parent;
          x->avl_parent = y->avl_parent = w;
          if (x->avl_link[1] != NULL)
            x->avl_link[1]->avl_parent = x;
          if (y->avl_link[0] != NULL)
            y->avl_link[0]->avl_parent = y;
          q->avl_link[dir] = w;
        } else {
          y->avl_link[0] = x->avl_link[1];
          x->avl_link[1] = y;
          x->avl_parent = y->avl_parent;
          y->avl_parent = x;
          if (y->avl_link[0] != NULL)
            y->avl_link[0]->avl_parent = y;
          q->avl_link[dir] = x;
          if (x->avl_balance == 0) {
            x->avl_balance = +1;
            y->avl_balance = -1;
            break;
          } else {
            x->avl_balance = y->avl_balance = 0;
            y = x;
          }
        }
      }
    }
  }

  tree->avl_count--;
  return(void *) val;

};

/* Deletes from |tree| and returns an item matching |item|.
   Returns a null pointer if no matching item found. */
void * map_remove( map_t tree, str key)
{
  struct avl_node *p; /* Traverses tree to find node to delete. */
  int dir; /* Side of |q| on which |p| is linked. */

  if (tree->avl_root == NULL)
    return NULL;

  p = tree->avl_root;
  for (;;) {
    int cmp = str_cmp(key, p->key);
    if (cmp == 0)
      break;

    dir = cmp > 0;
    p = p->avl_link[dir];
    if (p == NULL)
      return NULL;
  }

  return delete_node( tree, p );

}




/* Frees storage allocated for |tree|.
   If |destroy != NULL|, applies it to each data item in inorder. */
void map_destroy( map_t tree, value_destroy_func destroy)
{
  struct avl_node *p, *q;

  for (p = tree->avl_root; p != NULL; p = q)
    if (p->avl_link[0] == NULL) {
      q = p->avl_link[1];
      if (destroy != NULL && p->val != NULL)
        destroy(p->val);
      if( !(tree->flags & AVLMAP_NO_DUPLICATE ) )
        avl_free( p->key.s,tree->flags);
      avl_free( p, tree->flags );
    } else {
      q = p->avl_link[0];
      p->avl_link[0] = q->avl_link[1];
      q->avl_link[1] = p;
    }

  avl_free( tree, tree->flags );
}

int map_size( map_t tree )
{
  return tree->avl_count;
}


void process_all( map_t tree,  struct avl_node *p, process_each_func f, void * param );

void process_all( map_t tree,  struct avl_node *p, process_each_func f, void * param )
{
  if( tree->ret_code )
    return;

  if( p->avl_link[0] )
    process_all( tree, p->avl_link[0], f ,param );

  tree->ret_code |= f( param, p->key, p->val);

  if( p->avl_link[1] )
    process_all( tree, p->avl_link[1], f ,param );
}

int map_for_each( map_t tree, process_each_func f, void * param)
{
  tree->ret_code = 0;

  if( tree->avl_root )
    process_all( tree, tree->avl_root, f, param);

  return tree->ret_code;


}

int map_first( map_t map, map_iterator_t * it)
{
  if( map == NULL || it == NULL )
    return -1;

  it->map = map;

  it->node = map->avl_root;

  if( it->node )
  {
    while( it->node->avl_link[0] )
      it->node = it->node->avl_link[0];
  }

  return 0;
}


int map_last( map_t map, map_iterator_t * it)
{
  if( map == NULL || it == NULL )
    return -1;

  it->map = map;

  it->node = map->avl_root;

  if( it->node )
  {
    while( it->node->avl_link[1] )
      it->node = it->node->avl_link[1];
  }

  return 0;
}

str * iterator_key( map_iterator_t * it )
{
  if( it == NULL )
    return NULL;

  return &it->node->key;
}

void**  iterator_val( map_iterator_t * it )
{
  if( it == NULL )
    return NULL;

  return &it->node->val;
}

int iterator_is_valid( map_iterator_t * it )
{
  if( it == NULL || it->map ==NULL || it->node == NULL)
    return 0;

  return 1;
}

int iterator_next( map_iterator_t * it  )
{

  struct avl_node *q, *p;   /* Current node and its child. */

  if( it == NULL || it->map ==NULL || it->node == NULL)
    return -1;

  if( it->node->avl_link[1] )
  {
    it->node = it->node->avl_link[1];
    while( it->node->avl_link[0] )
      it->node = it->node->avl_link[0];

  }
  else
  {

    for (p = it->node, q = p->avl_parent ; ; p = q, q = q->avl_parent)
      if (q == NULL || p == q->avl_link[0])
      {
        it->node = q;
        return 0;
      }
  }

  return 0;
}


int iterator_prev( map_iterator_t * it  )
{

  struct avl_node *q, *p;   /* Current node and its child. */

  if( it == NULL || it->map ==NULL || it->node == NULL)
    return -1;

  if( it->node->avl_link[0] )
  {
    it->node = it->node->avl_link[0];
    while( it->node->avl_link[1] )
      it->node = it->node->avl_link[1];

  }
  else
  {

    for (p = it->node, q = p->avl_parent ; ; p = q, q = q->avl_parent)
      if (q == NULL || p == q->avl_link[1])
      {
        it->node = q;
        return 0;
      }
  }

  return 0;
}

void * iterator_delete( map_iterator_t * it  )
{
  void * ret;

  if( it == NULL || it->map ==NULL || it->node == NULL)
    return NULL;

  ret = delete_node( it->map, it->node );

  it->node = NULL;

  return ret;
}


Coverage Report

Created: 2025-07-12 06:14

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Copyright (C) 2009 Voice System SRL
3		*
4		* This file is part of opensips, a free SIP server.
5		*
6		* opensips is free software; you can redistribute it and/or modify
7		* it under the terms of the GNU General Public License as published by
8		* the Free Software Foundation; either version 2 of the License, or
9		* (at your option) any later version
10		*
11		* opensips is distributed in the hope that it will be useful,
12		* but WITHOUT ANY WARRANTY; without even the implied warranty of
13		* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14		* GNU General Public License for more details.
15		*
16		* You should have received a copy of the GNU General Public License
17		* along with this program; if not, write to the Free Software
18		* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19		*
20		* History:
21		* --------
22		* 2009-09-16 initial version (andreidragus)
23		*
24		*/
25
26		#include <assert.h>
27		#include <stdio.h>
28		#include <stdlib.h>
29		#include <string.h>
30		#include "str.h"
31		#include "map.h"
32
33		#include "mem/mem.h"
34		#include "mem/shm_mem.h"
35		#include "mem/rpm_mem.h"
36
37	0	#define avl_malloc(dest,size,flags) do \
38	0	{ \
39	0	if(flags & AVLMAP_SHARED) \
40	0	(dest) = shm_malloc(size); \
41	0	else if (flags & AVLMAP_PERSISTENT) \
42	0	(dest) = rpm_malloc(size); \
43	0	else \
44	0	(dest) = pkg_malloc(size); \
45	0	} while(0)
46
47	0	#define avl_free(dest,flags) do \
48	0	{ \
49	0	if(flags & AVLMAP_SHARED) \
50	0	shm_free(dest); \
51	0	else if (flags & AVLMAP_PERSISTENT) \
52	0	rpm_free(dest); \
53	0	else \
54	0	pkg_free(dest); \
55	0	} while(0)
56
57
58	0	#define min(a,b) ((a)<(b))?(a):(b)
59
60
61		static int str_cmp(str s1, str s2)
62	0	{
63	0	int ret;
64
65	0	ret = strncmp( s1.s, s2.s, min( s1.len, s2.len) );
66
67	0	if( ret == 0)
68	0	ret = s1.len - s2.len;
69
70
71	0	return ret;
72	0	}
73
74
75		/* Creates and returns a new table
76		with comparison function \|compare\| using parameter \|param\|
77		and memory allocator \|allocator\|.
78		Returns \|NULL\| if memory allocation failed. */
79
80		map_t map_create(enum map_flags flags)
81	0	{
82	0	map_t tree;
83
84	0	avl_malloc(tree, sizeof *tree, flags);
85
86	0	if (tree == NULL)
87	0	return NULL;
88
89	0	tree->avl_root = NULL;
90	0	tree->flags = flags;
91	0	tree->avl_count = 0;
92
93
94	0	return tree;
95	0	}
96
97		/* Search \|tree\| for an item matching \|item\|, and return it if found.
98		Otherwise return \|NULL\|. */
99		void ** map_find( map_t tree, str key)
100	0	{
101	0	struct avl_node *p;
102
103	0	for (p = tree->avl_root; p != NULL;) {
104	0	int cmp = str_cmp(key, p->key);
105
106	0	if (cmp < 0)
107	0	p = p->avl_link[0];
108	0	else if (cmp > 0)
109	0	p = p->avl_link[1];
110	0	else /* \|cmp == 0\| */
111	0	return & (p->val);
112	0	}
113
114	0	return NULL;
115	0	}
116
117		/* Inserts \|item\| into \|tree\| and returns a pointer to \|item\|'s address.
118		If a duplicate item is found in the tree,
119		returns a pointer to the duplicate without inserting \|item\|.
120		Returns \|NULL\| in case of memory allocation failure.
121		*/
122
123		void ** map_get( map_t tree, str key)
124	0	{
125	0	struct avl_node y; / Top node to update balance factor, and parent. */
126	0	struct avl_node p, q; /* Iterator, and parent. */
127	0	struct avl_node n; / Newly inserted node. */
128	0	struct avl_node w; / New root of rebalanced subtree. */
129	0	int dir; /* Direction to descend. */
130	0	str key_copy;
131
132	0	y = tree->avl_root;
133	0	dir = 0;
134	0	for (q = NULL, p = tree->avl_root; p != NULL; q = p, p = p->avl_link[dir]) {
135	0	int cmp = str_cmp(key, p->key);
136	0	if (cmp == 0)
137	0	return &p->val;
138	0	dir = cmp > 0;
139
140	0	if (p->avl_balance != 0)
141	0	y = p;
142	0	}
143
144	0	avl_malloc( n, sizeof *n, tree->flags );
145
146	0	if (n == NULL)
147	0	return NULL;
148
149	0	tree->avl_count++;
150	0	n->avl_link[0] = n->avl_link[1] = NULL;
151	0	n->avl_parent = q;
152
153	0	if( !( tree->flags & AVLMAP_NO_DUPLICATE ) )
154	0	{
155	0	avl_malloc(key_copy.s, key.len, tree->flags );
156	0	if (!key_copy.s)
157	0	return NULL;
158
159	0	memcpy(key_copy.s,key.s,key.len);
160	0	key_copy.len = key.len;
161	0	n->key = key_copy;
162	0	}
163	0	else
164	0	n->key = key;
165
166	0	n->val = NULL;
167	0	if (q != NULL)
168	0	q->avl_link[dir] = n;
169	0	else
170	0	tree->avl_root = n;
171
172	0	n->avl_balance = 0;
173
174	0	if (tree->avl_root == n)
175	0	return &n->val;
176
177	0	for (p = n; p != y; p = q) {
178	0	q = p->avl_parent;
179	0	dir = q->avl_link[0] != p;
180	0	if (dir == 0)
181	0	q->avl_balance--;
182	0	else
183	0	q->avl_balance++;
184	0	}
185
186	0	if (y->avl_balance == -2) {
187	0	struct avl_node *x = y->avl_link[0];
188	0	if (x->avl_balance == -1) {
189	0	w = x;
190	0	y->avl_link[0] = x->avl_link[1];
191	0	x->avl_link[1] = y;
192	0	x->avl_balance = y->avl_balance = 0;
193	0	x->avl_parent = y->avl_parent;
194	0	y->avl_parent = x;
195	0	if (y->avl_link[0] != NULL)
196	0	y->avl_link[0]->avl_parent = y;
197	0	} else {
198	0	assert(x->avl_balance == +1);
199	0	w = x->avl_link[1];
200	0	x->avl_link[1] = w->avl_link[0];
201	0	w->avl_link[0] = x;
202	0	y->avl_link[0] = w->avl_link[1];
203	0	w->avl_link[1] = y;
204	0	if (w->avl_balance == -1)
205	0	x->avl_balance = 0, y->avl_balance = +1;
206	0	else if (w->avl_balance == 0)
207	0	x->avl_balance = y->avl_balance = 0;
208	0	else /* \|w->avl_balance == +1\| */
209	0	x->avl_balance = -1, y->avl_balance = 0;
210	0	w->avl_balance = 0;
211	0	w->avl_parent = y->avl_parent;
212	0	x->avl_parent = y->avl_parent = w;
213	0	if (x->avl_link[1] != NULL)
214	0	x->avl_link[1]->avl_parent = x;
215	0	if (y->avl_link[0] != NULL)
216	0	y->avl_link[0]->avl_parent = y;
217	0	}
218	0	} else if (y->avl_balance == +2) {
219	0	struct avl_node *x = y->avl_link[1];
220	0	if (x->avl_balance == +1) {
221	0	w = x;
222	0	y->avl_link[1] = x->avl_link[0];
223	0	x->avl_link[0] = y;
224	0	x->avl_balance = y->avl_balance = 0;
225	0	x->avl_parent = y->avl_parent;
226	0	y->avl_parent = x;
227	0	if (y->avl_link[1] != NULL)
228	0	y->avl_link[1]->avl_parent = y;
229	0	} else {
230	0	assert(x->avl_balance == -1);
231	0	w = x->avl_link[0];
232	0	x->avl_link[0] = w->avl_link[1];
233	0	w->avl_link[1] = x;
234	0	y->avl_link[1] = w->avl_link[0];
235	0	w->avl_link[0] = y;
236	0	if (w->avl_balance == +1)
237	0	x->avl_balance = 0, y->avl_balance = -1;
238	0	else if (w->avl_balance == 0)
239	0	x->avl_balance = y->avl_balance = 0;
240	0	else /* \|w->avl_balance == -1\| */
241	0	x->avl_balance = +1, y->avl_balance = 0;
242	0	w->avl_balance = 0;
243	0	w->avl_parent = y->avl_parent;
244	0	x->avl_parent = y->avl_parent = w;
245	0	if (x->avl_link[0] != NULL)
246	0	x->avl_link[0]->avl_parent = x;
247	0	if (y->avl_link[1] != NULL)
248	0	y->avl_link[1]->avl_parent = y;
249	0	}
250	0	} else
251	0	return &n->val;
252	0	if (w->avl_parent != NULL)
253	0	w->avl_parent->avl_link[y != w->avl_parent->avl_link[0]] = w;
254	0	else
255	0	tree->avl_root = w;
256
257	0	return &n->val;
258	0	}
259
260
261		/* Inserts \|item\| into \|table\|.
262		Returns \|NULL\| if \|item\| was successfully inserted
263		or if a memory allocation error occurred.
264		Otherwise, returns the duplicate item. */
265		void * map_put( map_t table, str key, void *item)
266	0	{
267	0	void **p = map_get(table, key);
268	0	void * ret;
269
270
271	0	if( p == NULL )
272	0	return p;
273
274	0	ret = *p;
275	0	*p = item;
276
277	0	return ret == item ? NULL : ret;
278	0	}
279
280		void * delete_node(map_t tree, struct avl_node * p)
281	0	{
282	0	struct avl_node q; / Parent of \|p\|. */
283	0	int dir; /* Side of \|q\| on which \|p\| is linked. */
284	0	void * val;
285
286	0	val = p->val;
287
288	0	q = p->avl_parent;
289	0	if (q == NULL) {
290	0	q = (struct avl_node *) & tree->avl_root;
291	0	dir = 0;
292	0	}
293	0	else
294	0	{
295	0	if( p == q->avl_link[0] )
296	0	dir = 0;
297	0	else
298	0	dir = 1;
299	0	}
300
301	0	if (p->avl_link[1] == NULL) {
302	0	q->avl_link[dir] = p->avl_link[0];
303	0	if (q->avl_link[dir] != NULL)
304	0	q->avl_link[dir]->avl_parent = p->avl_parent;
305	0	} else {
306	0	struct avl_node *r = p->avl_link[1];
307	0	if (r->avl_link[0] == NULL) {
308	0	r->avl_link[0] = p->avl_link[0];
309	0	q->avl_link[dir] = r;
310	0	r->avl_parent = p->avl_parent;
311	0	if (r->avl_link[0] != NULL)
312	0	r->avl_link[0]->avl_parent = r;
313	0	r->avl_balance = p->avl_balance;
314	0	q = r;
315	0	dir = 1;
316	0	} else {
317	0	struct avl_node *s = r->avl_link[0];
318	0	while (s->avl_link[0] != NULL)
319	0	s = s->avl_link[0];
320	0	r = s->avl_parent;
321	0	r->avl_link[0] = s->avl_link[1];
322	0	s->avl_link[0] = p->avl_link[0];
323	0	s->avl_link[1] = p->avl_link[1];
324	0	q->avl_link[dir] = s;
325	0	if (s->avl_link[0] != NULL)
326	0	s->avl_link[0]->avl_parent = s;
327	0	s->avl_link[1]->avl_parent = s;
328	0	s->avl_parent = p->avl_parent;
329	0	if (r->avl_link[0] != NULL)
330	0	r->avl_link[0]->avl_parent = r;
331	0	s->avl_balance = p->avl_balance;
332	0	q = r;
333	0	dir = 0;
334	0	}
335	0	}
336
337	0	if(!( tree->flags & AVLMAP_NO_DUPLICATE ) )
338	0	avl_free(p->key.s,tree->flags);
339
340	0	avl_free(p,tree->flags);
341
342	0	while (q != (struct avl_node *) & tree->avl_root) {
343	0	struct avl_node *y = q;
344
345	0	if (y->avl_parent != NULL)
346	0	q = y->avl_parent;
347	0	else
348	0	q = (struct avl_node *) & tree->avl_root;
349
350	0	if (dir == 0) {
351	0	dir = q->avl_link[0] != y;
352	0	y->avl_balance++;
353	0	if (y->avl_balance == +1)
354	0	break;
355	0	else if (y->avl_balance == +2) {
356	0	struct avl_node *x = y->avl_link[1];
357	0	if (x->avl_balance == -1) {
358	0	struct avl_node *w;
359
360	0	w = x->avl_link[0];
361	0	x->avl_link[0] = w->avl_link[1];
362	0	w->avl_link[1] = x;
363	0	y->avl_link[1] = w->avl_link[0];
364	0	w->avl_link[0] = y;
365	0	if (w->avl_balance == +1)
366	0	x->avl_balance = 0, y->avl_balance = -1;
367	0	else if (w->avl_balance == 0)
368	0	x->avl_balance = y->avl_balance = 0;
369	0	else /* \|w->avl_balance == -1\| */
370	0	x->avl_balance = +1, y->avl_balance = 0;
371	0	w->avl_balance = 0;
372	0	w->avl_parent = y->avl_parent;
373	0	x->avl_parent = y->avl_parent = w;
374	0	if (x->avl_link[0] != NULL)
375	0	x->avl_link[0]->avl_parent = x;
376	0	if (y->avl_link[1] != NULL)
377	0	y->avl_link[1]->avl_parent = y;
378	0	q->avl_link[dir] = w;
379	0	} else {
380	0	y->avl_link[1] = x->avl_link[0];
381	0	x->avl_link[0] = y;
382	0	x->avl_parent = y->avl_parent;
383	0	y->avl_parent = x;
384	0	if (y->avl_link[1] != NULL)
385	0	y->avl_link[1]->avl_parent = y;
386	0	q->avl_link[dir] = x;
387	0	if (x->avl_balance == 0) {
388	0	x->avl_balance = -1;
389	0	y->avl_balance = +1;
390	0	break;
391	0	} else {
392	0	x->avl_balance = y->avl_balance = 0;
393	0	y = x;
394	0	}
395	0	}
396	0	}
397	0	} else {
398	0	dir = q->avl_link[0] != y;
399	0	y->avl_balance--;
400	0	if (y->avl_balance == -1)
401	0	break;
402	0	else if (y->avl_balance == -2) {
403	0	struct avl_node *x = y->avl_link[0];
404	0	if (x->avl_balance == +1) {
405	0	struct avl_node *w;
406	0	w = x->avl_link[1];
407	0	x->avl_link[1] = w->avl_link[0];
408	0	w->avl_link[0] = x;
409	0	y->avl_link[0] = w->avl_link[1];
410	0	w->avl_link[1] = y;
411	0	if (w->avl_balance == -1)
412	0	x->avl_balance = 0, y->avl_balance = +1;
413	0	else if (w->avl_balance == 0)
414	0	x->avl_balance = y->avl_balance = 0;
415	0	else /* \|w->avl_balance == +1\| */
416	0	x->avl_balance = -1, y->avl_balance = 0;
417	0	w->avl_balance = 0;
418	0	w->avl_parent = y->avl_parent;
419	0	x->avl_parent = y->avl_parent = w;
420	0	if (x->avl_link[1] != NULL)
421	0	x->avl_link[1]->avl_parent = x;
422	0	if (y->avl_link[0] != NULL)
423	0	y->avl_link[0]->avl_parent = y;
424	0	q->avl_link[dir] = w;
425	0	} else {
426	0	y->avl_link[0] = x->avl_link[1];
427	0	x->avl_link[1] = y;
428	0	x->avl_parent = y->avl_parent;
429	0	y->avl_parent = x;
430	0	if (y->avl_link[0] != NULL)
431	0	y->avl_link[0]->avl_parent = y;
432	0	q->avl_link[dir] = x;
433	0	if (x->avl_balance == 0) {
434	0	x->avl_balance = +1;
435	0	y->avl_balance = -1;
436	0	break;
437	0	} else {
438	0	x->avl_balance = y->avl_balance = 0;
439	0	y = x;
440	0	}
441	0	}
442	0	}
443	0	}
444	0	}
445
446	0	tree->avl_count--;
447	0	return(void *) val;
448
449	0	};
450
451		/* Deletes from \|tree\| and returns an item matching \|item\|.
452		Returns a null pointer if no matching item found. */
453		void * map_remove( map_t tree, str key)
454	0	{
455	0	struct avl_node p; / Traverses tree to find node to delete. */
456	0	int dir; /* Side of \|q\| on which \|p\| is linked. */
457
458	0	if (tree->avl_root == NULL)
459	0	return NULL;
460
461	0	p = tree->avl_root;
462	0	for (;;) {
463	0	int cmp = str_cmp(key, p->key);
464	0	if (cmp == 0)
465	0	break;
466
467	0	dir = cmp > 0;
468	0	p = p->avl_link[dir];
469	0	if (p == NULL)
470	0	return NULL;
471	0	}
472
473	0	return delete_node( tree, p );
474
475	0	}
476
477
478
479
480		/* Frees storage allocated for \|tree\|.
481		If \|destroy != NULL\|, applies it to each data item in inorder. */
482		void map_destroy( map_t tree, value_destroy_func destroy)
483	0	{
484	0	struct avl_node p, q;
485
486	0	for (p = tree->avl_root; p != NULL; p = q)
487	0	if (p->avl_link[0] == NULL) {
488	0	q = p->avl_link[1];
489	0	if (destroy != NULL && p->val != NULL)
490	0	destroy(p->val);
491	0	if( !(tree->flags & AVLMAP_NO_DUPLICATE ) )
492	0	avl_free( p->key.s,tree->flags);
493	0	avl_free( p, tree->flags );
494	0	} else {
495	0	q = p->avl_link[0];
496	0	p->avl_link[0] = q->avl_link[1];
497	0	q->avl_link[1] = p;
498	0	}
499
500	0	avl_free( tree, tree->flags );
501	0	}
502
503		int map_size( map_t tree )
504	0	{
505	0	return tree->avl_count;
506	0	}
507
508
509		void process_all( map_t tree, struct avl_node p, process_each_func f, void param );
510
511		void process_all( map_t tree, struct avl_node p, process_each_func f, void param )
512	0	{
513	0	if( tree->ret_code )
514	0	return;
515
516	0	if( p->avl_link[0] )
517	0	process_all( tree, p->avl_link[0], f ,param );
518
519	0	tree->ret_code \|= f( param, p->key, p->val);
520
521	0	if( p->avl_link[1] )
522	0	process_all( tree, p->avl_link[1], f ,param );
523	0	}
524
525		int map_for_each( map_t tree, process_each_func f, void * param)
526	0	{
527	0	tree->ret_code = 0;
528
529	0	if( tree->avl_root )
530	0	process_all( tree, tree->avl_root, f, param);
531
532	0	return tree->ret_code;
533
534
535	0	}
536
537		int map_first( map_t map, map_iterator_t * it)
538	0	{
539	0	if( map == NULL \|\| it == NULL )
540	0	return -1;
541
542	0	it->map = map;
543
544	0	it->node = map->avl_root;
545
546	0	if( it->node )
547	0	{
548	0	while( it->node->avl_link[0] )
549	0	it->node = it->node->avl_link[0];
550	0	}
551
552	0	return 0;
553	0	}
554
555
556		int map_last( map_t map, map_iterator_t * it)
557	0	{
558	0	if( map == NULL \|\| it == NULL )
559	0	return -1;
560
561	0	it->map = map;
562
563	0	it->node = map->avl_root;
564
565	0	if( it->node )
566	0	{
567	0	while( it->node->avl_link[1] )
568	0	it->node = it->node->avl_link[1];
569	0	}
570
571	0	return 0;
572	0	}
573
574		str * iterator_key( map_iterator_t * it )
575	0	{
576	0	if( it == NULL )
577	0	return NULL;
578
579	0	return &it->node->key;
580	0	}
581
582		void** iterator_val( map_iterator_t * it )
583	0	{
584	0	if( it == NULL )
585	0	return NULL;
586
587	0	return &it->node->val;
588	0	}
589
590		int iterator_is_valid( map_iterator_t * it )
591	0	{
592	0	if( it == NULL \|\| it->map ==NULL \|\| it->node == NULL)
593	0	return 0;
594
595	0	return 1;
596	0	}
597
598		int iterator_next( map_iterator_t * it )
599	0	{
600
601	0	struct avl_node q, p; /* Current node and its child. */
602
603	0	if( it == NULL \|\| it->map ==NULL \|\| it->node == NULL)
604	0	return -1;
605
606	0	if( it->node->avl_link[1] )
607	0	{
608	0	it->node = it->node->avl_link[1];
609	0	while( it->node->avl_link[0] )
610	0	it->node = it->node->avl_link[0];
611
612	0	}
613	0	else
614	0	{
615
616	0	for (p = it->node, q = p->avl_parent ; ; p = q, q = q->avl_parent)
617	0	if (q == NULL \|\| p == q->avl_link[0])
618	0	{
619	0	it->node = q;
620	0	return 0;
621	0	}
622	0	}
623
624	0	return 0;
625	0	}
626
627
628		int iterator_prev( map_iterator_t * it )
629	0	{
630
631	0	struct avl_node q, p; /* Current node and its child. */
632
633	0	if( it == NULL \|\| it->map ==NULL \|\| it->node == NULL)
634	0	return -1;
635
636	0	if( it->node->avl_link[0] )
637	0	{
638	0	it->node = it->node->avl_link[0];
639	0	while( it->node->avl_link[1] )
640	0	it->node = it->node->avl_link[1];
641
642	0	}
643	0	else
644	0	{
645
646	0	for (p = it->node, q = p->avl_parent ; ; p = q, q = q->avl_parent)
647	0	if (q == NULL \|\| p == q->avl_link[1])
648	0	{
649	0	it->node = q;
650	0	return 0;
651	0	}
652	0	}
653
654	0	return 0;
655	0	}
656
657		void * iterator_delete( map_iterator_t * it )
658	0	{
659	0	void * ret;
660
661	0	if( it == NULL \|\| it->map ==NULL \|\| it->node == NULL)
662	0	return NULL;
663
664	0	ret = delete_node( it->map, it->node );
665
666	0	it->node = NULL;
667
668	0	return ret;
669	0	}
670