Update Apple's list and hash utility routines to latest versions (John

    Harper).

3 files changed, 152 insertions, 132 deletions

diff --git a/hw/darwin/quartz/xpr/x-hash.c b/hw/darwin/quartz/xpr/x-hash.c
index 632ffdb33..51fbb2877 100644
--- a/hw/darwin/quartz/xpr/x-hash.c
+++ b/hw/darwin/quartz/xpr/x-hash.c
@@ -35,8 +35,8 @@
 #include <assert.h>
 
 struct x_hash_table_struct {
-    int bucket_index;
-    int total_keys;
+    unsigned int bucket_index;
+    unsigned int total_keys;
     x_list **buckets;
 
     x_hash_fun *hash_key;
@@ -72,28 +72,28 @@ static inline void
 hash_table_destroy_item (x_hash_table *h, void *k, void *v)
 {
     if (h->destroy_key != 0)
-	(*h->destroy_key) (k);
+        (*h->destroy_key) (k);
 
     if (h->destroy_value != 0)
-	(*h->destroy_value) (v);
+        (*h->destroy_value) (v);
 }
 
 static inline unsigned int
 hash_table_hash_key (x_hash_table *h, void *k)
 {
     if (h->hash_key != 0)
-	return (*h->hash_key) (k);
+        return (*h->hash_key) (k);
     else
-	return (unsigned int) k;
+        return (unsigned int) k;
 }
 
 static inline int
 hash_table_compare_keys (x_hash_table *h, void *k1, void *k2)
 {
     if (h->compare_keys == 0)
-	return k1 == k2;
+        return k1 == k2;
     else
-	return (*h->compare_keys) (k1, k2) == 0;
+        return (*h->compare_keys) (k1, k2) == 0;
 }
 
 static void
@@ -106,7 +106,7 @@ hash_table_split (x_hash_table *h)
     int i;
 
     if (h->bucket_index == N_BUCKET_SIZES - 1)
-	return;
+        return;
 
     old_size = hash_table_total_buckets (h);
     old = h->buckets;
@@ -118,22 +118,22 @@ hash_table_split (x_hash_table *h)
 
     if (new == 0)
     {
-	h->bucket_index--;
-	return;
+        h->bucket_index--;
+        return;
     }
 
     for (i = 0; i < old_size; i++)
     {
-	for (node = old[i]; node != 0; node = next)
-	{
-	    next = node->next;
-	    item = node->data;
+        for (node = old[i]; node != 0; node = next)
+        {
+            next = node->next;
+            item = node->data;
 
-	    b = hash_table_hash_key (h, ITEM_KEY (item)) % new_size;
+            b = hash_table_hash_key (h, ITEM_KEY (item)) % new_size;
 
-	    node->next = new[b];
-	    new[b] = node;
-	}
+            node->next = new[b];
+            new[b] = node;
+        }
     }
 
     h->buckets = new;
@@ -142,23 +142,23 @@ hash_table_split (x_hash_table *h)
 
 X_EXTERN x_hash_table *
 X_PFX (hash_table_new) (x_hash_fun *hash,
-			x_compare_fun *compare,
-			x_destroy_fun *key_destroy,
-			x_destroy_fun *value_destroy)
+                        x_compare_fun *compare,
+                        x_destroy_fun *key_destroy,
+                        x_destroy_fun *value_destroy)
 {
     x_hash_table *h;
 
     h = calloc (1, sizeof (x_hash_table));
     if (h == 0)
-	return 0;
+        return 0;
 
     h->bucket_index = 0;
     h->buckets = calloc (hash_table_total_buckets (h), sizeof (x_list *));
 
     if (h->buckets == 0)
     {
-	free (h);
-	return 0;
+        free (h);
+        return 0;
     }
     
     h->hash_key = hash;
@@ -181,13 +181,13 @@ X_PFX (hash_table_free) (x_hash_table *h)
 
     for (i = 0; i < n; i++)
     {
-	for (node = h->buckets[i]; node != 0; node = node->next)
-	{
-	    item = node->data;
-	    hash_table_destroy_item (h, ITEM_KEY (item), ITEM_VALUE (item));
-	    ITEM_FREE (item);
-	}
-	X_PFX (list_free) (h->buckets[i]);
+        for (node = h->buckets[i]; node != 0; node = node->next)
+        {
+            item = node->data;
+            hash_table_destroy_item (h, ITEM_KEY (item), ITEM_VALUE (item));
+            ITEM_FREE (item);
+        }
+        X_PFX (list_free) (h->buckets[i]);
     }
 
     free (h->buckets);
@@ -213,39 +213,39 @@ hash_table_modify (x_hash_table *h, void *k, void *v, int replace)
     hash_value = hash_table_hash_key (h, k);
 
     for (node = h->buckets[hash_value % hash_table_total_buckets (h)];
-	 node != 0; node = node->next)
+         node != 0; node = node->next)
     {
-	item = node->data;
-
-	if (hash_table_compare_keys (h, ITEM_KEY (item), k))
-	{
-	    if (replace)
-	    {
-		hash_table_destroy_item (h, ITEM_KEY (item),
-					 ITEM_VALUE (item));
-		ITEM_KEY (item) = k;
-		ITEM_VALUE (item) = v;
-	    }
-	    else
-	    {
-		hash_table_destroy_item (h, k, ITEM_VALUE (item));
-		ITEM_VALUE (item) = v;
-	    }
-	    return;
-	}
+        item = node->data;
+
+        if (hash_table_compare_keys (h, ITEM_KEY (item), k))
+        {
+            if (replace)
+            {
+                hash_table_destroy_item (h, ITEM_KEY (item),
+                                         ITEM_VALUE (item));
+                ITEM_KEY (item) = k;
+                ITEM_VALUE (item) = v;
+            }
+            else
+            {
+                hash_table_destroy_item (h, k, ITEM_VALUE (item));
+                ITEM_VALUE (item) = v;
+            }
+            return;
+        }
     }
 
     /* Key isn't already in the table. Insert it. */
 
     if (h->total_keys + 1
-	> hash_table_total_buckets (h) * SPLIT_THRESHOLD_FACTOR)
+        > hash_table_total_buckets (h) * SPLIT_THRESHOLD_FACTOR)
     {
-	hash_table_split (h);
+        hash_table_split (h);
     }
 
     hash_value = hash_value % hash_table_total_buckets (h);
     h->buckets[hash_value] = X_PFX (list_prepend) (h->buckets[hash_value],
-						   ITEM_NEW (k, v));
+                                                   ITEM_NEW (k, v));
     h->total_keys++;
 }
 
