1409302f0f9fce73ea4c82bbfd439041cd7923d34Elliott Hughes/* $NetBSD: tdelete.c,v 1.6 2012/06/25 22:32:45 abs Exp $ */ 221eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng 321eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng/* 421eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng * Tree search generalized from Knuth (6.2.2) Algorithm T just like 521eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng * the AT&T man page says. 621eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng * 721eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng * The node_t structure is for internal use only, lint doesn't grok it. 821eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng * 921eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng * Written by reading the System V Interface Definition, not the code. 1021eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng * 1121eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng * Totally public domain. 1221eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng */ 1321eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng 1421eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng#include <sys/cdefs.h> 1521eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng#if defined(LIBC_SCCS) && !defined(lint) 16409302f0f9fce73ea4c82bbfd439041cd7923d34Elliott Hughes__RCSID("$NetBSD: tdelete.c,v 1.6 2012/06/25 22:32:45 abs Exp $"); 1721eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng#endif /* LIBC_SCCS and not lint */ 1821eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng 19409302f0f9fce73ea4c82bbfd439041cd7923d34Elliott Hughes#include <assert.h> 2021eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng#define _SEARCH_PRIVATE 2121eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng#include <search.h> 2221eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng#include <stdlib.h> 2321eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng 2421eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng 25409302f0f9fce73ea4c82bbfd439041cd7923d34Elliott Hughes/* find a node with key "vkey" in tree "vrootp" */ 2621eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Chengvoid * 27409302f0f9fce73ea4c82bbfd439041cd7923d34Elliott Hughestdelete(const void *vkey, void **vrootp, 2821eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng int (*compar)(const void *, const void *)) 2921eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng{ 3021eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng node_t **rootp = (node_t **)vrootp; 3121eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng node_t *p, *q, *r; 32409302f0f9fce73ea4c82bbfd439041cd7923d34Elliott Hughes int cmp; 33409302f0f9fce73ea4c82bbfd439041cd7923d34Elliott Hughes 34409302f0f9fce73ea4c82bbfd439041cd7923d34Elliott Hughes _DIAGASSERT(vkey != NULL); 35409302f0f9fce73ea4c82bbfd439041cd7923d34Elliott Hughes _DIAGASSERT(compar != NULL); 3621eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng 3721eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng if (rootp == NULL || (p = *rootp) == NULL) 3821eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng return NULL; 3921eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng 4021eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { 4121eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng p = *rootp; 4221eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng rootp = (cmp < 0) ? 4321eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng &(*rootp)->llink : /* follow llink branch */ 4421eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng &(*rootp)->rlink; /* follow rlink branch */ 4521eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng if (*rootp == NULL) 4621eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng return NULL; /* key not found */ 4721eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng } 4821eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng r = (*rootp)->rlink; /* D1: */ 4921eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ 5021eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng q = r; 5121eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng else if (r != NULL) { /* Right link is NULL? */ 5221eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng if (r->llink == NULL) { /* D2: Find successor */ 5321eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng r->llink = q; 5421eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng q = r; 5521eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng } else { /* D3: Find NULL link */ 5621eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng for (q = r->llink; q->llink != NULL; q = r->llink) 5721eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng r = q; 5821eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng r->llink = q->rlink; 5921eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng q->llink = (*rootp)->llink; 6021eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng q->rlink = (*rootp)->rlink; 6121eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng } 6221eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng } 63409302f0f9fce73ea4c82bbfd439041cd7923d34Elliott Hughes if (p != *rootp) 64409302f0f9fce73ea4c82bbfd439041cd7923d34Elliott Hughes free(*rootp); /* D4: Free node */ 6521eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng *rootp = q; /* link parent to new node */ 6621eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng return p; 6721eab513e7eec280a7a8bcb9482a1a8b61e59442Ben Cheng} 68