@@ -272,20 +272,20 @@ X_PFX (hash_table_remove) (x_hash_table *h, void *k)
     hash_value = hash_table_hash_key (h, k);
 
     for (ptr = &h->buckets[hash_value % hash_table_total_buckets (h)];
-	 *ptr != 0; ptr = &((*ptr)->next))
+         *ptr != 0; ptr = &((*ptr)->next))
     {
-	item = (*ptr)->data;
-
-	if (hash_table_compare_keys (h, ITEM_KEY (item), k))
-	{
-	    hash_table_destroy_item (h, ITEM_KEY (item), ITEM_VALUE (item));
-	    ITEM_FREE (item);
-	    item = *ptr;
-	    *ptr = item->next;
-	    X_PFX (list_free_1) (item);
-	    h->total_keys--;
-	    return;
-	}
+        item = (*ptr)->data;
+
+        if (hash_table_compare_keys (h, ITEM_KEY (item), k))
+        {
+            hash_table_destroy_item (h, ITEM_KEY (item), ITEM_VALUE (item));
+            ITEM_FREE (item);
+            item = *ptr;
+            *ptr = item->next;
+            X_PFX (list_free_1) (item);
+            h->total_keys--;
+            return;
+        }
     }
 }
 
@@ -300,28 +300,28 @@ X_PFX (hash_table_lookup) (x_hash_table *h, void *k, void **k_ret)
     hash_value = hash_table_hash_key (h, k);
 
     for (node = h->buckets[hash_value % hash_table_total_buckets (h)];
-	 node != 0; node = node->next)
+         node != 0; node = node->next)
     {
-	item = node->data;
+        item = node->data;
 
-	if (hash_table_compare_keys (h, ITEM_KEY (item), k))
-	{
-	    if (k_ret != 0)
-		*k_ret = ITEM_KEY (item);
+        if (hash_table_compare_keys (h, ITEM_KEY (item), k))
+        {
+            if (k_ret != 0)
+            *k_ret = ITEM_KEY (item);
 
-	    return ITEM_VALUE (item);
-	}
+            return ITEM_VALUE (item);
+        }
     }
 
     if (k_ret != 0)
-	*k_ret = 0;
+        *k_ret = 0;
 
     return 0;
 }
 
 X_EXTERN void
 X_PFX (hash_table_foreach) (x_hash_table *h,
-			    x_hash_foreach_fun *fun, void *data)
+                            x_hash_foreach_fun *fun, void *data)
 {
     int i, n;
     x_list *node, *item;
@@ -332,10 +332,10 @@ X_PFX (hash_table_foreach) (x_hash_table *h,
 
     for (i = 0; i < n; i++)
     {
-	for (node = h->buckets[i]; node != 0; node = node->next)
-	{
-	    item = node->data;
-	    (*fun) (ITEM_KEY (item), ITEM_VALUE (item), data);
-	}
+        for (node = h->buckets[i]; node != 0; node = node->next)
+        {
+            item = node->data;
+            (*fun) (ITEM_KEY (item), ITEM_VALUE (item), data);
+        }
     }
 }
diff --git a/hw/darwin/quartz/xpr/x-list.c b/hw/darwin/quartz/xpr/x-list.c
index 17843362a..c2f1db161 100644
--- a/hw/darwin/quartz/xpr/x-list.c
+++ b/hw/darwin/quartz/xpr/x-list.c
@@ -75,8 +75,8 @@ X_PFX (list_free) (x_list *lst)
 
     for (; lst != NULL; lst = next)
     {
-	next = lst->next;
-	list_free_1 (lst);
+        next = lst->next;
+        list_free_1 (lst);
     }
 
     pthread_mutex_unlock (&freelist_lock);
@@ -91,16 +91,16 @@ X_PFX (list_prepend) (x_list *lst, void *data)
 
     if (freelist == NULL)
     {
-	x_list_block *b;
-	int i;
+        x_list_block *b;
+        int i;
 
-	b = malloc (sizeof (x_list_block));
+        b = malloc (sizeof (x_list_block));
 
-	for (i = 0; i < NODES_PER_BLOCK - 1; i++)
-	    b->l[i].next = &(b->l[i+1]);
-	b->l[i].next = NULL;
+        for (i = 0; i < NODES_PER_BLOCK - 1; i++)
+            b->l[i].next = &(b->l[i+1]);
+        b->l[i].next = NULL;
 
-	freelist = b->l;
+        freelist = b->l;
     }
 
     node = freelist;
@@ -120,10 +120,10 @@ X_PFX (list_append) (x_list *lst, void *data)
     x_list *head = lst;
 
     if (lst == NULL)
-	return X_PFX (list_prepend) (NULL, data);
+        return X_PFX (list_prepend) (NULL, data);
 
     while (lst->next != NULL)
-	lst = lst->next;
+        lst = lst->next;
 
     lst->next = X_PFX (list_prepend) (NULL, data);
 
@@ -137,10 +137,10 @@ X_PFX (list_reverse) (x_list *lst)
     
     while (lst != NULL)
     {
-	next = lst->next;
-	lst->next = head;
-	head = lst;
-	lst = next;
+        next = lst->next;
+        lst->next = head;
+        head = lst;
+        lst = next;
     }
 
     return head;
@@ -151,8 +151,8 @@ X_PFX (list_find) (x_list *lst, void *data)
 {
     for (; lst != NULL; lst = lst->next)
     {
-	if (lst->data == data)
-	    return lst;
+        if (lst->data == data)
+            return lst;
     }
 
     return NULL;
@@ -162,21 +162,40 @@ X_EXTERN x_list *
 X_PFX (list_nth) (x_list *lst, int n)
 {
     while (n-- > 0 && lst != NULL)
-	lst = lst->next;
+        lst = lst->next;
+
+    return lst;
+}
+
+X_EXTERN x_list *
+X_PFX (list_pop) (x_list *lst, void **data_ret)
+{
+    void *data = NULL;
+
+    if (lst != NULL)
+    {
+        x_list *tem = lst;
+        data = lst->data;
+        lst = lst->next;
+        X_PFX (list_free_1) (tem);
+    }
+
+    if (data_ret != NULL)
+        *data_ret = data;
 
     return lst;
 }
 
 X_EXTERN x_list *
 X_PFX (list_filter) (x_list *lst,
-		     int (*pred) (void *item, void *data), void *data)
+                     int (*pred) (void *item, void *data), void *data)
 {
     x_list *ret = NULL, *node;
 
     for (node = lst; node != NULL; node = node->next)
     {
-	if ((*pred) (node->data, data))
-	    ret = X_PFX (list_prepend) (ret, node->data);
+        if ((*pred) (node->data, data))
+            ret = X_PFX (list_prepend) (ret, node->data);
     }
 
     return X_PFX (list_reverse) (ret);
@@ -184,13 +203,13 @@ X_PFX (list_filter) (x_list *lst,
 
 X_EXTERN x_list *
 X_PFX (list_map) (x_list *lst,
-		  void *(*fun) (void *item, void *data), void *data)
+                  void *(*fun) (void *item, void *data), void *data)
 {
     x_list *ret = NULL, *node;
 
     for (node = lst; node != NULL; node = node->next)
     {
-	X_PFX (list_prepend) (ret, fun (node->data, data));
+        X_PFX (list_prepend) (ret, fun (node->data, data));
     }
 
     return X_PFX (list_reverse) (ret);
@@ -203,7 +222,7 @@ X_PFX (list_copy) (x_list *lst)
 
     for (; lst != NULL; lst = lst->next)
     {
-	copy = X_PFX (list_prepend) (copy, lst->data);
+        copy = X_PFX (list_prepend) (copy, lst->data);
     }
 
     return X_PFX (list_reverse) (copy);
@@ -216,15 +235,15 @@ X_PFX (list_remove) (x_list *lst, void *data)
 
     for (ptr = &lst; *ptr != NULL;)
     {
-	node = *ptr;
-
-	if (node->data == data)
-	{
-	    *ptr = node->next;
-	    X_PFX (list_free_1) (node);
-	}
-	else
-	    ptr = &((*ptr)->next);
+        node = *ptr;
+
+        if (node->data == data)
+        {
+            *ptr = node->next;
+            X_PFX (list_free_1) (node);
+        }
+        else
+            ptr = &((*ptr)->next);
     }
 
     return lst;
@@ -237,25 +256,25 @@ X_PFX (list_length) (x_list *lst)
 
     n = 0;
     for (; lst != NULL; lst = lst->next)
-	n++;
+        n++;
 
     return n;
 }
 
 X_EXTERN void
 X_PFX (list_foreach) (x_list *lst,
-		      void (*fun) (void *data, void *user_data),
-		      void *user_data)
+                      void (*fun) (void *data, void *user_data),
+                      void *user_data)
 {
     for (; lst != NULL; lst = lst->next)
     {
-	(*fun) (lst->data, user_data);
+        (*fun) (lst->data, user_data);
     }
 }
 
 static x_list *
 list_sort_1 (x_list *lst, int length,
-	     int (*less) (const void *, const void *))
+             int (*less) (const void *, const void *))
 {
     x_list *mid, *ptr;
     x_list *out_head, *out;
@@ -264,7 +283,7 @@ list_sort_1 (x_list *lst, int length,
     /* This is a standard (stable) list merge sort */
 
     if (length < 2)
-	return lst;
+        return lst;
 
     /* Calculate the halfway point. Split the list into two sub-lists. */
 
@@ -285,16 +304,16 @@ list_sort_1 (x_list *lst, int length,
     assert (lst != NULL && mid != NULL);
 
     if ((*less) (mid->data, lst->data))
-	out = out_head = mid, mid = mid->next;
+        out = out_head = mid, mid = mid->next;
     else
-	out = out_head = lst, lst = lst->next;
+        out = out_head = lst, lst = lst->next;
 
     while (lst != NULL && mid != NULL)
     {
         if ((*less) (mid->data, lst->data))
-	    out = out->next = mid, mid = mid->next;
+            out = out->next = mid, mid = mid->next;
         else
-	    out = out->next = lst, lst = lst->next;
+            out = out->next = lst, lst = lst->next;
     }
 
     if (lst != NULL)
diff --git a/hw/darwin/quartz/xpr/x-list.h b/hw/darwin/quartz/xpr/x-list.h
index 991e2b1f6..3faed5330 100644
--- a/hw/darwin/quartz/xpr/x-list.h
+++ b/hw/darwin/quartz/xpr/x-list.h
@@ -55,24 +55,25 @@ X_EXTERN x_list *X_PFX (list_prepend) (x_list *lst, void *data);
 X_EXTERN x_list *X_PFX (list_append) (x_list *lst, void *data);
 X_EXTERN x_list *X_PFX (list_remove) (x_list *lst, void *data);
 X_EXTERN void X_PFX (list_free) (x_list *lst);
+X_EXTERN x_list *X_PFX (list_pop) (x_list *lst, void **data_ret);
 
 X_EXTERN x_list *X_PFX (list_copy) (x_list *lst);
 X_EXTERN x_list *X_PFX (list_reverse) (x_list *lst);
 X_EXTERN x_list *X_PFX (list_find) (x_list *lst, void *data);
 X_EXTERN x_list *X_PFX (list_nth) (x_list *lst, int n);
 X_EXTERN x_list *X_PFX (list_filter) (x_list *src,
-				      int (*pred) (void *item, void *data),
-				      void *data);
+                                      int (*pred) (void *item, void *data),
+                                      void *data);
 X_EXTERN x_list *X_PFX (list_map) (x_list *src,
-				   void *(*fun) (void *item, void *data),
-				   void *data);
+                                   void *(*fun) (void *item, void *data),
+                                   void *data);
 
 X_EXTERN unsigned int X_PFX (list_length) (x_list *lst);
 X_EXTERN void X_PFX (list_foreach) (x_list *lst, void (*fun)
-				    (void *data, void *user_data),
-				    void *user_data);
+                                    (void *data, void *user_data),
+                                    void *user_data);
 
 X_EXTERN x_list *X_PFX (list_sort) (x_list *lst, int (*less) (const void *,
-							    const void *));
+                                    const void *));
 
 #endif /* X_LIST_H */